Giáo trình Toàn rời rạc 1 - Bài tập chương 9: Đồ thị (Phần 2)
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 cần giải
Câu 1.
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
c
e
c
e
b
b
a
a
d
d
Câu 2.
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
Câu 3.
Hãy xác định vertex cut và edge cut trong đồ thị G sau
Giáo trình Toán Rời Rạc 1
Trang 1/13
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
y
z
a
e
x
w
b
c
d
Câu 4.
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.
Câu 5.
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ẽ xác định.
c
b
c
b
d
e
k
i
l
i
e
f
d
g
a
h
j
a
g
h
f
Câu 6.
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
Câu 7.
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ị như sau.
6
(G3)
B
E
4
4
2
2
5
A
D
F
1
6
7
C
Giáo trình Toán Rời Rạc 1
Trang 2/13
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 8.
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ị như sau.
5
b
d
4
6
8
a
z
1
2
2
3
10
c
e
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ị như sau.
7
b
d
3
2
1
1 2
a
z
1
3
9
c
e
5
3 Bài tập làm thêm
Câu 10.
Hãy dùng giải thuật Dijsktra để tìm đường đi ngắn nhất của đỉnh S đến một đỉnh bất kỳ khác trong
đồ thị như sau.
(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 11.
Giáo trình Toán Rời Rạc 1
Trang 3/13
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
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ị như sau.
5
(G5)
B
D
E
F
7
2
6
2
3
4
4
A
C
G
3
H
6
2
1
4
Câu 12.
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.
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
Câu 13.
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.
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
Câu 14.
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.
Giáo trình Toán Rời Rạc 1
Trang 4/13
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
a
b
c
b
c
f
f
d
e
e
d
Câu 15.
Vẽ đồ thị đối ngẫu của các bản đồ sau, 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.
Câu 16.
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 17.
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 18.
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 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 19.
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
Giáo trình Toán Rời Rạc 1
Trang 5/13
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.
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 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ị G6 như bên dưới.
4
(G6)
B
C
E
3
2
-3
2
A
2
F
1
5
7
6
D
Câu 22.
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 23.
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 24.
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.
Câu 25.
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?
Giáo trình Toán Rời Rạc 1
Trang 6/13
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) 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 26.
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 27.
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 28.
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.
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
Câu 29.
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
Giáo trình Toán Rời Rạc 1
Trang 7/13
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 30.
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ì 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 31.
Số màu của Wn là bao nhiêu?
4 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 8/13
8 trang
26/04/2022
3560
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ị (Phần 2)", để 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_phan_2.pdf
