BÀI TẬP LÝ THUYẾT ĐỒ THỊ
Giảng viên: Nguyễn Ngọc Trung
Chương 1. ĐẠI CƯƠNG VỀ ĐỒ THỊ
1. Loại đồ thị nào được dùng để mô hình hệ thống các đường cao tốc giữa các thành phố lớn
trong các trường hợp sau:
a. N
ếu giữa hai thành phố có đường cao tốc thì giữa chúng sẽ được nối bởi một cạnh.
b. M
ỗi cạnh biểu thị cho mỗi đường cao tốc giữa các thành phố.
c. M
ỗi cạnh biểu thị cho mỗi đường cao tốc giữa các thành phố và ngoài ra có thêm khuyên
để biểu diễn cho đường cao tốc bao quanh một thành phố nào đó.
2. Hãy xây dựng đồ thị lấn tổ cho cả 6 loài chim trong đó chim hét cạnh tranh với chim cổ đỏ và
chim gi
ẻ cùi xanh, chim cổ đỏ cũng cạnh tranh với chim nhại, chim nhại cạnh tranh với chim
gi
ẻ cùi và chim bổ hạt cạnh tranh với chim gõ kiến.
3. N
ếu cần phải dùng đồ biểu diễn cho kết quả thắng – thua của các trận đấu bóng chuyền giữa
các đội theo thể thức vòng tròn hai lượt (mỗi đội gặp nhau 2 lần) thì cần phải dùng đồ thị gì?
Đồ thị này sẽ có bao nhiêu cạnh nếu số đội là n đội?
4. Hãy xây d
ựng đồ thị ưu tiên trước sau cho chương trình sau:
a. x := 0;
b. x := x+1;
c. y := 2;
d. z := y;
e. x := x + 2;
f. y := y + z;
g. z := 4;
5. Có th

c. 0, 1, 2, 2, 3
d. 1, 1, 1, 1, 1
e. 3, 4, 3, 4, 4
f. 0, 1, 0, 1, 0
1 2
3
4 5
6
1
2
3
4 5
6
14. Hãy vẽ các đồ thị sau đây:
a. K
4x4
b. C
7
c. W
7
d. K
5
15. Cho đồ thị sau. Hãy cho biết đồ thị này có tất cả bao nhiêu đồ thị con.
16. Đồ thị K
3
có bao nhiêu đồ thị con có ít nhất một đỉnh?
Một đồ thị được gọi là chính quy nếu mọi đỉnh của nó đều có bậc như nhau. Một đồ thị được
gọi là n-chính quy nếu mọi đỉnh của nó đều có bậc n.
17. Với các giá trị nào của n thì đồ thị sau đây là chính quy?
a. K

n
m 
22. Cho các đồ thị sau, hãy xác định đồ thị nào là đồ thị phân đôi:
23. Xét đồ thị sau:
a. Hãy tìm 3 đường đi đơn khác nhau từ đỉnh 1 đến đỉnh 6
b. Hãy tìm 3 chu trình sơ cấp chứa đỉnh 1
c. Cho biết đồ thị này có liên thông mạnh hay liên thông yếu hay không?
24. Cho đồ thị sau. Hãy cho biết có tất cả bao nhiêu đường đi đơn từ đỉnh 1 đến đỉnh 16.
1
2
3
4
5
6
7
1
2
3
4
5
6
25. Hãy tìm số đường đi đơn độ dài n giữa hai đỉnh kề nhau bất kỳ trong đồ thị K
3x3
với:
a. n = 2
b. n = 3
c. n = 4
26. T
ừ kết quả của bài 25, hãy rút ra công thức tổng quát về số đường đi đơn độ dài n giữa hai
đỉnh kề nhau bất kỳ trong đồ thị K

