GỢI Ý GIẢI ĐỀ THI MÔN TOÁN RỜI RẠC 2(ĐỀ 3)
Đề số: 2(2016-2017)
Gợi ý:
Câu 1:
a,
deg(1)=2
deg(2)=3
deg(3)=2
deg(4)=3
deg(5)=3
deg(6)=2
deg(7)=2
deg(8)=1
b,Ma trận kề
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
2
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
3
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
4
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
5
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
6
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
7
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
8
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
Câu 2:
a,
void BFS(int u){
bool chuaxet[MAX];
for(int
i=1;i<=n;i++) chuaxet[i]=true;//n là số đỉnh của đồ thị
queue<int>
q;
q.push(u);
chuaxet[u]=false;
cout<<u<<“
”;
while(!q.empty()){
int
s=q.front();
cout<<s<<”
”;
q.pop();
for(int
i=1;i<=n;i++){
if(chuaxet[i]&&a[s][i]){
chuaxet[i]=false;
q.push(i);
}
}
}
}
b,
BFS(1)={1(0),2(1),3(1),4(2),5(4),6(4),7(5),8(7)}
è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
|
BFS(2)={2(0),3(2),4(2),5(4),6(4),7(5),8(7)}
àl=1
|
No
|
------
|
2
|
BFS(1)={1(0),3(1)}
BFS(4)={4(0),5(4),6(4),7(5),8(7)}
àl=2
|
Yes
|
2
|
3
|
BFS(1)={1(0),2(1),4(2),5(4),6(4),7(5),8(7)}
àl=1
|
No
|
-------
|
4
|
BFS(1)={1(0),2(1),3(1)}
BFS(5)={5(0),6(5),7(5),8(7)}
àl=2
|
Yes
|
4
|
5
|
BFS(1)={ 1(0),2(1),3(1),4(2),6(4)}
BFS(7)={7(0),8(7)}
àl=2
|
Yes
|
5
|
6
|
BFS(1)={1(0),2(1),3(1),4(2),5(4),7(5),8(7)}
àl=1
|
No
|
-------
|
7
|
BFS(1)={ 1(0),2(1),3(1),4(2),5(4),6(4)}
BFS(8)={8(0)}
àl=2
|
Yes
|
7
|
8
|
BFS(1)={ 1(0),2(1),3(1),4(2),5(4),6(4),7(5)}
àl=1
|
No
|
------
|
KL: Các đỉnh trụ : 2,4,5,7
Câu 3:
a,
Điều kiện cần và đủ để một đồ thị vô hướng là nửa EULER:
-Đồ thị vô hướng G liên thông
-Số đỉnh v thuộc V có bậc lẻ không vượt quá 2
Chứng minh đồ thị vô hướng G là nửa EULER:
BFS(1)={1(0),3(1),5(1),2(3),10(3),6(2),8(2),9(2),7(10),4(6)}=V
àĐồ
thị G liên thông (1)
Tính bậc của các đỉnh:
deg(1)=2
deg(2)=4
deg(3)=4
deg(4)=2
deg(5)=2
deg(6)=4
deg(7)=3
deg(8)=2
deg(9)=3
deg(10)=2
àCó
2 đỉnh 7 và 9 là có bậc lẻ (2)
(1),(2)èĐồ thị vô hướng G là nửa EULER.
b,
Tìm đường đi EULER trên
đồ thị G bắt đầu từ u=7
n=10,u=7.
Bước
|
Stack
|
CE
|
1
|
7
|
Ø
|
2
|
Ø
|
9,6,4,8,2,9,7,10,3,5,1,3,2,6,7
|
KL:Đường đi Euler từ đỉnh
u=7: 7-6-2-3-1-5-3-10-7-9-2-8-4-6-9
Câu 4:
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
1
|
0
|
1
|
1
|
¥
|
¥
|
¥
|
2
|
¥
|
¥
|
¥
|
2
|
1
|
0
|
1
|
¥
|
¥
|
¥
|
3
|
¥
|
7
|
¥
|
3
|
1
|
1
|
0
|
¥
|
¥
|
5
|
¥
|
3
|
¥
|
¥
|
4
|
¥
|
¥
|
¥
|
0
|
6
|
¥
|
¥
|
¥
|
¥
|
¥
|
5
|
¥
|
¥
|
¥
|
6
|
0
|
5
|
¥
|
1
|
4
|
7
|
6
|
¥
|
¥
|
5
|
¥
|
5
|
0
|
3
|
¥
|
¥
|
¥
|
7
|
2
|
3
|
¥
|
¥
|
¥
|
3
|
0
|
¥
|
¥
|
6
|
8
|
¥
|
¥
|
3
|
¥
|
1
|
¥
|
¥
|
0
|
¥
|
5
|
9
|
¥
|
7
|
¥
|
¥
|
4
|
¥
|
¥
|
¥
|
0
|
6
|
10
|
¥
|
¥
|
¥
|
¥
|
7
|
¥
|
6
|
5
|
6
|
0
|
a,
Thuật toán Prim(u):
Bước 1: (Khởi tạo)
VH={u};//Khởi tạo tập đỉnh cây khung ban đầu
là u;
V=V\{u};\\Tập đỉnh V được bớt đi u;
T= Ø;//Khởi tạo tập cạnh cây khung ban đầu rỗng
d(H)=0;//Khởi tạo độ dài cây khung ban đầu là 0
Bước 2: (Lặp)
While(V‡ Ø){
e=<s,t>;//e là cạnh có độ dài
nhỏ nhất thỏa mãn s thuộc V,t thuộc VH
d(H)=d(H)+d(e);//Thiết lập độ dài cây
khung nhỏ nhất
T=T ◡e;//Kết nạp cạnh e vào cây khung
V=V\{s};//Tập đỉnh V bớt đi đỉnh s
VH=VH◡{s};//Tập
đỉnh VH thêm đỉnh s
}
Bước 3: (Trả
lại kết quả)
If(|T|<n-1)
then <Đồ thị không liên thông>;
Else Return(T,d(H));
b,
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]
|
d[9]|p[9]
|
d[10]|p[10]
|
1
|
¥|5
|
¥|5
|
¥|5
|
6|5
|
0|0
|
5|5
|
¥|5
|
1|5
|
4|5
|
7|5
|
2
|
¥|5
|
¥|5
|
3|8
|
6|5
|
5|5
|
¥|5
|
1|5
|
4|5
|
5|8
|
|
3
|
1|3
|
1|3
|
3|8
|
6|5
|
5|5
|
¥|5
|
4|5
|
5|8
|
||
4
|
1|3
|
1|3
|
6|5
|
5|5
|
2|1
|
4|5
|
5|8
|
|||
5
|
1|3
|
6|5
|
5|5
|
2|1
|
4|5
|
5|8
|
||||
6
|
6|5
|
3|7
|
2|1
|
4|5
|
5|8
|
|||||
7
|
6|5
|
3|7
|
4|5
|
5|8
|
||||||
8
|
6|5
|
4|5
|
5|8
|
|||||||
9
|
6|5
|
5|8
|
||||||||
10
|
6|5
|
KL: T={(1,3),(2,3),(3,8),(4,5),(6,7),(1,7),(5,8),(5,9),(8,10)};
WT=1+1+3+6+3+2+1+4+5=26
Câu 5:
a,
void BELLMAN(int u){
int D[MAX];// Mảng D chứa độ dài đường đi
int a[MAX][MAX],Trace[MAX];
int n,v;//n là số đỉnh,v là đỉnh kết thúc
for(int i=1;i<=n;i++){
D[i]=A[u][i];
Trace[i]=S;
}
int k,s,t;
D[u]=0;
For(k=1;k<=n-2;k++){
For(s=1;s<=n;s++){
If(s!=u){
For(t=1;t<=n;t++){
If(D[s]>D[t]+a[t,s]){
D[s]= D[t]+a[t,s];
Trace[t]=s;
}
}
}
}
}
While(v!=u){
cout<<”<---”<<v;
v=Trace[v];
}
}
b,
n=8,Đồ thị không chứa chu
trình âm
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]
|
0
|
0|0
|
2|1
|
¥|1
|
¥|1
|
¥|1
|
¥|1
|
3|1
|
¥|1
|
1
|
1|7
|
6|2
|
8|3
|
7|3
|
2|2
|
3|1
|
3|6
|
|
2
|
1|7
|
5|8
|
7|3
|
5|6
|
2|2
|
3|1
|
2|5
|
|
3
|
1|7
|
4|8
|
6|3
|
5|6
|
2|2
|
3|1
|
2|5
|
|
4
|
1|7
|
4|8
|
6|3
|
5|6
|
2|2
|
3|1
|
2|5
|
|
5
|
1|7
|
4|8
|
6|3
|
5|6
|
2|2
|
3|1
|
2|5
|
|
6
|
1|7
|
4|8
|
6|3
|
5|6
|
2|2
|
3|1
|
2|5
|
KL:
Đường đi ngắn nhất từ đỉnh
1->2: 1à7à2(d=1)
Đường đi ngắn nhất từ đỉnh
1->3: 1à7à2à6à5à8à3(d=4)
Đường đi ngắn nhất từ đỉnh
1->4: 1à7à2à6à5à8à3à4(d=6)
Đường đi ngắn nhất từ đỉnh
1->5: 1à7à2à6à5(d=5)
Đường đi ngắn nhất từ đỉnh
1->6: 1à7à2à6(d=2)
Đường đi ngắn nhất từ đỉnh
1->7: 1à7(d=3)
Đường đi ngắn nhất từ đỉnh
1->8: 1à7à2à6à5à8(d=2)
Tải đề thi: Tải về
Nếu thấy tài liệu có ích hi vọng các bạn ủ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