GỢI Ý GIẢI ĐỀ THI MÔN TOÁN RỜI RẠC 2(ĐỀ 5)
GỢI Ý:
Đề số: 3(2014-2015)
Câu 1:
a,
deg(1)=2
deg(2)=4
deg(3)=3
deg(4)=4
deg(5)=4
deg(6)=2
deg(7)=1
b,Biểu diễn đồ thị G dưới
dạng ma trận kề:
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
2
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
3
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
4
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
5
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
6
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
7
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
c,
Đỉnh đầu
|
Đỉnh cuối
|
1
|
2
|
1
|
3
|
2
|
3
|
2
|
4
|
2
|
5
|
3
|
5
|
4
|
5
|
4
|
6
|
4
|
7
|
5
|
6
|
Câu 2:
a,
BFS(7)={7(0),4(7),2(4),5(4),6(4),1(2),3(2)};
èĐường đi từ đỉnh số 7àđỉnh số 1: 7à4à2à1
b,
DFS(1)={1(0),2(1),3(2),5(3),4(5),6(4),7(4)};
àSố thành phần liên thông: k=1.
Lập bảng:
Đỉnh u
|
Số TPLT
l của G\{u}
|
l>k
|
Đỉnh trụ
|
4
|
DFS(1)={ 1(0),2(1),3(2),5(3),6(5)}
DFS(7)={7(0)};
àl=2
|
Yes
|
4
|
6
|
DFS(1)={ 1(0),2(1),3(2),5(3),4(5),7(4)}
àl=1
|
No
|
--------
|
7
|
DFS(1)={ 1(0),2(1),3(2),5(3),4(5),6(4)}
àl=1
|
No
|
---------
|
KL: Đỉnh trụ: 4
Câu 3:
a,
Thuật toán Euler-Cycle(u):
Bước 1: (Khởi tạo)
stack=🛇;//Khởi tạo stack ban đầu rỗng
CE=🛇;//Khởi
tạo mảng CE ban đầu rỗng
Push(u,stack);//Đưa đỉnh u vào ngăn xếp
Bước 2:(Lặp)
while(stack≠ 🛇){//Lặp đến khi nào stack rỗng
s=get(stack);//Lấy
đỉnh đầu của ngăn xếp
if(ke(s)
≠ 🛇){//Nếu danh sach ke(s) chưa rỗng
t=<t
là đỉnh đầu tiên trong ke(s)>;
Push(t,stack);//Đẩy
đỉnh t vào stack
E=E\{s.t};//Loại bỏ cạnh (s,t)
}
else{
Pop(s,stack);//Loại s ra khỏi stack
s=>CE;//Đưa s sang CE
}
}
Bước 3: (Trả lại kết quả)
<Lật ngược các đỉnh trong mảng CE thu được
chu trình EULER >;
b,Tìm chu trình EULER của đồ thị G bắt đầu
từ đỉnh 1
Ke(1)={2,3,5,6}
Ke(2)={1,3}
Ke(3)={1,2,7,8}
Ke(4)={5,6}
Ke(5)={1.4}
Ke(6)={1,4}
Ke(7)={3,9}
Ke(8)={3,9}
Ke(9)={7,8}
n=9,u=1;
Lập bảng:
Bước
|
Stack
|
CE
|
0
|
1
|
🛇
|
1
|
1,2,3
|
1,6,4,5,1
|
2
|
🛇
|
1,6,4,5,1,3,8,9,7,3,2,1
|
KL:Chu trình EULER: 1-2-3-7-9-8-3-1-5-4-6-1
Câu
4:
a,
Thuật toán Kruskal:
Bước 1:(Khởi tạo)
T= 🛇;//Khởi tạo 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: (Sắp xếp)
<Sắp
xếp các cạnh theo thứ tự tăng dần của 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ị
While(T◡{e} không chứa chu trình){
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 cây khung
}
}
Bước
4:(Trả lại kết quả)
If(|T|<n-1)
<Đồ thị không liên thông>;
Else
return(T,d(H));
b,
n=9;
Sắp
xếp các cạnh theo thứ tự tăng dần trọng số:
(1,2)<=(1,5)<=(4,6)<=(1,3)<=(1,6)<=(7,9)<=(2,3)<=(8,9)<=(3,8)<=(4,5)<=(3,7)
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,5)
|
No
|
(1,5)
|
2
|
2
|
(4,6)
|
No
|
(4,6)
|
3
|
3
|
(1,3)
|
No
|
(1,3)
|
5
|
4
|
(1,6)
|
No
|
(1,6)
|
7
|
5
|
(7,9)
|
No
|
(7,9)
|
9
|
6
|
(2,3)
|
Yes
|
-------
|
-------
|
-------
|
(8,9)
|
No
|
(8,9)
|
12
|
7
|
(3,8)
|
No
|
(3,8)
|
16
|
8
|
KL:
WTmin=16
T={(1,2),(1,5),(4,6),(1,3),(1,6),(7,9),(8,9),(3,8)}
Câu 5:
n=1,s=1;
Đồ thị không
chứa chu trình âm
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]
|
0
|
0|0
|
3|1
|
4|1
|
¥|1
|
¥|1
|
1
|
2|3
|
4|1
|
5|2
|
3|2
|
|
2
|
2|3
|
4|1
|
5|2
|
3|2
|
|
3
|
2|3
|
4|1
|
5|2
|
3|2
|
KL:
Đường đi ngắn nhất từ đỉnh 1à đỉnh 5: 1à3à2à5 (Độ dài 3)
>>Xem thêm
Tổng hợp bài tập môn Toán rời rạc 2 kèm gợi ý
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