Bài tập Toán rời rạc - Bài 4+5+6

BÀI TẬP PHẦN ĐỒ THỊ NORMAN L. BIGGS (DISCRETE MATHEMATICS) 1. Đồ thị và biểu diễn 1. Có ba ngôi nhà A;B;C, mỗi ngôi nhà đều kết nối với cả ba nhà cung cấp ga, nước, và điện: G;W;E. (a) Hãy viết danh sách cạnh cho đồ thị biểu diễn bài toán này và vẽ nó. (b) Liệu bạn có thể vẽ đồ thị này trên mặt phẳng để không có cạnh cắt nhau không? 2. Một khu vườn được thiết kế dạng đồ thị hình bánh xe Wn, trong đó tập đỉnh là V = f0; 1; 2; : : : ; ng và tập cạnh là f0; 1g; f0; 2g;


; f0; ng f1; 2g; f2; 3g;


; fn 1; ng; fn; 1g Hãy mô tả một đường đi bắt đầu và kết thúc đều tại đỉnh 0 và thăm mỗi đỉnh đúng một lần. 3. Với mỗi số nguyên dương n, ta định nghĩa đồ thị đầy đủ Kn là đồ thị gồm n đỉnh, trong đó mọi cặp đỉnh đều kề nhau. Đồ thị Kn có bao nhiêu cạnh? Với giá trị nào của n thì ta có thể vẽ đồ thị Kn trên mặt phẳng sao cho không có cạnh nào cắt nhau. 4. Một 3-chu trình trong đồ thị là tập ba đỉnh đôi một kề nhau. Hãy xây dựng một đồ thị với 5 đỉnh và 6 cạnh mà không chứa C3. 2. Đẳng cấu 1. Hãy chứng minh rằng hai đồ thị sau không đẳng cấu. 2. Tìm một đẳng cấu giữa các đồ thị định nghĩa bởi hai danh sách cạnh sau. (Đây chính là đồ thị Peterson) a b c d e f g h i j b a b c d a b c d e e c d e a h i j f g f g h i j i j f g h 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 0 1 0 2 6 5 0 1 2 3 4 4 3 5 7 7 6 8 7 6 8 9 9 9 8 1 2 NORMAN L. BIGGS (DISCRETE MATHEMATICS) 3. Xét G = (V;E) là đồ thị định nghĩa như sau. Tập đỉnh V là tập mọi xâu nhị phân độ dài 3, và tập cạnh E chứa các cặp xâu khác nhau đúng một vị trí. Chứng minh rằng G đẳng cấu với đồ thị tạo bởi các góc và các cạnh của một khối lập phương. 3. Bậc 1. Các dãy số sau đây có thể là các bậc của mọi đỉnh của đồ thị nào đó không? Nếu có hãy vẽ một đồ thị như vậy. (a) 2; 2; 2; 3 (b) 1; 2; 2; 3; 4 (c) 2; 2; 4; 4; 4 (d) 1; 2; 3; 4. 2. Xét đồ thị G = (V;E), phần bù G của G là đồ thị có cùng tập đỉnh là V và tập cạnh là tất cả các cặp đỉnh khong kề nhau trong G. Nếu G có n đỉnh và các bậc của nó là d1; d2; : : : ; dn, thì các bậc của G là gì? 3. Liệt kê các đồ thị chính quy bậc 4 (đôi một không đẳng cấu) với bảy đỉnh. 4. Giả sử G1 và G2 là các đồ thị đẳng cấu. Với mỗi k  0, ký hiệu ni(k) là số đỉnh của Gi có bậc k (i = 1; 2). Chứng minh rằng n1(k) = n2(k). 5. Chứng minh rằng trong mọi đồ thị với ít nhất hai đỉnh luôn có hai đỉnh cùng bậc. 4. Đường đi và chu trình 1. Tìm số thành phần liên thông của đồ thị với danh sách cạnh là a b c d e f g h i j f c b h c a b d a a i g e g i c f f j g j e 2. Đồ thị mô tả bữa tiệc của April có bao nhiêu thành phần liên thông? 3. Tìm chu trình Hamilton của đồ thị tạo bởi các đỉnh và cạnh của khối lập phương. 4. Năm tới, Dr Chunner và Dr Dodder định đi thăm đảo Mianda. Các địa điểm hấp dẫn và đường đi nối giữa chúng được biểu diễn bởi đồ thị có danh sách cạnh là 0 1 2 3 4 5 6 7 8 1 0 1 0 3 0 1 0 1 3 2 3 2 5 4 5 2 3 5 6 7 4 6 7 6 5 7 8 8 8 8 7 Liệu có thể tìm đường cho họ thỏa mãn như trong ví dụ trên lớp. 5. Một con chuột định ăn một khối lập phương bơ 3 3 3. Nó bắt đầu ở một góc và ăn hết toàn bộ khối 1 1 1 trước khi chuyển sang ăn ô bên cạnh. Liệu con chuột có thể ăn miếng cuối cùng ở trung tâm khối lập phương không? BÀI TẬP PHẦN ĐỒ THỊ 3 5. Cây 1. Xét T = (V;E) là cây với jV j  2. Hãy dùng tính chất (T1) jEj = jV j 1; để chứng minh rằng T có ít nhất hai đỉnh bậc 1. 5. Hãy chứng minh rằng tính chất: (T1) với mỗi cặp đỉnh x; y có duy nhất một đường đi từ x tới y; kéo theo cả hai tính chất: (T1) T liên thông; và (T2) T không có chu trình. 3. Ta nói rằng đồ thị F là một rừng nếu nó có tính chất: (T1) F không có chu trình. Hãy chứng minh rằng nếu F = (V;E) là một rừng với c thành phần liên thông thì jEj = jV j c: 6. Tô màu đồ thị 1. Tìm sắc số của các đồ thị sau: (i) đồ thị đầy đủ Kn; (ii) đồ thị chu trình C2r với số đỉnh chẵn; (iii) đồ thị chu trình C2r+1 với số đỉnh lẻ. 2. Tìm sắc số của các đồ thị sau: 3. Hãy mô tả tất cả các đồ thị G có (G) = 1. 7. Thuật toán tham lam tô màu đỉnh 1. Tìm 3 cách đánh số thứ tự các đỉnh của đồ thị lập phương dưới đây để thuật toán tham lam dùng 2; 3; và 4 màu. 4 NORMAN L. BIGGS (DISCRETE MATHEMATICS) 2. Chứng minh rằng với mọi đồ thị G ta luôn có cách sắp thứ tự các đỉnh để thuật toán tham lam tô màu G dùng đúng (G) màu. [Gợi ý: dùng một cách tô màu dùng (G) màu để xác định thứ tự đỉnh cho thuật toán tham lam.] 3. Ký hiệu ei(G) là số đỉnh của đồ thị G có bậc nhỏ hơn i. Dùng thuật toán tham lam để chỉ ra rằng nếu tồn tại i để ei(G)  i+ 1 thì (G)  i+ 1. 4. Đồ thị Mr (r  2) đặt được từ đồ thị chu trình C2r bằng cách thêm các cạnh nối giữa mỗi cặp đỉnh đối nhau. Chứng minh rằng (i) Mr là đồ thị hai phần khi r là số lẻ. (ii) (Mr) = 3 khi r chẵn và r 6= 2. (iii) (M2) = 4. 8. Bài tập thêm 1. Với giá trị nào của n đồ thị Kn có hành trình Euler? 2. Dùng nguyên lý quy nạp để chứng minh rằng nếu G = (V;E) là một đồ thị với jV j = 2m, và G không chứa tam giác (đồ thị C3), vậy thì jEj  m2. 3. Xét X = f1; 2; 3; 4; 5g và đặt V là tập mọi tập con 2-phần tử của X. Ký hiệu E là tập mọi cặp phần tử rời nhau của V . Chứng minh rằng đồ thị G = (V;E) đẳng cấu với đồ thị dưới đây. Thực ra đây chính là một phiên bản của đồ thị Peterson nổi tiếng. 4. Xét G là một đồ thị hai phần với số đỉnh lẻ. Chứng minh rằng G không có chu trình Hamilton. 5. Đồ thị k-lập phương là đồ thị trong đó tập đỉnh là tập mọi xâu nhị phân độ dài k và hai đỉnh kề nhau nếu chúng khác nhau đúng một vị trí. Chứng minh rằng (a) Qk là đồ thị chính quy bậc k, (b) Qk là đồ thị hai phần. 6. Chứng minh rằng đồ thị Qk có chu trình Hamilton. 7. Chứng minh rằng đồ thị Peterson không có chu trình Hamilton. 8. Chứng minh rằng nếu  : V1 ! V2 là một đẳng cấu của các đồ thị G1 = (V1; E1) và G2 = (V2; E2) thì hàm  : E1 ! E2 định nghĩa bởi fx; yg = f(x); (y)g (fx; yg 2 E1) là một song ánh. BÀI TẬP PHẦN ĐỒ THỊ 5 9. Nếu G là một đồ thị chính quy với bậc k và n đỉnh, hãy chứng minh rằng (G)  n n k : 10. Hãy xây dựng năm đồ thị chính quy bậc 3 đôi một không đẳng cấu với tám đỉnh. 11. Chứng minh rằng đồ thị đầy đủ K2n+1 là hợp của n chu trình Hamilton, trong đó không có hai chu trình nào có chung cạnh. 12. Liệu một con mã có thể đi hết các ô vuông của bàn cờ mỗi ô đúng một lần rồi quy về ô vuông xuất phát không? Diễn dịch câu trả lời của bạn theo thuật ngữ của chu trình Hamilton trong một đồ thị nào đó. 13. Đồ thị kỳ lạ Ok được định nghĩa như sau (khi k  2): các đỉnh là các tập con k 1 phần tử của một tập 2k 1 phần tử nào đó, và các cạnh nối hai tập con rời nhau. (Vậy thì O3 là đồ thị Peterson.) Chúng minh rằng (Ok) = 3 với mọi k  2. 14. Chứng minh rằng nếu G là một đồ thị với n đỉnh, m cạnh, và c thành phần liên thông thì n c  m  1 2 (n c)(n c+ 1): Hãy xây dựng các ví dụ để chứng minh rằng cả hai dấu bằng có thể đạt được với mọi giá trị của n và c thỏa mãn n  c. 15. Một dãy số d1; d2; : : : ; dn là dãy bậc nếu có một đồ thị với n đỉnh gán nhãn v1; v2; : : : ; vn sao cho deg(vi) = di (1  i  n). Chứng minh rằng nếu d1; d2; : : : ; dn là dãy bậc và d1  d2 


 dn, vậy thì d1 + d2 +


