/ / 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)

Edit
Tài liệu blog

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].

b,
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
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 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 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
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
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?
b,
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
1
2
3
4

5
6
7
8
9
0
1
0
4
8
8

2
9
¥
5
4
7
2
4
0
2
¥

9
7
5
¥
6
¥
3
8
2
0
4

¥
6
6
9
9
9
4
8
¥
4
0

7
7
¥
6
¥
¥
5
2
9
¥
7

0
3
4
3
1
2
6
9
7
6
7

3
0
3
1
1
5
7
¥
5
6
¥

4
3
0
4
5
¥
8
5
¥
9
6

3
1
4
0
4
2
9
4
6
9
¥

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 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/
Share on Google Plus

About Kỹ Thuật Xe

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.
    Blogger Comment
    Facebook Comment

0 nhận xét:

Đăng nhận xét

Đăng ký: Đăng Nhận xét ( Atom )