GỢI Ý GIẢI BÀI TẬP TOÁN RỜI RẠC 2(P3)
GỢI Ý GIẢI BÀI TẬP TOÁN RỜI RẠC 2(P3)
Câu hỏi 25a
Cho
đơn đồ thị G = <V, E> gồm 6 đỉnh
được biểu diễn dưới dạng ma trận trọng số như sau
|
|
1
|
2
|
3
|
4
|
5
|
6
|
1
|
0
|
15
|
5
|
20
|
¥
|
¥
|
2
|
1
|
0
|
¥
|
17
|
10
|
¥
|
3
|
¥
|
¥
|
0
|
2
|
¥
|
50
|
4
|
15
|
1
|
¥
|
0
|
¥
|
70
|
5
|
20
|
30
|
¥
|
10
|
0
|
10
|
6
|
¥
|
18
|
¥
|
23
|
20
|
0
|
Hãy thực hiện:
a)
Trình bày thuật toán Floyd tìm đường đi ngắn nhất giữa
các cặp đỉnh trong đồ thị?
b)
Áp dụng thuật toán Floyd, tìm đường đi ngắn nhất giữa
các cặp đỉnh (1, 2), (1, 3), (3, 4), (4, 2) của đồ thị G đã cho, chỉ rõ kết quả
tại mỗi bước thực hiện theo thuật toán?
Giải:
a,
Thuật toán Floyd:
d[i][j] là độ dài đường
đi từ i đến j và pr[i][j] là đỉnh trước j trên đường đi từ i đến j.
- Khởi tạo: d[i][j]= a[i][j];
pr[i][j]= i;
- Với mọi k thuộc G,
i thuộc G, j thuộc G sao cho (d[i][j]> d[i][k] + d[k][j]) thì thay thế:
pr[i][j]=
k; d[i][j]= d[i][k] + d[k][j];
- Xuất d[i][j] và pr[i][j].
Lập bảng:
|
|
1
|
2
|
3
|
4
|
5
|
6
|
1
|
0|1
|
15|1
|
5|1
|
20|1
|
¥|1
|
¥|1
|
2
|
1|2
|
0|2
|
¥|2
|
17|2
|
10|2
|
¥|2
|
3
|
¥|3
|
¥|3
|
0|3
|
2|3
|
¥|3
|
50|3
|
4
|
15|4
|
1|4
|
¥|4
|
0|4
|
¥|4
|
70|4
|
5
|
20|5
|
30|5
|
¥|5
|
10|5
|
0|5
|
10|5
|
6
|
¥|6
|
18|6
|
¥|6
|
23|6
|
20|6
|
0|6
|
(k=1)è
|
|
1
|
2
|
3
|
4
|
5
|
6
|
1
|
0|1
|
15|1
|
5|1
|
20|1
|
¥|1
|
¥|1
|
2
|
1|2
|
0|2
|
6|1
|
17|2
|
10|2
|
¥|2
|
3
|
¥|3
|
¥|3
|
0|3
|
2|3
|
¥|3
|
50|3
|
4
|
15|4
|
1|4
|
20|1
|
0|4
|
¥|4
|
70|4
|
5
|
20|5
|
30|5
|
25|1
|
10|5
|
0|5
|
10|5
|
6
|
¥|6
|
18|6
|
¥|6
|
23|6
|
20|6
|
0|6
|
(k=2)è
|
|
1
|
2
|
3
|
4
|
5
|
6
|
1
|
0|1
|
15|1
|
5|1
|
20|1
|
25|2
|
¥|1
|
2
|
1|2
|
0|2
|
6|1
|
17|2
|
10|2
|
¥|2
|
3
|
¥|3
|
¥|3
|
0|3
|
2|3
|
¥|3
|
50|3
|
4
|
2|2
|
1|4
|
7|2
|
0|4
|
11|2
|
70|4
|
5
|
20|5
|
30|5
|
25|1
|
10|5
|
0|5
|
10|5
|
6
|
19|2
|
18|6
|
24|2
|
23|6
|
20|6
|
0|6
|
(k=3)è
|
|
1
|
2
|
3
|
4
|
5
|
6
|
1
|
0|1
|
15|1
|
5|1
|
7|3
|
25|2
|
55|3
|
2
|
1|2
|
0|2
|
6|1
|
8|3
|
10|2
|
56|3
|
3
|
¥|3
|
¥|3
|
0|3
|
2|3
|
¥|3
|
50|3
|
4
|
2|2
|
1|4
|
7|2
|
0|4
|
11|2
|
57|3
|
5
|
20|5
|
30|5
|
25|1
|
10|5
|
0|5
|
10|5
|
6
|
19|2
|
18|6
|
24|2
|
23|6
|
20|6
|
0|6
|
(k=4)è
|
|
1
|
2
|
3
|
4
|
5
|
6
|
1
|
0|1
|
8|4
|
5|1
|
7|3
|
18|4
|
55|3
|
2
|
1|2
|
0|2
|
6|1
|
8|3
|
10|2
|
56|3
|
3
|
4|4
|
3|4
|
0|3
|
2|3
|
13|4
|
50|3
|
4
|
2|2
|
1|4
|
7|2
|
0|4
|
11|2
|
57|3
|
5
|
12|4
|
11|4
|
17|4
|
10|5
|
0|5
|
10|5
|
6
|
19|2
|
18|6
|
24|2
|
23|6
|
20|6
|
0|6
|
(k=5)è
|
|
1
|
2
|
3
|
4
|
5
|
6
|
1
|
0|1
|
8|4
|
5|1
|
7|3
|
18|4
|
28|5
|
2
|
1|2
|
0|2
|
6|1
|
8|3
|
10|2
|
20|5
|
3
|
4|4
|
3|4
|
0|3
|
2|3
|
13|4
|
23|5
|
4
|
2|2
|
1|4
|
7|2
|
0|4
|
11|2
|
21|5
|
5
|
12|4
|
11|4
|
17|4
|
10|5
|
0|5
|
10|5
|
6
|
19|2
|
18|6
|
24|2
|
23|6
|
20|6
|
0|6
|
(k=6)è
|
|
1
|
2
|
3
|
4
|
5
|
6
|
1
|
0|1
|
8|4
|
5|1
|
7|3
|
18|4
|
28|5
|
2
|
1|2
|
0|2
|
6|1
|
8|3
|
10|2
|
20|5
|
3
|
4|4
|
3|4
|
0|3
|
2|3
|
13|4
|
23|5
|
4
|
2|2
|
1|4
|
7|2
|
0|4
|
11|2
|
21|5
|
5
|
12|4
|
11|4
|
17|4
|
10|5
|
0|5
|
10|5
|
6
|
19|2
|
18|6
|
24|2
|
23|6
|
20|6
|
0|6
|
(1, 2), (1, 3), (3, 4), (4, 2)
KL: d[1][2]=8: 2ß4ß3ß1
d[1][3]=5: 3ß1
d[3][4]=2: 4ß3
d[4][2]=1: 2ß4
Câu hỏi 25b Cho
đơn đồ thị G = <V, E> gồm 6 đỉnh được biểu diễn dưới dạng ma trận trọng
số như sau:
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
0
|
1
|
15
|
¥
|
¥ss
|
20
|
2
|
1
|
0
|
¥
|
¥
|
5
|
30
|
3
|
15
|
¥
|
0
|
1
|
¥
|
7
|
4
|
¥
|
¥
|
1
|
0
|
20s
|
20
|
5
|
¥
|
5
|
¥
|
20
|
0
|
5
|
6
|
20
|
30
|
20
|
7
|
5
|
0
|
Hãy thực hiện:
a) Trình
bày thuật toán Floyd tìm đường đi ngắn nhất giữa các cặp đỉnh trong đồ thị?
b) Áp
dụng thuật toán Floyd, tìm đường đi ngắn nhất giữa các cặp đỉnh (1, 2), (1, 6),
(2, 5), (5, 6) của đồ thị G đã cho, chỉ rõ kết quả tại mỗi bước thực hiện theo
thuật toán?
Giải:
a,
Thuật toán Floyd:
d[i][j] là độ dài đường đi từ i đến j và pr[i][j] là đỉnh trước
j trên đường đi từ i đến j.
-Khởi tạo: d[i][j]=a[i][j]; pr[i][j]=i;
-Với mọi k thuộc G, i thuộc G, j thuộc G sao cho(d[i][j]>d[i][k]+d[k][j])
thì thay thế:
pr[i][j]=k;
d[i][j]= d[i][k]+d[k][j];
-Xuất d[i][j] và pr[i][j]
b,
Lập bảng:
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
0|1
|
1|1
|
15|1
|
¥|1
|
¥|1
|
20|1
|
2
|
1|2
|
0|2
|
¥|2
|
¥|2
|
5|2
|
30|2
|
3
|
15|3
|
¥|3
|
0|3
|
1|3
|
¥|3
|
7|3
|
4
|
¥|4
|
¥|4
|
1|4
|
0|4
|
20|4
|
20|4
|
5
|
¥|5
|
5|5
|
¥|5
|
20|5
|
0|5
|
5|5
|
6
|
20|6
|
30|6
|
20|6
|
7|6
|
5|6
|
0|6
|
+, k=1
à
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
0|1
|
1|1
|
15|1
|
¥|1
|
¥|1
|
20|1
|
2
|
1|2
|
0|2
|
16|1
|
¥|2
|
5|2
|
21|1
|
3
|
15|3
|
16|1
|
0|3
|
1|3
|
¥|3
|
7|3
|
4
|
¥|4
|
¥|4
|
1|4
|
0|4
|
20|4
|
20|4
|
5
|
¥|5
|
5|5
|
¥|5
|
20|5
|
0|5
|
5|5
|
6
|
20|6
|
21|1
|
20|6
|
7|6
|
5|6
|
0|6
|
+,k=2
à
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
0|1
|
1|1
|
15|1
|
¥|1
|
6|2
|
20|1
|
2
|
1|2
|
0|2
|
16|1
|
¥|2
|
5|2
|
21|1
|
3
|
15|3
|
16|1
|
0|3
|
1|3
|
21|2
|
7|3
|
4
|
¥|4
|
¥|4
|
1|4
|
0|4
|
20|4
|
20|4
|
5
|
6|2
|
5|5
|
21|2
|
20|5
|
0|5
|
5|5
|
6
|
20|6
|
21|1
|
20|6
|
7|6
|
5|6
|
0|6
|
+,k=3
à
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
0|1
|
1|1
|
15|1
|
16|3
|
6|2
|
20|1
|
2
|
1|2
|
0|2
|
16|1
|
17|3
|
5|2
|
21|1
|
3
|
15|3
|
16|1
|
0|3
|
1|3
|
21|2
|
7|3
|
4
|
16|3
|
17|3
|
1|4
|
0|4
|
20|4
|
8|3
|
5
|
6|2
|
5|5
|
21|2
|
20|5
|
0|5
|
5|5
|
6
|
20|6
|
21|1
|
20|6
|
7|6
|
5|6
|
0|6
|
+,k=4
à
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
0|1
|
1|1
|
15|1
|
16|3
|
6|2
|
20|1
|
2
|
1|2
|
0|2
|
16|1
|
17|3
|
5|2
|
21|1
|
3
|
15|3
|
16|1
|
0|3
|
1|3
|
21|2
|
7|3
|
4
|
16|3
|
17|3
|
1|4
|
0|4
|
20|4
|
8|3
|
5
|
6|2
|
5|5
|
21|2
|
20|5
|
0|5
|
5|5
|
6
|
20|6
|
21|1
|
8|4
|
7|6
|
5|6
|
0|6
|
+,k=5
à
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
0|1
|
1|1
|
15|1
|
16|3
|
6|2
|
11|5
|
2
|
1|2
|
0|2
|
16|1
|
17|3
|
5|2
|
10|5
|
3
|
15|3
|
16|1
|
0|3
|
1|3
|
21|2
|
7|3
|
4
|
16|3
|
17|3
|
1|4
|
0|4
|
20|4
|
8|3
|
5
|
6|2
|
5|5
|
21|2
|
20|5
|
0|5
|
5|5
|
6
|
11|5
|
10|5
|
8|4
|
7|6
|
5|6
|
0|6
|
+,k=6
à
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
0|1
|
1|1
|
15|1
|
16|3
|
6|2
|
11|5
|
2
|
1|2
|
0|2
|
16|1
|
17|3
|
5|2
|
10|5
|
3
|
15|3
|
16|1
|
0|3
|
1|3
|
12|6
|
7|3
|
4
|
16|3
|
17|3
|
1|4
|
0|4
|
13|6
|
8|3
|
5
|
6|2
|
5|5
|
13|6
|
12|6
|
0|5
|
5|5
|
6
|
11|5
|
10|5
|
8|4
|
7|6
|
5|6
|
0|6
|
KL:
Đường đi ngắn nhất giữa các cặp đỉnh:
d[1][2]=1: 1à2
d[1][6]=11: 1à2à5à6
d[2][5]=5: 2à5
d[5][6]=5: 5à6
Câu hỏi 26 Cho đơn đồ thị vô hướng G = <V, E> gồm 10
đỉnh được biểu diễn dưới dạng ma trận trọng số như sau
Hãy thực hiện:
a) Trình
bày thuật toán Kruskal tìm cây khung nhỏ nhất trên đồ thị vô hướng, liên thông,
có trọng số?
b) Áp
dụng thuật toán Kruskal, tìm cây khung nhỏ nhất của đồ thị G đã cho, chỉ rõ kết
quả tại mỗi bước thực hiện theo thuật toán?
Giải:
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â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}//Loại cạnh e ra khỏi đồ thị
If(T ∪ {e} không
tạo nên chu trình) then{
d(h)=d(h)+d(e);
}
Endif;
}
Endwhile;
Buoc 4: Tra lai ket qua
If(|T|<n-1) then (Đồ thị
không liên thông)
Else return (T,d(H))
b,
n=10
Sắp xếp thứ tự các cạnh theo thứ tự tăng dần của trọng số:
(1,3)<=(1,4)<=(2,6)<=(3,8)<=(3,9)<=(4,5)<=(5,9)<=(6,8)<=(6,9)<=(1,5)<=(2,3)<=(5,10)<=(8,10)<=(5,6)<=(5,8)<=(6,7)<=(1,2)<=(1,9)<=(5,7)<=(7,8)<=(8,9)<=(9,10)<=(1,8)<=(2,7)<=(6,10)<=(7,9)<=(2,9)<=(3,6)<=(3,7)<=(4,8)<=(1,10)<=(3,4)<=(4,6)<=(1,6)<=(2,5)<=(3,10)
|
Cạnh ei
|
T∪ei chứa chu trình
|
T
|
WT
|
k
|
|
(1,3)
|
No
|
(1,3)
|
1
|
1
|
|
(1,4)
|
No
|
(1,4)
|
2
|
2
|
|
(2,6)
|
No
|
(2,6)
|
3
|
3
|
|
(3,8)
|
No
|
(3,8)
|
4
|
4
|
|
(3,9)
|
No
|
(3,9)
|
5
|
5
|
|
(4,5)
|
No
|
(4,5)
|
6
|
6
|
|
(5,9)
|
Yes
|
------
|
------
|
------
|
|
(6,8)
|
No
|
(6,8)
|
7
|
7
|
|
(6,9)
|
Yes
|
------
|
-----
|
--------
|
|
(1,5)
|
Yes
|
----------
|
--------
|
-------------
|
|
(2,3)
|
Yes
|
----------
|
----------
|
----------
|
|
(5,10)
|
No
|
(5,10)
|
9
|
8
|
|
(8,10)
|
Yes
|
----------
|
----------
|
----------
|
|
(5,6)
|
Yes
|
----------
|
----------
|
----------
|
|
(5,8)
|
Yes
|
----------
|
----------
|
----------
|
|
(6,7)
|
No
|
(6,7)
|
12
|
9
|
KL: WTmin=12
T={(1,3);(1,4);(2,6);(3,8);(3,9);(4,5);(6,8);(5,10),(6,7)}
Câu hỏi 27
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
0
|
1
|
0
|
4
|
1
|
1
|
2
|
9
|
¥
|
5
|
4
|
7
|
2
|
4
|
0
|
2
|
¥
|
9
|
1
|
5
|
¥
|
6
|
¥
|
3
|
1
|
2
|
0
|
7
|
¥
|
6
|
6
|
1
|
1
|
9
|
4
|
1
|
¥
|
7
|
0
|
1
|
7
|
¥
|
6
|
¥
|
¥
|
5
|
2
|
9
|
¥
|
1
|
0
|
3
|
4
|
3
|
1
|
2
|
6
|
9
|
1
|
6
|
7
|
3
|
0
|
3
|
1
|
1
|
5
|
7
|
¥
|
5
|
6
|
¥
|
4
|
3
|
0
|
4
|
5
|
¥
|
8
|
5
|
¥
|
1
|
6
|
3
|
1
|
4
|
0
|
4
|
2
|
9
|
4
|
6
|
1
|
¥
|
1
|
1
|
5
|
4
|
0
|
4
|
0
|
7
|
¥
|
9
|
¥
|
2
|
5
|
¥
|
2
|
4
|
0
|
Hãy thực hiện:
a) Trình
bày thuật toán Prim tìm cây khung nhỏ nhất bắt đầu từ đỉnh s = 1 trên đồ thị vô hướng,
liên thông, có trọng số?
b) Áp
dụng thuật toán Prim tìm cây khung nhỏ nhất của đồ thị G đã cho, chỉ rõ kết quả
tại mỗi bước thực hiện theo thuật toán?
n=10,s=1;
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
|
0|0
|
4|1
|
1|1
|
1|1
|
2|1
|
9|1
|
¥|1
|
5|1
|
4|1
|
7|1
|
2
|
|
2|3
|
1|1
|
1|1
|
2|1
|
6|3
|
6|3
|
1|3
|
1|3
|
7|1
|
3
|
|
2|3
|
|
1|1
|
1|4
|
6|3
|
6|3
|
1|3
|
1|3
|
7|1
|
4
|
|
2|3
|
|
|
1|4
|
3|5
|
4|5
|
1|3
|
1|3
|
2|5
|
5
|
|
2|3
|
|
|
|
1|8
|
4|5
|
1|3
|
1|3
|
2|5
|
6
|
|
1|6
|
|
|
|
1|8
|
3|6
|
|
1|3
|
2|5
|
7
|
|
1|6
|
|
|
|
|
3|6
|
|
1|3
|
2|5
|
8
|
|
|
|
|
|
|
3|6
|
|
1|3
|
2|5
|
9
|
|
|
|
|
|
|
3|6
|
|
|
2|5
|
10
|
|
|
|
|
|
|
3|6
|
|
|
|
èKL:
T={(2,6),(1,3),(1,4),(4,5),(6,8),(6,7),(3,8),(3,9),(5,10)}
WT=1+1+1+1+1+3+1+1+2=12
Câu hỏi 28
Cho đơn đồ thị vô hướng G = <V, E> gồm 10 đỉnh được biểu diễn dưới
dạng ma trận trọng số như sau
Hãy thực hiện:
a) Trình
bày thuật toán Kruskal tìm cây khung nhỏ nhất trên đồ thị vô hướng, liên thông,
có trọng số?
b) Áp
dụng thuật toán Kruskal, tìm cây khung nhỏ nhất của đồ thị G đã cho, chỉ rõ kết
quả tại mỗi bước thực hiện theo thuật toán?
Giải:
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â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}//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}
d(h)=d(h)+d(e);
}
Endif;
}
Endwhile;
Buoc 3: Tra lai ket qua
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ố:
(5,9)<=(6,8)<=(6,9)<=(1,5)<=(2,3)<=(5,10)<=(8,10)<=(5,6)<=(5,8)<=(6,7)<=(1,2)<=(1,9)<=(3,4)<=(5,7)<=(7,8)<=(8,9)<=(9,10)<=(1,8)<=(2,7)<=(6,10)<=(7,9)<=(2,9)<=(3,6)<=(3,7)<=(4,8)<=(8,4)<=(1,10)<=(2,6)<=(4,5)<=(4,6)<=(1,3)<=(1,4)<=(1,6)<=(2,5)<=(3,8)<=(3,9)<=(3,10)
Lập bảng:
Cạnh ei
|
T∪{ei} chứa chu trình
|
T
|
WT
|
k
|
(5,9)
|
No
|
(5,9)
|
1
|
1
|
(6,8)
|
No
|
(6,8)
|
2
|
2
|
(6,9)
|
No
|
(6,9)
|
3
|
3
|
(1,5)
|
No
|
(1,5)
|
5
|
4
|
(2,3)
|
No
|
(2,3)
|
7
|
5
|
(5,10)
|
No
|
(5,10)
|
9
|
6
|
(8,10)
|
Yes
|
------
|
---------
|
---------
|
(5,6)
|
Yes
|
------
|
------------
|
-----------
|
(5,8)
|
Yes
|
------
|
---------
|
-----------
|
(6,7)
|
No
|
(6,7)
|
12
|
7
|
(1,2)
|
No
|
(1,2)
|
16
|
8
|
(1,9)
|
Yes
|
--------
|
-----------
|
------------
|
(3,4)
|
No
|
(3,4)
|
20
|
9
|
KL: WTmin=20
T={(5,9),(6,8),(6,9),(1,5),(2,3),(5,10),(6,7),(1,2),(3,4)}.
*Chú ý: Gợi ý tại mỗi đề chỉ mang tính chất tham khảo rất mong sự góp ý của mọi người để có lời giải hoàn thiện và chính xác nhất.
Nếu thấy tài liệu có ích hi vọng mn ủng hộ blog 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 : https://www.facebook.com/TaiLieuBlog/
💰Ủng hộ blog: https://unghotoi.com/1546792457ngwn4
bài 28 thuật toán Kruskal ấy doạn Yes ấy giải thích t vs đc k,..
Trả lờiXóaKhi kết nạp cạnh ấy vào cây khung T tạo nên chu trình thì đánh dấu là Yes và xóa cạnh đó nhé b
Xóa