bởi admin lúc Mon, Apr 16 '18 11:39 AM | Lần xem 539 | Lần tải 21
  • Download images đề thi lí thuyết đồ thị 2

ĐỀ THI
Lý thuyết đồ thị
( 120 phút – Không dùng tài liệu )
Trả lời các câu hỏi trong những đề bài sau đây (giải thích rõ ràng, chạy thuật toán trên giấy hay
chứng minh các khẳng định của bạn tùy theo câu hỏi).
Bài 1
(H)
1.1)
Chứng minh một đồ thị đơn và phẳng luôn chứa ít nhất
một đỉnh có bậc nhỏ hơn hay bằng 5.
1.2)
Xét xem đồ thị (H), hình bên cạnh, có phải là đồ thị
Hamilton hay không.
1
2
Bài 2
Xem sơ đồ bố trí các chiếc cầu như hình vẽ sau đây.
2.1)
Vẽ
đồ
thị
(K):
tập
đỉnh

các
vùng (có ghi chữ trong hình) tập
cạnh

các
chiếc
cầu
ắc
qua
những vùng này.
2.2)
(K) có là đồ thị đơn hay không?
2.3)
Vẽ đồ thị con (G1) của (K) sinh
ởi tập đỉnh {E, F, G}.
2.4)
Viết ma trận liên thuộc của (G1).
2.5)

thể
xuất
phát
từ
một
vùng
(trong hình vẽ) đi dạo qua tất cả
các chiếc cầu, mỗi chiếc đúng một
lần hay không?
2.6)
Tìm số màu của đồ thị (K).
2.7)
Giả sử các vùng A, B, C, … được đặt các trọng số W(A)=4, W(B)=6, W(C)=8, … Mỗi chiếc
cầu nối hai vùng x và y được gắn với trọng số là bội số chung nhỏ nhất của W(x) và W(y).
(a) Hãy tính trọng số mỗi chiếc cầu trong hình vẽ.
(b) Tìm một cây khung ngắn nhất của đồ thị (K).
(c) Trong đồ thị (K) tìm đường đi ngắn nhất từ đỉnh E đến đỉnh G mà bắt buộc phải đi ngang
qua chiếc cầu nối 2 đỉnh A và D.
Bài 3
Gọi (G2) là đồ thị có được bằng cách thêm vào một cạnh nối đỉnh 1 và đỉnh 2 trong đồ thị (H) của
ài 1. Hãy xét xem đồ thị (G2) có phẳng hay không.
( Đề thi tổng cộng 1 trang)
bởi admin lúc Mon, Apr 16 '18 11:39 AM

đề thi lí thuyết đồ thị đại học khoa học tự nhiên
774909.pdf
Kích thước: 218.43 kb
Lần tải: 0 lần
Download