+ dk  k(k 1) + nX j=k+1 min(k; di) với 1  k  n. 16. Chu vi nhỏ nhất của một đồ thị G là giá trị nhỏ nhất của g để G có chứa một g-chu trình. Chứng minh rằng một đồ thị chính quy với bậc k và có chu vi nhỏ nhất 2m+ 1 phải có ít nhất 1 + k + k(k 1) +


+ k(k 1)m1 đỉnh, và rằng một đồ thị chính quy với bậc k và chu vi nhỏ nhất bằng 2m phải có ít nhất 2[1 + (k 1) + (k 1)2 +


+ (k 1)m1] đỉnh. 17. Hãy xây dựng một bảng của các cận dưới trong hai bài tập trước khi k = 3 và chu vi nhỏ nhất là 3; 4; 5; 6; 7. Chứng minh rằng có một đồ thị đạt được cận dưới cho bốn trường hợp đầu tiên, nhưng không cho trường hợp thứ 5. 18. Xét G = (V;E) là đồ thị với ít nhất ba đỉnh thỏa mãn deg(v)  1 2 jV j (v 2 V ): Chứng minh rằng G có chu trình Hamilton. 19. Chứng minh rằng nếu G là đồ thị bù của đồ thị G, thì (G)(G)  n, với n là số đỉnh của G.