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ểtồn tại đơn đồ thị có 15 đỉnh, mỗi đỉnh đều có bậc là 5 không?
6. Cho các đồ thịhãy xác định bậc của các đỉnh của các đồ thị đó.
a. b.
7. Hãy vẽmột đơn đồ thị vô hướng có 5 đỉnh. Trong đó có 3 đỉnh rẽnhánh, một đỉnh cô lập. Hỏi
đồ thịnày phải có bao nhiêu cạnh? Đỉnh còn lại phải có bậc mấy?
(Chú ý: có thểcó nhiều đáp án cho câu hỏi này)
8. Cho một đồ thị vô hướng có n đỉnh. Hỏi đồ thịnày có thểcó tối đa bao nhiêu cạnh. Trong
trường hợp sốcạnh là tối đa thì mỗi đỉnh sẽcó bậc là bao nhiêu?
9. Xét một đồ thị vô hướng có n đỉnh và m cạnh. Gọi k là bậc nhỏnhất, K là bậc lớn nhất trong
đồ thị. Chứng minh rằng:
2m
k K
n
10. Cho một đồ thị vô hướng có n đỉnh và 2n cạnh. Chứng minh rằng trong đồ thịnày luôn tồn
tại một đỉnh có bậc không nhỏ hơn 4.
11. Chứng minh rằng trong một đơn đồ thị vô hướng nếu không chứa chu trình thì sẽluôn tồn
tại ít nhất hai đỉnh treo.
12. Cho một đồ thị có hướng có n đỉnh. Hỏi đồ thịnày có thểcó tối đa bao nhiêu cạnh. Trong
trường hợp sốcạnh là tối đa thì mỗi đỉnh sẽcó bán bậc ra và bán bậc vào là bao nhiêu?
13. Có tồn tại đơn đồ thị vô hướng có 5 đỉnh với các sốbậc sau đây không? Nếu có, hãy vẽ đồ thị đó.
a. 3, 3, 3, 3, 2
b. 1, 2, 3, 4, 5
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
123
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
b. C
n
c. W
n
18. Với các giá trịnào của m, n thì đồ thịK
mxn
là đồ thịchính quy?
19. Đồ thịbù
G
của đồ thịGlà đồ thịcó cùng số đỉnh với G. Hai đỉnh u và v được gọi là kề
nhau (được nối bằng một cạnh) trong
G
nếu và chỉnếu nó không kềnhau trong G ( (u,v)
không phải là cạnh trong G). Hãy xác định đồ thịbù của các đồ thị dưới đây:
a. n
K
b. n
C
c. mxn
K
d.
W
n
20. Nếu đồ thị G có n đỉnh và m cạnh thì đồ thị
G
có bao nhiêu đỉnh, bao nhiêu cạnh?
21. Chứng minh rằng nếu G là đồ thị phân đôi có n đỉnh và m cạnh thì ta có:
2
4
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ịK3x3 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ịKmxm
27. Chứng minh rằng đồ thị vô hướng liên thông G có n đỉnh thì sẽcó ít nhất n – 1 cạnh.
28. Giảsử v là đỉnh đầu của một cạnh cắt. Chứng minh rằng v là đỉnh cắt nếu và chỉnếu nó
không là đỉnh treo.
29. Chứng minh rằng trong một đơn đồ thịsẽluôn tồn tại ít nhất 2 đỉnh không là đỉnh cắt.
(Gợi ý: sửdụng kết quảcủa bài tập 11).
30. Chứng minh rằng một cạnh trong đơn đồ thịlà cạnh cắt nếu và chỉnếu nó không nằm trong
bất kỳchu trình nào của đồ thị.
31. Xét một đồ thị vô hướng có k thành phần liên thông. Chứng minh rằng sốcạnh của đồ thị
này không thể vượt quá
( )( 1)
2
n k n k
?
1
2
3
4
5
6
7
Chương 2. BIỂU DIỄN ĐỒ THỊ
32. Xác định ma trận kềcủa các đồ thị sau đây:
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 A2
b. Hãy cho biết giá trịcủa A2ij biểu diễn cho cái gì?
c. Từ đó, nếu ta tính An thì Anij 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
nhau.
40. Nêu đặc điểm của ma trận kềcủa các đồ thịsau:
a. Đồ thị đầy đủ
b. Đồ thị phân đôi đầy đủ K1xn
41. Hãy vẽ các đồ thị được biểu diễn bởi các ma trận kề dưới đây. Hãy cho biết chúng là đồ thị
có hướng hay vô hướng:
a.
0 0 1
1 0 1
1 1 0
b.
0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0
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 Cnlà đồ 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.