GỢI Ý GIẢI ĐỀ THI MÔN TOÁN RỜI RẠC 2(ĐỀ 4)
Đề số 1(2016-2017)
Câu 1:
a,
deg(1)=2
deg(2)=2
deg(3)=2
deg(4)=2
deg(5)=4
deg(6)=3
deg(7)=2
deg(8)=1
b,Biểu diễn đồ thị G dưới dạng ma trận kề:
Câu 2:
a,
int n;//n là số đỉnh
bool chuaxet[MAX];//Mảng chuaxet lưu trạng thái của từng
đỉnh
for(int i=1;i<=n;i++){
chuaxet[i]=true;
}
void DFS(int u){
cout<<u<<”
”;
chuaxet[u]=false;
for(int
v=1;v<=n;v++){
if(chuaxet[v]&&a[u][v]){
DFS(v);
}
}
}
b,
DFS(1)={1(0),3(1),4(3),5(4),2(5),6(2),7(6),8(7)}=V;
èSố
thành phần liên thông: k=1
Đỉnh u
|
Số TPLT l của G\{u}
|
l>k
|
Đỉnh trụ
|
1
|
l=1
|
-------
|
-------
|
2
|
l=1
|
-------
|
-------
|
3
|
l=1
|
-------
|
-------
|
4
|
l=1
|
-------
|
-------
|
5
|
l=2
|
Yes
|
5
|
6
|
l=2
|
Yes
|
6
|
7
|
l=2
|
Yes
|
7
|
8
|
l=1
|
-------
|
-------
|
KL: Có 3 đỉnh là đỉnh trụ: 5,6,7
Câu 3:
a,
*Điều kiện cần và đủ để một đồ thị vô hướng là EULER:
-Đồ thị vô hướng G liên thông
-Mọi đỉnh v thuộc V đều có bậc chẵn
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
0
|
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
2
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
3
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
4
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
5
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
6
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
7
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
8
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
9
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
*Chứng minh đồ thị vô hướng G là Euler:
-BFS(1)={1(0),2(1),10(1),6(2),5(6),7(6),9(6),3(5),4(7),8(7)}=V
àG
liên thông (1)
-Tính bậc của các đỉnh:
deg(1)=2
deg(2)=4
deg(3)=2
deg(4)=2
deg(5)=2
deg(6)=4
deg(7)=4
deg(8)=2
deg(9)=2
deg(10)=2
àTất
cả 10 đỉnh đều có bậc chẵn (2)
(1),(2) èĐồ thị vô hướng G là Euler.
b,Tìm chu trình Euler
trên đồ thị G bắt đầu từ đỉnh 2
n=10,u=2;
Bước
|
Stack
|
CE
|
0
|
2
|
Ø
|
1
|
2,1,10,2,6,5,3,4,7,6,9,7,8
|
2
|
2
|
Ø
|
2,8,7,9,6,7,4,3,5,6,2,10,1,2
|
KL: Chu trình Euler bắt
đầu từ đỉnh 2: 2-1-10-2-6-5-3-4-7-6-9-7-8-2
Câu 4:
a,
Thuật toán Kruskal:
Bước 1: (Khởi tạo)
T= Ø;//Khởi tạo tập cạnh cây khung là rỗng
d(H)=0;//Khởi tạo độ dài cây khung là 0
Bước 2: (Sắp xếp)
<Sắp xếp các cạnh đồ thị theo thứ tự tăng dần trọng
số>;
Bước 3:(Lặp)
While(|T|<n-1&&E ≠ Ø){//Lặp
nếu |T|<n-1 và E ≠ Ø
e=<Cạnh có độ dài nhỏ nhất>;
E=E\{e};//Loại cạnh e ra khỏi đồ thị
If(T◡{e} không tạo nên chu trình) then{
T=T◡{e};//Kết nạp cạnh e vào cây
khung
d(H)=d(H)+d(e);//Cập nhật
độ dài tập cạnh cây khung
}
}
Bước 4: (Trả lại kết quả)
If(|T|<n-1) then <đồ thì không liên thông>;
Else Return(T,d(H));
b,
n=10;
Sắp xếp các cạnh theo thứ tự tăng dần của trọng số:
(1,2)<=(1,3)<=(2,3)<=(5,8)<=(1,7)<=(2,7)<=(3,8)<=(6,7)<=(5,9)<=(3,6)<=(5,6)<=(8,10)<=(4,5)<=(7,10)<=(9,10)<=(2,9)<=(5,10)
Lập bảng:
Cạnh ei
|
T ◡ei
chứa chu trình
|
T
|
WT
|
k
|
(1,2)
|
No
|
(1,2)
|
1
|
1
|
(1,3)
|
No
|
(1,3)
|
2
|
2
|
(2,3)
|
Yes
|
------
|
------
|
------
|
(5,8)
|
No
|
(5,8)
|
3
|
3
|
(1,7)
|
No
|
(1,7)
|
5
|
4
|
(2,7)
|
Yes
|
-----
|
-----
|
-----
|
(3,8)
|
No
|
(3,8)
|
8
|
5
|
(6,7)
|
No
|
(6,7)
|
11
|
6
|
(5,9)
|
No
|
(5,9)
|
15
|
7
|
(3,6)
|
Yes
|
-----
|
-----
|
-----
|
(5,6)
|
Yes
|
-----
|
-----
|
-----
|
(8,10)
|
No
|
(8,10)
|
20
|
8
|
(4,5)
|
No
|
(4,5)
|
26
|
9
|
KL:
WTmin=26;
T={(1,2),(1,3),(5,8),(1,7),(3,8),(6,7),(5,9),(8,10),(4,5)}
Câu 5:
a,
void DIJKSTRA(int u){
int
n,v;//n la so dinh do thi,v la đỉnh cuối
cout<<"Duong
di tu dinh u den dinh ";
cin>>v;
int
truoc[100],d[100];/*Mảng truoc[] lưu đỉnh trước,d[] lưu độ dài đường đi từ đỉnh u đến đỉnh xét*/
bool
chuaxet[100];
for(int
i=1;i<=n;i++){
d[i]=a[u][i];
truoc[i]=u;
chuaxet[i]=true;
}
truoc[u]=0;
d[u]=0;
chuaxet[u]=false;
int
i,j;
while(chuaxet[v]){
minp=2000;
for(i=1;i<=n;i++){//Tìm
đỉnh i sao cho d[i] min
if(chuaxet[i]&&(minp>d[i])){
j=i;
minp=d[i];
}
}
chuaxet[j]=false;
if(chuaxet[v]){
for(i=1;i<=n;i++){
if(chuaxet[i]&&(d[j]+a[j][i])<d[i]){
d[i]=d[j]+a[j][i]);
truoc[i]=j;
}
}
}
int i=truoc[v];
while(i!=u){
cout<<i<<”
“;//In ra duong di tu dinh u đến đỉnh v
i=truoc[i];
}
}
b,n=10,u=1,v=4
Lập bảng:
Bước
|
d[1]|p[1]
|
d[2]|p[2]
|
d[3]|p[3]
|
d[4]|p[4]
|
d[5]|p[5]
|
d[6]|p[6]
|
d[7]|p[7]
|
d[8]|p[8]
|
1
|
0|1
|
4|1
|
∞|1
|
∞|1
|
∞|1
|
∞|1
|
1|1
|
∞|1
|
2
|
3|7
|
∞|1
|
∞|1
|
∞|1
|
6|7
|
1|1
|
∞|1
|
|
3
|
3|7
|
8|2
|
∞|1
|
∞|1
|
4|2
|
∞|1
|
||
4
|
8|2
|
∞|1
|
7|6
|
4|2
|
5|6
|
|||
5
|
7|8
|
∞|1
|
7|6
|
5|6
|
||||
6
|
7|8
|
9|3
|
7|6
|
|||||
7
|
8|5
|
7|6
|
||||||
8
|
8|5
|
KL:
Đường đi ngắn nhất từ đỉnh số 1 tới đỉnh số 4: 1à7à2à6à5à4
(Độ dài 8)
Tải đề thi: Tải về
Nếu thấy tài liệu có ích hi vọng mọi người ủng hộ trang web bằng cách like và theo dõi địa chỉ page chính thức của Tài Liệu Blog tại đây nhé: https://www.facebook.com/TaiLieuBlog/
💰Ủng hộ blog: https://unghotoi.com/1546792457ngwn4
Nhận xét