Gợi ý giải đề thi môn Toán rời rạc 2(Đề 1)
Gợi ý:
Đề số 1
Câu 1:
a,
deg(1)=3
deg(5)=2
deg(2)=2 deg(6)=4
deg(3)=3
deg(7)=3
deg(4)=3
deg(8)=2
b,
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
2
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
3
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
4
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
5
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
6
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
7
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
8
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
c,
Đỉnh đầu
|
Đỉnh cuối
|
Đỉnh đầu
|
Đỉnh cuối
|
1
|
2
|
4
|
6
|
1
|
3
|
5
|
6
|
1
|
4
|
5
|
7
|
2
|
3
|
6
|
7
|
3
|
4
|
6
|
8
|
7
|
8
|
Câu 2:
a,
BFS(7)={7(0),5(7),6(7),8(7),4(6),1(4),3(4),2(1)}
Đường đi từ đỉnh 7 -> đỉnh 2: 7à6à4à1à2
b,
BFS(1)={1(0),2(1),3(1),4(1),6(4),5(6),7(6),8(6)}=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
|
DFS(2)={2(0),3(2),4(3),6(4),5(6),7(6),8(6)}
àl=1
|
No
|
------
|
4
|
DFS(1)={1(0),2(1),3(1)}
DFS(5)={5(0),6(5),7(5),8(6)}
àl=2
|
Yes
|
4
|
6
|
DFS(1)={1(0),2(1),3(1),4(1)}
DFS(5)={5(0),7(5),8(7)}
àl=2
|
Yes
|
6
|
KL:Đỉnh 4,6 là các đỉnh trụ
Câu 3:
a,
Input: Cho đồ thị G=(V,E) gồm n đỉnh biểu diễn bởi ma trận kề
Output: Tìm chu trình Euler của đồ thị G bắt đầu từ đỉnh u.
(1): Kiểm tra G có thỏa mãn điều kiện hay không
Nếu G không thỏa mãn điều kiện thì kt=0
Nếu có chu trình Euler thì kt=1
(2):Nếu kt=0 => thông báo đồ thị không có chu trình Euler và dừng
Nếu kt=1 =>Chọn u là đỉnh cho trước và chuyển sang (3)
(3): Xây dựng chu trình Euler trong G
(3.1) Tạo mảng CE để ghi chu trình Euler vào stack để xếp các đỉnh sẽ
xét.Xếp đỉnh u và stack
(3.2)Xét đỉnh v nằm trên cùng của Stack và thực hiện:
- Nếu v là đỉnh cô lập thì lấy v ra khỏi Stack và đưa vào CE
- Nếu v có đỉnh kề là x thì đưa x vào Stack sau đó xóa cạnh nối v với x
(3.3)Quay lại (3.2) cho tới khi Stack rỗng
(4)Xuất chi trình EULER chứa trong CE theo thứ tự ngược lại
b,
BFS(1)={1(0),2(1),3(1),5(1),6(1),7(3),8(3),4(5),9(7)}=V
=> G liên thông 1
Tính bậc của các đỉnh:
Deg(1)=4
Deg(2)=2
Deg(3)=4
Deg(4)=2
Deg(5)=4
Deg(6)=4
Deg(7)=4
Deg(8)=4
Deg(9)=2
=> Tất cả 9 đỉnh đều có bậc chẵn 2
àG là đồ thị EULER
Chu trình EULER của đồ thị G bắt đầu từ đỉnh 1
Bước
|
Stack
|
CE
|
1
|
1,2,3,1,5,4,6,1
|
Ø
|
2
|
1,2,3,1,5,4,6,5,7,3,8,6
|
1
|
3
|
1,2,3,1,5,4,6,5,7,3,8,7,9,8
|
1,6
|
4
|
1,2,3,1,5,4,6,5,7,3,8,7,9
|
1,6,8
|
5
|
Ø
|
1,6,8,9,7,8,3,7,5,6,4,5,1,3,2,1
|
KL: Chu trình EULER bắt
đầu từ đỉnh 1:
1-2-3-1-5-4-6-5-7-3-8-7-9-8-6-1
Câu 4:
a,Thuật toán xây dựng cây khung nhỏ nhất H=<V,T>:
Bước 1: Khởi tạo
T= Ø;//Khởi tạo tập
cạnh cây khung là Ø
d(H)=0;//Khởi tạo độ dài nhỏ nhất của cây khung là 0
Bước 2: Sắp xếp
<Sắp xếp các cạnh của đồ thị theo thứ tự tăng dần trọng số>
Bước 3:Lặp
While(|T|<n-1&&E‡ Ø){
e=<Cạnh
có độ dài nhỏ nhất>;
E=E\{e};
If(T∪{e} không tạo nên chu trình) then{
T=T
∪{e};
d(H)=d(H)+d(e);
}
Endif;
}
Endwhile;
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=9
Sắp xếp thứ tự các cạnh theo thứ tự tăng dần của trọng số:
(1,2)<=(2,3)<=(3,7)<=(6,8)<=(1,3)<=(4,6)<=(5,7)<=(1,5)<=(1,6)<=(3,8)<=(7,9)<=(4,5)<=(5,6)<=(7,8)<=(8,9)
Cạnh ei
|
T∪ei chứa chu trình
|
T
|
WT
|
k
|
(1,2)
|
No
|
(1,2)
|
1
|
1
|
(2,3)
|
No
|
(2,3)
|
2
|
2
|
(3,7)
|
No
|
(3,7)
|
3
|
3
|
(6,8)
|
No
|
(6,8)
|
4
|
4
|
(1,3)
|
Yes
|
----
|
---------
|
---------
|
(4,6)
|
No
|
(4,6)
|
6
|
5
|
(5,7)
|
No
|
(5,7)
|
8
|
6
|
(1,5)
|
Yes
|
-------
|
--------
|
---------
|
(1,6)
|
No
|
(1,6)
|
11
|
7
|
(3,8)
|
Yes
|
------
|
----------
|
----------
|
(7,9)
|
No
|
(7,9)
|
14
|
8
|
KL: WTmin=14
T={(1,2),(2,3),(3,7),(6,8),(4,6),(5,7),(1,6),(7,9)}
Câu 5:
Các bước thực hiện thuật toán Dijkstra tại s=1
|
|||||
Bước
|
Đỉnh 1
|
Đỉnh 2
|
Đỉnh 3
|
Đỉnh 4
|
Đỉnh 5
|
1
|
<0,1>
|
<4,1>
|
<1,1>
|
<¥,1>
|
<¥,1>
|
2
|
<3,3>
|
<1,1>
|
<¥,1>
|
<6,3>
|
|
3
|
<3,3>
|
<6,2>
|
<4,2>
|
||
4
|
<6,2>
|
<4,2>
|
|||
5
|
<6,2>
|
||||
KL:
Đường
đi ngắn nhất từ đỉnh 1->2: 1à3à2(Độ dài 3)
Đường đi ngắn nhất từ đỉnh 1->3: 1à3 (Độ dài 1)
Đường đi ngắn nhất từ đỉnh 1->4: 1à3à2à4(Độ dài 6)
Đường đi ngắn nhất từ đỉnh 1->5: 1à3à2à5 (Độ dài 4)
Tải đề thi: Tải về
>>Xem thêm
Gợi ý giải đề thi môn Toán rời rạc 2(Đề 2)
Gợi ý giải đề thi môn Toán rời rạc 2(Đề 3)
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