33. Hãy xác định ma trận liên thuộc của các đồ thị trên
34. Hãy xác
định danh sách cạnh của các đồ thị trên
35. Hãy xác
định danh sách kề của các đồ thị trên
36. G
ọi A là ma trận kề của đồ thị bên.
a. Hãy xác
định A
2
b. Hãy cho biết giá trị của A
2
ij
biểu diễn cho cái gì?
c. T
ừ đó, nếu ta tính An thì A
n
ij
sẽ biểu diễn cho cái gì?
37. N
ếu hai đồ thị đẳng cấu với nhau thì ma trận kề của chúng có giống
nhau hay không? T
ại sao?
38.
Cho hai đồ thị có cùng 5 đỉnh. Cơ cấu bậc của chúng cũng giống nhau: đều có 1 đỉnh bậc 3,
3 đỉnh bậc 2 và 1 đỉnh bậc 1. Vậy hai đồ thị có chắc chắn đẳng cấu với nhau hay không. Nếu
có thì ch
ứng minh, nếu không thì cho một ví dụ minh họa.
39. Có t
ất cả bao nhiêu đồ thị có 5 đỉnh và 2 cạnh. Trong số đó có bao nhiêu đồ thị đẳng cấu với

Một đơn đồ thị được gọi là tự bù nếu và chỉ nếu G và
G
là đẳng cấu.
42. Hãy tìm m
ột đồ thị tự bù có 5 đỉnh
43. V
ới số nguyên nào của n thi C
n
là đồ thị tự bù.
44. Ch
ứng minh rằng nếu G là đồ thị tự bù với n đỉnh thì hoặc n chia hết cho 4, hoặc n chia 4 dư
1.
45. Hãy xác
định các đồ thị sau có đẳng cấu hay không
46. Chứng minh răng một đồ thị vô hướng, liên thông có n đỉnh và n-1 cạnh thì sẽ không thể
chứa chu trình nào.
Chương 3. Đ
Ồ
47. Chứng minh rằng trong mộ
t đ
này đến một đỉnh bậc lẻ
khác.
48. Các đồ thị sau đây có phả
i là đ
hay nửa Euler thì phải chỉ
ra chu trình (

49. Các đồ thị trên đây có phả
i là đ
là Hamilton hay nử

i là đ
ồ thị Euler hay nửa Euler hay không? Giả
i thích. N
ra chu trình (
đường đi) Euler tương ứng.i là đ
ồ thị Hamilton hay nử
a Hamilton hay không? Gi
a Hamilton thì ph
ải chỉ ra chu trình (đườ
ng đi) Hamilton tương
ng liên thông
G mà mỗi đỉnh đều có bậc là 20. Chứ
ng minh r
u) nào.
u b
ỏ đi bất kỳ 1 cạnh nào thì đồ thị vẫ
n còn liên thông)
a m và n thì
đồ thị phân đôi đầy đủ K
mxn
là:
ấ
t để có thể vẽ được các hình ở bài 48. Giả
i thích.
i là đ
ồ thị Hamilton hay không? Chứng minh.


Chương 4. ĐỒ THỊ PHẲNG – BÀI TOÁN TÔ MÀU ĐỒ THỊ
58. Có năm ngôi nhà nối với hai thiết bị sinh hoạt: Gas và Điện. Hỏi có cách nối để các dây nối
không c
ắt nhau hay không? Tại sao?
59. Xét m
ột đồ thị liên thông có 8 đỉnh bậc 3. Hỏi biểu diễn phẳng của đồ thị này sẽ chia mặt
ph
ẳng thành mấy miền.
60.
Các đồ thị sau đây có là đồ thị phẳng không? Nếu có hãy vẽ biểu diễn phẳng của nó

61.
Các đồ thị sau đây có là đồ thị phẳng không? Nếu có hãy vẽ biểu diễn phẳng của nó

62. Ch
ứng minh rằng nếu một đơn đồ thị phẳng, liên thông có e cạnh và v đỉnh, trong đó có
(v3), và không có chu trình với độ dài 3, thì e  2v – 4.
63. Xét m
ột đơn đồ thị phân đôi, phẳng, liên thông có e cạnh và v đỉnh (v3). Chứng minh rằng
e  2v – 4.
64. M
ột đồ thị vô hướng, phẳng có e cạnh, v đỉnh và k thành phần liên thông. Hãy tìm biểu thức
quan h
ệ giữa r – số miền trong biểu diễn phẳng của đồ thị – với e, v và k.
65. Hãy xây d
ựng đồ thị đối ngẫu với các bản đồ dưới đây. Từ đó cho biết các bản đồ trên có thể
đượ
c tô bằng tổi thiều bao nhiêu màu sao cho hai vùng giáp nhau phải có màu khác nhau.

