Giáo trình Toàn rời rạc 1 - Bài tập chương 8: Lý thuyết đồ 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 8
Lý thuyết đồ thị
1 Dẫn nhập
Trong phần bài tập này, chúng ta sẽ làm quen với các khái niệm và định nghĩa trong lý
thuyết đồ thị . Sinh viên cần ôn lại lý thuyết của chương 4 trước khi làm các bài tập bên
dưới.
2 Bài tập mẫu
Câu 1.
Có bao nhiêu cạnh trong một đồ thị vô hướng có 6 đỉnh, mỗi đỉnh có bậc bằng 4?
Lời giải. Vì tổng các bậc của đồ thị là 6 × 4 = 24, nên 2e=24. Do đó, số cạnh trong đồ
thị là e=12.
Đồ thị có thể được vẽ như hình bên dưới đây:
2
A
E
B
D
F
C
Câu 2.
Có bao nhiêu bậc vào và bậc ra của mỗi đỉnh trong đồ thị có hướng G như dưới đây?
Lời giải.
• deg−(A) = 0, deg−(B) = 2, deg−(C) = 2, deg−(D) = 2, deg−(E) = 2, deg−(F) = 3,
• deg+(A) = 4, deg+(B) = 2, deg+(C) = 1, deg+(D) = 2, deg+(E) = 1, deg+(F) = 1.
Giáo trình Toán Rời Rạc 1
Trang 1/10
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
B
F
C
E
D
2
Câu 3.
Liệu có tồn tại một đơn đồ thị gồm các đỉnh mà có bậc lần lượt là :
a) 1,1,2,2?
b) 1,1,2,2,3,3,3?
Nếu có hãy vẽ đồ thị đó.
Lời giải.
a) Có tồn tại đơn đồ thị gồm 4 đỉnh mà có bậc lần lượt là 1, 1, 2, và 2.
Đồ thị này được vẽ như sau:
B
C
A
D
b) Không tồn tại đơn đồ thị gồm 7 đỉnh mà có bậc lần lượt là 1,1,2,2,3,3, và 3 vì tổng số
bậc của tất cả các đỉnh là một số lẻ.
2
3 Bài tập cần giải
Câu 4.
Có bao nhiêu cạnh trong một đồ thị vô hướng có 8 đỉnh, mỗi đỉnh có bậc bằng 4?
Lời giải. Vì tổng các bậc của đồ thị là 8 × 4 = 32, nên 2m=32. Do đó, số cạnh trong đồ
thị là m = 16.
Giáo trình Toán Rời Rạc 1
Trang 2/10
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Đồ thị có thể được vẽ như hình bên dưới đây:
2
A
B
E
H
G
C
D
F
Câu 5.
Có bao nhiêu bậc vào và bậc ra của mỗi đỉnh trong đồ thị có hướng G như dưới đây?
A
B
E
H
G
C
D
F
Lời giải.
• deg−(A) = 0, deg−(B) = 2, deg−(C) = 2, deg−(D) = 2, deg−(E) = 2, deg−(F) = 3,
deg−(G) = 2, deg−(H) = 3,
• deg+(A) = 4, deg+(B) = 2, deg+(C) = 1, deg+(D) = 2, deg+(E) = 1, deg+(F) = 1,
deg+(G) = 1, deg+(H) = 1.
2
Câu 6.
Liệu có tồn tại một đơn đồ thị gồm các đỉnh mà có bậc lần lượt là :
a) 1,2,3,4?
Giáo trình Toán Rời Rạc 1
Trang 3/10
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) 3,3,3,3?
c) 1,2,3,4,5,6,7?
Nếu có hãy vẽ đồ thị đó.
Lời giải.
a) Không tồn tại đơn đồ thị gồm 4 đỉnh mà có bậc lần lượt là 1, 2, 3, và 4 vì trong đơn đồ
thị gồm n đỉnh, bậc của mọi đỉnh phải nhỏ n.
b) Có tồn tại đơn đồ thị gồm 4 đỉnh mà các đỉinh đều có bậc là 3.
Đồ thị này được vẽ như sau:
B
C
A
D
c) Không tồn tại đơn đồ thị gồm 7 đỉnh mà có bậc lần lượt là 1, 2, 3, 4, 5, 6, và 7 vì tổng
số bậc của tất cả các đỉnh phải là một số chẵn.
2
Câu 7.
Số cạnh nhiều nhất có thể của một đơn đồ thị gồm 10 đỉnh là bao nhiêu? Còn trong trường
hợp đa đồ thị và giả đồ thị thì như thế nào?
Lời giải. Một đơn đồ thị gồm 10 đỉnh có tối đa 45 cạnh. Còn đa đồ thị và giả đồ thị thì
có thể có vô số cạnh (số cạnh tối đa là vô hạn).
2
Câu 8.
Đồ thị phân đôi.
a) Các chu trình C3,C4, và C5 có phải là đồ thị phân đôi không?
b) Mệnh đề sau là đúng hay là sai : "Nếu một đồ thị có chứa một tam giác thì sẽ không
phải là phân đôi". Chứng minh.
c) Mệnh đề nghịch đảo "Nếu một đồ thị không chứa bất kỳ một tam giác nào thì sẽ phân
đôi" là đúng hay sai. Chứng minh.
Lời giải.
a) C4 là đồ thị phân đôi nhưng C3, C5 thì không phải .
Giáo trình Toán Rời Rạc 1
Trang 4/10
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) Mệnh đề "Nếu một đồ thị có chứa một tam giác thì sẽ không phải là phân đôi" là đúng.
Vì xét 3 đỉnh của tam giác, theo nguyên lý chuồng chim bồ câu, luôn tồn tại 2 trong 3
đỉnh này nằm trong một tập con của V (hoặc V1, hoặc V2). Và do giữa 2 đỉnh này luôn
có một cạnh nối liền chúng, nên đồ thị loại này luôn không phải là đồ thị phân đôi.
c) Mệnh đề nghịch đảo "Nếu một đồ thị không chứa bất kỳ một tam giác nào thì sẽ phân
đôi" là sai do C5 là một phản ví dụ.
2
Câu 9.
Do khói, bụi và hơi nước bốc lên từ một miệng núi lửa bên dưới mặt sông băng Eyjafjal-
lajokull ở Iceland vào ngày thứ tư (14/04/2010), hơn 90.000 chuyến bay ở châu Âu đã bị
hủy. Đây cũng là một minh chứng về sự bất ổn của thiên nhiên có thể gây tổn hại tới công
việc kinh doanh toàn cầu.
Để giảm thiểu thiệt hại về kinh tế, cơ quan quản lý tối ưu hóa và lập lịch đường bay
EuroControl cố gắng tiếp tục duy trì một số đường bay đi và đến Việt Nam, liên quan
đến các thành phố lớn như: Hồ Chí Minh (A), Paris (B), Berlin (C), và London (D). Tuy
nhiên, do ảnh hưởng của môi trường thiên nhiên nói trên, chỉ có một vài chuyến bay có
thể hoạt động: từ A hướng đến B và D, từ B hướng đến C, từ C hướng đến A và D, từ
D hướng đến B.
a) Hãy vẽ đồ thị có hướng tương ứng.
b) Viết ma trận kề M cho đồ thị có hướng này
c) Hãy tính M + M2 + M3 và cho biết ý nghĩa của ma trận này.
Lời giải.
a) Đồ thị có hướng tương ứng :
B
A
C
D
b) Viết ma trận kề M (adjacent matrix) gắn liền với đồ thị này.
0 1 0 1
0 0 1 0
1 0 0 1
0 1 0 0
M
=
Giáo trình Toán Rời Rạc 1
Trang 5/10
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 M2 và M3.
0 1 1 0
1 0 1 1
0 2 1 0
0 1 2 0
1 0 0 1
1 0 0 1
0 2 0 1
0 0 1 0
M2
=
M3
=
Tính tổng ma trận M + M2 + M3.
0 1 0 1
0 0 1 0
1 0 0 1
0 1 0 0
0 1 1 0
1 0 0 1
0 2 0 1
0 0 1 0
1 0 1 1
0 2 1 0
0 1 2 0
1 0 0 1
1 2 2 2
1 2 1 2
1 3 2 2
1 1 1 1
2
3
+
+
M+M +M =
=
Vì M là ma trận đại diện cho các liên thông trực tiếp giữa hai đỉnh trong một đồ thị,
M2 là ma trận đại diện cho các liên thông gián tiếp thông qua một đỉnh trung gian, và
M2 là ma trận đại diện cho các liên thông gián tiếp thông qua hai đỉnh trung gian.
Do vậy, tổng M + M2 + M3 tạo thành ma trận đại diện cho các đường liên thông trực
tiếp và gián tiếp thông qua tối đa hai đỉnh trung gian, hay nói cách khác, là số đường
đi có thể giữa hai điểm.
2
4 Bài tập nâng cao
Câu 10.
Đếm số cạnh của các đồ thị đặc biệt sau:
a) Kn
b) Cn
c) Km,n
d) Wn
e) Qn
Câu 11.
Hãy vẽ các đồ thị sau:
a) K8
b) K1,7
c) K4,4
d) W8
Giáo trình Toán Rời Rạc 1
Trang 6/10
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) Q4
Câu 12.
Hãy xác định danh sách kề, ma trận kề và ma trận liên thuộc của đồ thị sau:
F
B
E
C
D
A
G
Câu 13.
• Hãy xác định danh sách kề, ma trận kề và ma trận liên thuộc của đồ thị sau:
B
A
C
D
F
E
• Hãy cho biết đồ thị này có phải là đồ thị phân đôi không. Nếu có, hãy vẽ lại dưới
dạng một đồ thị phân đôi.
• Hãy cho biết đồ thị này có phải là đồ thị phẳng không. Nếu có, hãy vẽ lại dưới dạng
một đồ thị phẳng.
Câu 14.
Hãy xác định danh sách kề, ma trận kề và ma trận liên thuộc của hai đồ thị sau và cho
biết hai đồ thị này có đẳng cấu không.
Câu 15.
Hãy xác định danh sách kề, ma trận kề và ma trận liên thuộc của hai đồ thị sau và cho
Giáo trình Toán Rời Rạc 1
Trang 7/10
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
E
F
D
E
F
C
B
D
C
B
G1
G2
A
B
A
C
F
C
D
F
E
E
D
G1
G2
biết hai đồ thị này có đẳng cấu không.
Câu 16.
Hãy vẽ các đồ thị sau:
a) Hãy vẽ một đồ thị gồm các đỉnh biểu diễn các số từ 1 đến 10, trong đó bất kỳ 2 đỉnh
nào sẽ nối với nhau nếu và chỉ nếu 1 trong 2 số tương ứng sẽ chia hết cho số còn lại
b) Hãy vẽ một đồ thị gồm các đỉnh biểu diễn các số từ 1 đến 10, trong đó bất kỳ 2 đỉnh
nào sẽ nối với nhau nếu và chỉ nếu 2 số tương ứng có ước số chung lớn nhất là 1.
c) Tìm số cạnh, và số bậc của từng đỉnh trong các đồ thị trên
Câu 17.
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 18.
Hãy chứng minh rằng trong một đơn đồ thị, luôn tồn tại hai đỉnh có cùng bậc.
Giáo trình Toán Rời Rạc 1
Trang 8/10
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 19.
Các đồ thị đặc biệt sau có phải là đồ thị phân đôi không, hãy giải thích:
a) Kn
b) Cn
c) Wn
d) Qn
Câu 20.
Hãy chứng minh rằng trong một đồ thị vô hướng G,
a) nếu số đỉnh là một số chẵn, thì tồn tại một đỉnh trong G có số bậc là lẻ.
b) nếu số đỉnh là một số lẻ, thì tồn tại một đỉnh trong G có số bậc là chẵn.
c) nếu số đỉnh là một số chẵn, thì số đỉnh bậc chẵn trong G phải là số chẵn.
d) nếu số đỉnh là một số lẻ, thì số đỉnh bậc chẵn trong G phải là số lẻ.
e) nếu số đỉnh là một số chẵn, thì số đỉnh bậc lẻ trong G phải là chẵn.
f) nếu số đỉnh là một số lẻ, thì số đỉnh bậc chẵn trong G phải là lẻ.
Câu 21.
Một buổi thảo luận có 101 khách mời; hãy chứng minh rằng tồn tại một người khách mời
đã tranh luận với một số chẵn người khách mời khác.
Câu 22.
Có 4 người dân, 4 ông cha và 4 tên ác quỷ dracula cùng cư ngụ trên cùng một đất nước
X. Do đất nước này bị động đất, tất cả mọi người đều muốn chuyển sang một nước Y trù
phú hơn, và vì thế mọi người đều đã đăng ký một dịch vụ du lịch hỗ trợ di chuyển sang
đất nước giàu có Y.
Vì sự cách trở địa lý, việc di chuyển chỉ có thể thông qua máy bay và hiện chỉ có duy nhất
một máy bay trực thăng và một viên phi công còn cư ngụ trên nước X. Hơn nữa, số lượng
dự trữ xăng cũng chỉ đủ để di chuyển 5 vòng qua lại giữa hai đất nước X và Y.
Nếu trên đường di chuyển, số lượng dracula nhiều hơn số lượng ông cha, thì viên phi công
sẽ bị một tên ác quỷ nào đó hút hết máu và sẽ không còn khả năng điều khiển máy bay.
Ngoài ra, tại một thời điểm bất kỳ và trên một đất nước bất kỳ, nếu số lượng dracula nhiều
hơn số lượng ông cha, thì dracula sẽ có khả năng hút máu những người xung quanh trong
đất nước đó.
Liệu có thể tìm ra giải pháp tối ưu giúp viên phi công vận chuyển tất cả hành khách sang
đất nước B mà vẫn đảm bảo an toàn cho các hành khách và chính bản thân của anh ta
sau tất cả các chuyến bay, đồng thời anh ta cũng có thể di trú sang đất nước Y sau khi
hoàn thành nhiệm vụ.
Giáo trình Toán Rời Rạc 1
Trang 9/10
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
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 các định nghĩa, các tính
chất, cũng như là các định lý trong lý thuyết đồ thị (tham khảo chi tiết trong chương 4).
Ngoài ra, các bài tập này cũng đã giúp chúng ta phần nào hiểu thêm các ứng dụng thực
tiễn về đồ thị.
Giáo trình Toán Rời Rạc 1
Trang 10/10
10 trang
19800
Free
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 8: Lý thuyết đồ 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_8_ly_thuyet_do_thi.pdf
