Bài tập Toán rời rạc - Bài 10

Toán rời rạc: Cây Bài tập 10 1. Có thể tìm được một cây có 8 đỉnh và thoả điều kiện dưới đây hay không? Nếu có, hãy vẽ cây đó; còn nếu không, hãy giải thích. a. Mọi đỉnh đều có bậc 1. b. Mọi đỉnh đều có bậc 2. c. Có 6 đỉnh bậc 2 và 2 đỉnh bậc 1. d. Có một đỉnh bậc 7 và 7 đỉnh bậc 1. 2. Chứng minh định lý móc xích kiểu hoa cúc trong slides. 3. a. Chứng minh rằng bậc trung bình của cây luôn nhỏ hơn 2. b. Giả sử mọi đỉnh trong một đồ thị có bậc ít nhất bằng k. Hãy giải thích tại sao đồ thị có một đường đi độ dài k. 4. Một siêu khối Hn là một đồ thị với tập đỉnh là tập các xâu nhị phân độ dài n, và hai đỉnh trong Hn là kề nhau nếu và chỉ nếu chúng chỉ khác nhau đúng một bit. Ví dụ trong H3, đỉnh 111 kề với đỉnh 011, nhưng hai đỉnh 101 và 011 là không kề. a. Tính số đỉnh và số cạnh của Hn. b. Giải thích tại sao ta không thể tìm được hai cây bao trùm không có chung cạnh trong H3. 5. Chứng minh rằng mọi cây đều là đồ thị hai phần. 6. Giả sử G là một đồ thị liên thông với n đỉnh. Hãy chứng minh rằng G có đúng một chu trình nếu và chỉ nếu G có n cạnh. 7. Chứng minh rằng: Nếu G là một cây với đúng 2k đỉnh bậc lẻ, vậy G phân rã được thành k đường đi. 8. Hãy liệt kê tất cả các cây bao trùm đôi một không đẳng cấu của mỗi đồ thị dưới đây. a. K3 b. K4 c. K5 d. K3,3 9. Tìm cây bao trùm nhỏ nhất bằng thuật toán Kruskal của đồ thị gồm các đỉnh A, B, C , D, E, F , G, H được cho bởi ma trận trọng số sau. A B C D E F G H A ∞ 5 7 ∞ 10 ∞ ∞ ∞ B 5 ∞ ∞ ∞ 12 3 ∞ ∞ C 7 ∞ ∞ 9 ∞ ∞ 5 ∞ D ∞ ∞ 9 ∞ 1 ∞ 5 8 E 10 12 ∞ 1 ∞ 7 ∞ ∞ F ∞ 3 ∞ ∞ 7 ∞ ∞ 9 G ∞ ∞ 5 5 ∞ ∞ ∞ 7 H ∞ ∞ ∞ 8 ∞ 9 7 ∞ 1 10. Giả sử G = (V, E) là đồ thị có trọng số; và trong G tồn tại cạnh e có trọng số nhỏ nhất, có nghĩa rằng w(e)< w( f ) với mọi cạnh f ∈ E−{e}. Chứng minh rằng mọi MST của G đều phải chứa e. 11. Xét G là một lưới 4× 4 với cạnh dọc và ngang giữa hai đỉnh cạnh nhau. Một cách hình thức, tập đỉnh của nó là V (G) := {(k, j) | 0≤ k, j ≤ 3}. Đặt hi j là cạnh ngang 〈(i, j) − (i + 1, j)〉 và v ji là cạnh dọc 〈( j, i) − ( j, i + 1)〉 với mọi i = 0,1,2 và j = 0,1,2, 3. Trọng số của các cạnh này được định nghĩa như sau: w(hi j) := 4i + j 100 , w(v ji) := 1+ i + 4 j 100 . (a) Hãy vẽ G trên mặt phẳng. (b) Xây dựng một cây bao trùm trọng số nhỏ nhất (MST) cho G bằng thuật toán Kruskal. (c) Xây dựng một MST cho G bắt đầu từ đỉnh (1,2) bằng thuật toán Prim–Jarník như sau: Input: Đồ thị G = (V, E) liên thông có trọng số. Output: MST T = (W, F) của G. 1 W := {x}, với x là một đỉnh bất kỳ trong V ; 2 F := ;; 3 while W 6= V do 4 Tìm một cạnh {u, v} có trọng số nhỏ nhất trong G thoả mãn u ∈W và v /∈W ; 5 Thêm đỉnh v vào W ; 6 Thêm cạnh {u, v} vào F ; 7 end (d) Chứng minh rằng với mọi đồ thị có trọng số G, thuật toán Prim-Jarník luôn cho một MST. 12. Chứng minh rằng: Nếu trọng số trên các cạnh của đồ thị G là khác nhau từng đôi một, vậy đồ thị có duy nhất một MST. 13. Cây bao trùm lớn nhất của một đồ thị liên thông, có trọng số là cây bao trùm có trọng số lớn nhất. Hãy đề xuất một thuật toán tương tự thuật toán Kruskal xây dựng cây bao trùm cực đại của một đồ thị liên thông có trọng số. 14. Hãy đề xuất một thuật toán tương tự thuật toán Prim-Jarník để xây dựng cây bao trùm cực đại của một đồ thị liên thông có trọng số. 15. Hãy tìm cây bao trùm cực đại cho đồ thị có trọng số trong bài tập 11. 16. Hãy đề xuất một thuật toán tìm cây bao trùm nhỏ thứ 2 trong một đồ thị liên thông có trọng số. Chứng minh tính đúng đắn của thuật toán bạn vừa xây dựng. 2