66. Hãy tìm s

200
20
100
2
85 125 175 100 160
3
175 125 100 200 250
4
200 175 100 210 220
5
10 100 200 210 100
6
100 160 250 220 100
71. Chứng minh rằng một đơn đồ thị vô hướng là phân đôi nếu và chỉ nếu số màu của nó là 2.
Tô màu cạnh của đồ thị là gán mỗi cạnh của đồ thị bằng một màu sao cho hai cạnh có cùng
chung đỉnh đầu sẽ không được gán cùng màu. Số màu cạnh của một đồ thị là số màu ít nhất
dùng để tô màu các cạnh của đồ thị.
72. Hãy xác
định số màu cạnh của các đồ thị trong bài 66.
73. Hãy
đưa bài toán tô màu cạnh về bài toán tô màu đồ thị (tô màu đỉnh)
Chương 5. CÂY
74. Có bao nhiêu cây không đẳng cấu với n đỉnh nếu
a. n = 3
b. n = 4
75. Cho G là m
ột cây 5-phân đầy đủ có 100 đỉnh trong. Hỏi G có tất cả bao nhiêu đỉnh
76. Cây 3-
phân (tam phân) đầy đủ có 100 đỉnh thì có bao nhiêu lá?
77. Ch

ụng thuật toán Kruskal để tìm cây khung nhỏ nhất của các đồ thị trong bài 86.
Chương 6. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
88. Hãy áp dụng thuật toán Ford-Bellman để tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh
khác trong các đồ thị dưới đây. Hãy vẽ cây đường đi thể hiện cho các đường đi ngắn nhất
đó.

89. Tương tự như bài 88, nhưng sử dụng thuật toán Dijsktra.
90. Hãy áp dụng thuật toán Dijsktra để tìm đường đi ngắn nhất từ a tới z trong đồ thị ở bài 88,
câu b, biết rằng đường đi này phải đi qua đỉnh f.
91. Cho G là một đồ thị có trọng số và u* là một đỉnh của G. Hãy cải tiến thuật toán Dijsktra sao
cho có thể tìm được đường đi ngắn nhất từ đỉnh s đến đỉnh t mà phải đi qua đỉnh u*.
(Chú ý: Không cần viết chi tiết, chỉ cần mô tả ý tưởng)
92. Hãy áp dụng thuật toán Dijsktra để tìm đường đi ngắn nhất từ a tới z trong đồ thị ở bài 88,
câu b, biết rằng đường đi này phải đi qua cạnh (d, f).
(HD: Chọn đường đi ngắn hơn giữa hai đường đi ngắn nhất: a - … - d – f - … z, và
a - … - f – d - … z.)
93. Cho G là một đồ thị có trọng số và (u*, v*) là một cạnh của G. Hãy cải tiến thuật toán
Dijsktra sao cho có thể tìm được đường đi ngắn nhất từ đỉnh s đến đỉnh t mà phải đi qua
cạnh (u*, v*).
(Chú ý: Không cần viết chi tiết, chỉ cần mô tả ý tưởng)
94. Cho sơ đồ các thành phố và chi phí để di chuyển (bằng máy bay) giữa các thành phố như
sau:
Giả sử một công ty du lịch đặt tại NewYork muốn tổ chức các tour du lịch từ NewYork tới
các thành phố khác. Hãy chỉ đường cho công ty này sao cho các tour là ít tốn kém về tiền vé
nhất.
95. Xét đồ thị sau, hãy cho biết ma trận d và p cuối cùng sau khi thực hiện thuật toán Floyd trên
đồ thị này.
3
1 2
3