Giáo trình Toàn rời rạc 1 - Bài tập chương 9: Đồ thị
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Bài tập chương 9
Đồ thị (phần hai)
1 Dẫn nhập
Trong bài tập dưới đây, chúng ta sẽ làm quen với các bài toán, giải thuật và ứng dụng của
lý thuyết đồ thị. Sinh viên cần xem lại lý thuyết của Chương 9 trước khi thực hiện những
bài tập này.
2 Bài tập mẫu
Đồ thị G1 như hình bên dưới đây.
(G1)
11
5
7
A
B
C
D
E
F
10
6
2
3
4
8
2
4
S
10
8
H
6
14
G
Câu 1.
Tìm đường đi ngắn nhất xuất phát từ S đến tất cả các đỉnh còn lại bằng giải thuật
Dijkstra.
Lời giải.
2
Câu 2.
Tìm đường đi ngắn nhất xuất phát từ S đến tất cả các đỉnh còn lại bằng giải thuật
Bellman-Ford.
Lời giải.
2
Giáo trình Toán Rời Rạc 1
Trang 1/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Câu 3.
Tìm đường đi ngắn nhất xuất phát từ S đến tất cả các đỉnh còn lại bằng giải thuật
Floyd-Warshall.
Lời giải.
2
3 Bài tập cần giải
Câu 4.
Xác định xem những đồ thị dưới đây có liên thông mạnh hay không, nếu không, thì nó có
liên thông yếu hay không.
b
a
f
c
a
c
b
d
e
f
d
e
Lời giải.
a) Liên thông yếu
b) Liên thông mạnh
2
Câu 5.
Chứng minh rằng các đồ thị sau không có đỉnh cắt.
a) Cn với n ≥ 3
b) Wn với n ≥ 3
c) Km,n với m ≥ 2 và n ≥ 2
d) Qn với n ≥ 2
Lời giải.
Giáo trình Toán Rời Rạc 1
Trang 2/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
a) Cn với n ≥ 3: Ta có các cạnh sau: {x0, x1},{x1, x2},...,{xn−2, xn−1},{xn−1, x0}.
Giả sử ta bỏ đỉnh i (0 ≤ i ≤ n-1). Đồ thị sẽ còn các cạnh như sau: {x0, x1},{x1, x2},...,{xi−2, xi−1},{xi+1, xi+
Việc bỏ đi đỉnh i không làm tăng thành phần liên thông của đồ thị vì vẫn tồn tại đường
đi từ các điểm còn lại. Vậy Cn không có đỉnh cắt.
(Hoặc đồ thị trên có chu trình Haminton. Việc loại 1 đỉnh sẽ vẫn tồn tại đường đi
Haminton).
b) Wn với n ≥ 3: Là đồ thị thu được từ Cn, vì vậy đối với các điểm cũ trên Cn khi bỏ đi
vẫn đảm bảo liên thông. Nếu bỏ điểm trung tâm thì nó trở lại thành Cn.
c) Km,n với m ≥ 2 và n ≥ 2: Ta chứng mình bỏ 1 đỉnh phía trái đồ thị vẫn liên thông, từ
đó phía bên phải cũng tương tự. Dùng phương pháp quy nạp:
Với K2,n (n ≥ 2) đồ khi bỏ đi 1 đỉnh phía trái đồ thị có dạng hình sao với 1 điểm nối
với các đỉnh phía phải (liên thông)
Giả sử đúng với m ≥ 2, ta cần chứng minh đúng với m = m + 1.
Thật vậy với m = m + 1, ta có đồ thị Km+1,n. Lúc này nếu bỏ 1 điểm bên trái đồ thị
trở về là Km,n (liên thông)
Vậy Km,n không có đỉnh cắt.
d) Qn với n ≥ 2: Luôn chứa chu trình Haminton. Vì vậy khi bỏ 1 điểm khỏi đồ thị vẫn tồn
tại đường đi Haminton, liên thông. Vậy Qn không có đỉnh cắt.
2
Câu 6.
Hãy vẽ một đồ thị G có κ(G) = 1, λ(G) = 2, và bậc nhỏ nhất của các đỉnh là 3.
f
g
c
b
e
a
h
i
d
Lời giải.
Câu 7.
2
Xác định xem đồ thị sau có chu trình Euler hay không. Nếu có, hãy xác định. Nếu không,
xác định xem nó có đường đi Euler hay không. Nếu có, vẽ đường đi Euler.
Giáo trình Toán Rời Rạc 1
Trang 3/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
c
b
c
b
d
e
k
i
l
i
e
f
d
g
a
h
j
a
g
h
f
Lời giải.
a) Không có chu trình Euler. Có đường đi Euler
b) Có chu trình Euler
2
Câu 8.
Xác định xem đồ thị sau có chu trình Hamilton hay không. Nếu có, hãy xác định nó. Nếu
không, hãy đưa lý luận tại sao không có.
g
a
d
a
b
f
c
e
e
c
b
d
f
Lời giải.
a) Không có chu trình Hamilton vì liên thông cạnh λ(G) = 1
b) Không có chu trình Hamilton vì có 3 đỉnh deg(v)=1
2
Câu 9.
Hãy dùng giải thuật Dijsktra để tìm đường đi ngắn nhất của đỉnh A đến một đỉnh bất kỳ
khác trong đồ thị G3 như sau.
Lời giải. Dựa theo giải thuật Dijkstra, chúng ta cần xây dựng bảng sau.
Giáo trình Toán Rời Rạc 1
Trang 4/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
6
(G3)
B
E
4
4
2
2
5
A
D
F
1
6
7
C
i
A
0
B
C
1
1
D
E
F
π(0)
π(1)
π(2)
π(3)
π(4)
π(5)
4
4
4
+∞ +∞ +∞
7
6
6
+∞
10
8
8
8
8
8
8
8
Từ bảng trên, ta có thể xác đinh đường đi ngắn nhất từ A đến các đỉnh còn lại.
• A → B
• A → C
• A → B → D
• A → B → D → E
• A → C → F
2
Câu 10.
Hãy dùng giải thuật Bellman-Ford để tìm đường đi ngắn nhất của đỉnh A đến một đỉnh
bất kỳ khác trong đồ thị G4 bên dưới.
Lời giải. Dựa theo giải thuật Bellman-Ford, chúng ta xây dựng bảng sau.
Step
0
A
0
0
0
0
0
0
B
C
D
E
F
G
H
I
J
+∞ +∞ +∞ +∞ +∞ +∞ +∞ +∞ +∞
1
2
3
4
3
3
3
3
3
5
5
5
5
5
8
7
7
7
7
+∞ +∞ +∞ +∞ +∞ +∞
9
9
9
9
12 +∞ +∞ +∞ +∞
12
12
12
16
16
16
22
22
22
19 +∞
19
19
21
21
5
Stop since Step 5 = Step 4
Giáo trình Toán Rời Rạc 1
Trang 5/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
6
7
(G4)
B
E
G
3
2
15
3
3
5
4
3
A
C
H
J
10
7
8
2
4
2
12
4
D
F
I
Từ bảng trên, ta có thể xác đinh đường đi ngắn nhất từ A đến các đỉnh còn lại.
• A → B
• A → C
• A → C → D
• A → B → E
• A → C → D → F
• A → B → E → G
• A → C → D → F → H
• A → C → D → F → H → I
• A → C → D → F → H → I → J
2
Câu 11.
Hãy dùng giải thuật Floyd-Warshall để tìm đường đi ngắn nhất của một đỉnh bất kỳ đến
một đỉnh khác bất kỳ trong đồ thị G8 như bên dưới.
Lời giải.
0
3
8
0
∞
2
0
6
1
∞ ∞
7
∞
∞ ∞ ∞ ∞
∞ ∞
∞
2
4
0
5
∞
9
∞ ∞
∞ ∞ ∞
0
1
∞
L(0)
=
∞ ∞ ∞ ∞
∞
∞
0
∞
1
∞ ∞
4
∞ ∞
0
3
4
0
5
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
7
Giáo trình Toán Rời Rạc 1
Trang 6/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
2
(G8)
B
C
E
H
3
4
3
8
1
2
1
5
9
6
4
4
A
D
F
7
7
1
5
G
0
3
8
0
∞
2
0
6
∞ ∞
7
∞
1
∞
0
∞ ∞ ∞ ∞
∞ ∞
2
4
0
5
∞
9
∞ ∞
∞ ∞ ∞
1
∞
1
3
4
0
L(1)
L(2)
L(3)
=
∞ ∞ ∞ ∞
∞
∞
0
∞
∞ ∞
4
∞ ∞
0
5
13 ∞ 11 ∞ ∞
∞ ∞ ∞ ∞ ∞
7
0
3
8
0
10
2
0
6
1
∞ ∞
7
∞
∞ ∞ ∞ ∞
∞ ∞
∞
2
4
0
5
∞
9
∞ ∞
∞ ∞ ∞
0
1
∞
=
∞ ∞ ∞ ∞
∞
∞
0
∞
1
∞ ∞
4
∞ ∞
0
3
4
0
5
13 15 11 ∞ ∞
∞ ∞ ∞ ∞ ∞
7
0
3
8
0
10
2
0
6
1
12 15
7
∞
4
2
4
0
6
7
5
∞ ∞
∞ ∞
∞ ∞
∞
∞ ∞ ∞
0
∞
1
∞
=
∞ ∞ ∞ ∞
9
∞
∞
0
∞
1
∞ ∞
4
∞
0
3
4
0
5
13 15 11 17 20
∞ ∞ ∞ ∞ ∞
7
Giáo trình Toán Rời Rạc 1
Trang 7/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
0
3
8
0
10
2
0
6
1
10 15
7
2
∞
∞
4
2
4
0
6
7
5
∞ ∞
∞
∞ ∞
∞ ∞ ∞
0
∞
1
∞
1
3
4
0
L(4)
L(5)
L(6)
L(7)
=
=
=
=
∞ ∞ ∞ ∞
9
∞
∞
0
∞
∞ ∞
4
∞
0
5
13 15 11 15 20
∞ ∞ ∞ ∞ ∞
7
0
3
8
0
10
2
0
6
1
10 15
7
2
11
5
3
5
1
3
4
0
4
2
4
0
6
7
5
13
9
∞ ∞
∞
∞
∞ ∞ ∞
0
1
∞ ∞ ∞ ∞
∞
∞
0
∞
∞ ∞
4
∞
0
5
13 15 11 15 20
7
∞ ∞ ∞ ∞ ∞
0
3
8
0
10
2
0
6
1
10 15
7
2
11
5
3
5
1
3
4
0
4
2
4
0
6
7
5
13
9
∞ ∞
∞
∞
∞ ∞ ∞
0
1
∞ ∞ 13 ∞
∞
∞
0
∞
∞ ∞
4
∞
0
5
13 15 11 15 20
7
∞ ∞ 11 ∞ 13
0
3
8
0
10
2
0
6
1
10 15
7
2
11
5
3
5
1
3
4
0
4
2
4
0
6
7
5
13
9
∞ ∞
∞
∞
6
14 16
0
1
∞ ∞ 13 ∞
∞
∞
0
∞
∞ ∞
4
∞
0
5
13 15 11 15 20
∞ ∞ 11 ∞ 13
7
Giáo trình Toán Rời Rạc 1
Trang 8/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
0
3
8
0
10
2
0
6
1
10 15
7
2
11
5
3
5
1
3
4
0
4
2
4
0
6
7
5
12
8
∞ ∞
∞
∞
6
14 16
0
1
L(8)
=
∞ ∞ 12 ∞
∞
∞
0
∞
∞ ∞
4
∞
0
5
13 15 11 15 11
∞ ∞ 11 ∞ 13
7
2
Câu 12.
Xác định xem các đồ thị sau có phẳng hay không. Nếu có, hãy vẽ lại đồ thị sao cho không
có cạnh nào giao nhau.
a
a
b
c
b
c
f
f
d
e
e
d
Lời giải.
a) Không, vì nó là K3,3
b) Phẳng:
d
f
a
b
c
e
2
Câu 13.
Vẽ đồ thị đối ngẫu của các bản đồ sa, sau đó tìm số màu cần thiết để tô bản đồ sao cho
các vùng kế nhau không cùng màu với nhau.
Giáo trình Toán Rời Rạc 1
Trang 9/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
E
F
E
B
C
D
A
B
A
C
D
Lời giải.
2
4 Bài tập làm thêm
Câu 14.
Cho đồ thị G = (V, E) là một đồ thị có hướng. Đỉnh w ∈ V được gọi là đến được từ đỉnh
v ∈ V nếu có một đường đi có hướng từ v sang w. Hai đỉnh v và w được gọi là đến được
nhau nếu tồn tại đường đi có hướng từ v đến w và đường đi có hướng từ w đến v trong G.
Chứng minh rằng nếu G = (V, E) là đồ thị có hướng và u, v, và w là các đỉnh thuộc V
trong đó u và v là đến được nhau và v và w là đến được nhau, thì u và w cũng đến được
nhau.
Câu 15.
Chứng minh rằng một đồ thị liên thông có n đỉnh phải có ít nhất n − 1 cạnh.
Câu 16.
a) Bạn được trao một cái bình 3 lít và một cái bình 5 lít. Bạn có thể làm một trong ba
hành động, đổ nước đầy mỗi bình, đổ nước hoàn toàn ra khỏi mỗi bình, và đổ nước qua
lại mỗi bình. Hãy sử dụng một đường đi trong đồ thị có hướng để cho thấy bạn thể làm
cho một bình có chứa đúng 1 lít nước.
b) Có hai cặp vợ chồng muốn qua sông. Họ chỉ có một chiếc thuyền duy nhất có thể chở
một lần một hoặc hai người từ bờ này sang bờ bên kia. Vấn đề ở chỗ hai ông chồng
Giáo trình Toán Rời Rạc 1
Trang 10/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
có tính ghen tuông tới múc không muốn để vợ mình lại với người đàn ông kia, dù trên
thuyền hay trên bờ. Làm cách nào để bốn này qua được bờ bên kia?
Câu 17.
Hãy xác định xem các đồ thị vô hướng sau có chứa đường đi/chu trình Euler và Hamilton
không ? Nếu có, hãy vẽ ra.
(G10)
11
5
7
A
B
C
D
E
F
10
6
2
3
4
8
2
4
S
10
8
H
6
14
G
Câu 18.
Một cuộc họp có ít nhất ba đại biểu đến dự. Mỗi người quen ít nhất hai đại biểu khác.Hãy
tìm cách để sắp xếp chỗ ngồi của các đại biểu chung quanh một bàn tròn, sao cho mỗi
người ngồi giữa hai người mà đại biểu đó quen.
Câu 19.
Hãy dùng giải thuật Dijsktra và giải thuật Ford để tìm đường đi ngắn nhất của đỉnh A
đến một đỉnh bất kỳ khác trong đồ thị G5 như bên dưới.
5
(G5)
B
D
E
F
7
2
6
2
3
4
4
A
C
G
3
H
6
2
1
4
Giáo trình Toán Rời Rạc 1
Trang 11/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Câu 20.
Hãy dùng giải thuật Bellman-Ford để tìm đường đi ngắn nhất của đỉnh A đến một đỉnh
bất kỳ khác trong đồ thị G6 như bên dưới.
4
(G6)
B
C
3
2
-3
2
A
2
F
1
5
7
6
D
E
Câu 21.
Hãy dùng giải thuật Bellman-Ford để tìm đường đi ngắn nhất của đỉnh A đến một đỉnh
bất kỳ khác trong đồ thị G7 như bên dưới.
8
(G7)
B
C
E
H
7
1
2
1
-3
5
-6
3
5
2
8
A
D
F
9
-4
10
G
Câu 22.
Liệu có thể dùng giải thuật Dijsktra để giải bài toán tìm đường đi ngắn nhất xuất phát từ
một đỉnh bất kỳ đến một đỉnh bất kỳ khác không ? Nếu có hãy minh họa bằng áp dụng
vào các đồ thị từ G5 đến G8.
Câu 23.
Hãy thiết kế một giải thuật để đếm số đường đi ngắn nhất trong một đồ thị cho sẵn.
Giáo trình Toán Rời Rạc 1
Trang 12/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Câu 24.
a) Làm thế nào đếm được số đường đi khác nhau xuất phát từ một đỉnh u và đến một
đỉnh v trong một đồ thị G cho trước?
b) Hãy vẽ một đồ thị và minh họa việc đếm.
c) Liệu có tồn tại giải thuật đếm số đường đi có thể có từ u đến v không?
Câu 25.
Liệu có tồn tại giải thuật xác định một cách nhanh chóng sự tồn tại của chu trình trong
một đồ thị cho trước không? Nếu có hãy viết giải thuật đó.
Câu 26.
Gọi Π∗ là đường đi ngắn nhất trong một đồ thị. Nếu trọng số của tất cả các cạnh đều tăng
lên một giá trị hằng số nào đó thì liệu Π∗ có vẫn là đường đi ngắn nhất trong đồ thị mới
không?
Câu 27.
Tìm đường đi ngắn nhất của một đỉnh bất kỳ đến một đỉnh bất kỳ khác trong đồ thị G9
sau.
Câu 28.
Xác định xem các đồ thị sau có đồng phôi với K3,3 hay không.
c
a
b
d
a
b
c
g
h
e
g
e
f
h
d
f
Câu 29.
Một vườn thú muốn mở một số khu vực trưng bày thú. Tuy nhiên, một vài loài thú sẽ ăn
thịt lẫn nhau nếu có cơ hội. Mô hình đồ thị và phương pháp tô màu sẽ giúp ích được gì
Giáo trình Toán Rời Rạc 1
Trang 13/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
1900
(G9)
Hải Phòng
Cà Mau
1200
200
400
Hồ Chí Minh
1000
Hà Nội
600
500
800
100
Nha Trang
Đà Nẵng
200
500
Vũng Tàu
Giáo trình Toán Rời Rạc 1
Trang 14/15
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
trong việc xác định xem vườn thú cần mở bao nhiêu khu vực trưng bày và cách sắp đặt
các con thú thế nào trong các khu vực này?
Câu 30.
Số màu của Wn là bao nhiêu?
5 Tổng kết
Thông qua các bài tập trong phần này, chúng ta đã làm quen với lý thuyết về đường đi
và chu trình (tham khảo chi tiết lý thuyết trong chương 9). Và các bài tập này cũng đã
giúp chúng ta phần nào hiểu thêm về các ý tưởng, các hướng giải thuật để giải được vài
bài toán thực tế đơn giản chung quanh chúng ta.
Giáo trình Toán Rời Rạc 1
Trang 15/15
15 trang
26/04/2022
6720
Bạn đang xem tài liệu "Giáo trình Toàn rời rạc 1 - Bài tập chương 9: Đồ thị", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_toan_roi_rac_1_bai_tap_chuong_9_do_thi.pdf
