Bài tập Đồ thị

BÀI TẬP LOẠI 11. Vẽ tất cả đồ thị a. 3 đỉnh và 3 cạnh. b. 4 đỉnh, 4 cạnh và không có vòng, không có cạnh //. c. liệt kê 4 đồ thị đều trong 2 trường hợp trên. d. đều, 4 đỉnh, mỗi đỉnh bậc 3, không vòng, không có cạnh //. e. đều, 5 đỉnh, mỗi đỉnh bậc 3.2. Tại một câu lạc bộ có 9 thành viên ngồi ăn với nhau mỗi ngày ở một bàn tròn, mỗi người muốn mỗi ngày 2 người bạn kế bên là bạn mới. Sự xắp xếp kéo dài trong bao nhiêu ngày ?INSTANT INSANITY3. Cho 4 khối vuông, 6 mặt của mỗi khối vuông được tô bằng 4 màu khác nhau. Có thể xắp xếp 4 khối thành một cột sao cho mỗi mặt của cột có 4 màu khác nhau ?.BÀI TẬP4. Một đồ thị có 21 cạnh có 7 đỉnh bậc 1, 3 đỉnh bậc 2, 7 đỉnh bậc 3, các đỉnh còn lại bậc 4. Đồ thị có bao nhiêu đỉnh ?. Nếu thêm 6 đỉnh bậc 0 thì câu trả lời là bao nhiêu.5. Chứng minh trong đồ thị đơn giản có ít nhất 2 đỉnh thì phải có ít nhất 2 đỉnh có cùng bậc.6. Các đồ thị sau có bao nhiêu đỉnh nếu chúng có : a. 12 cạnh, tất cả đỉnh bậc 2. b. 15 cạnh, 3 đỉnh bậc 4, các đỉnh còn lại bậc 3. c. 20 cạnh, các đỉnh có cùng bậc.BÀI TẬP7. Số đỉnh lớn nhất trong một đồ thị 19 cạnh và các đỉnh có bậc ít nhất là 3 là bao nhiêu ?.8. Chứng minh đồ thị đơn giản v đỉnh có số cạnh tối đa v(v1)/2. 9. Nếu đồ thị đơn giản có 50 cạnh, số đỉnh nhỏ nhất là bao nhiêu?. Tổng quát cho n cạnh.10. Chứng minh một đồ thị đều bậc lẻ phải có số đỉnh chẵn.BÀI TẬP11. Đồ thị có v đỉnh, tất cả các đỉnh có bậc lẻ ngoại trừ một đỉnh. Có bao nhiêu đỉnh bậc lẻ trong đồ thị bù của ?. 12. Gọi e là số cạnh, v là số đỉnh của đồ thị, t(i) là số đỉnh bậc i. chứng minh 2e  v = t(0) + t(2) + 2t(3) +...+ (k1)t(k).BÀI TẬP LOẠI 21. Chứng minh phần bù của đồ thị không liên thông phải liên thông.2. Chứng minh đồ thị có đúng hai đỉnh bậc lẻ chúng phải thuộc cùng thành phần liên thông.3. Chứng minh một đồ thị đơn giản v đỉnh, p thành phần liên thông có số cạnh tối đa là e  (vp)(vp+1)/2.4. Chứng minh một đồ thị đơn giản v đỉnh có số cạnh nhiều hơn (v1)(v2)/2 là liên thông.BÀI TẬP5. Chứng minh một đồ thị đơn giản v đỉnh có số cạnh nhiều hơn (v1)(v2)/2 là liên thông.6. Lấy , là hai đường khác nhau nối hai đỉnh của đồ thị . Chứng minh  là một chu trình hoặc tập hợp những chu trình trong .7. Chứng minh một đồ thị liên thông có 2k đỉnh bậc lẻ, khi đó tập hợp các cạnh có thể được phân hoạch vào k đường sao cho mọi cạnh được dùng đúng một lần. Điều kiện liên thông có cần thiết không hay có thể thay bằng một điều kiện yếu hơn ?.BÀI TẬP LOẠI 31. Đồ thị sau đẳng cấu với nhau hay không :??BÀI TẬP2. Đồ thị sau đẳng cấu với nhau hay không :??BÀI TẬP3. Đồ thị sau đẳng cấu với nhau hay không :BÀI TẬP4. Đồ thị sau đẳng cấu với nhau hay không :BÀI TẬP5. Đồ thị sau đẳng cấu với nhau hay không :BÀI TẬP6. Đồ thị sau đẳng cấu với nhau hay không :BÀI TẬP7. Đồ thị sau đẳng cấu với nhau hay không :BÀI TẬP8. Đồ thị sau đẳng cấu với nhau hay không :BÀI TẬP9. Tìm các đồ thị đẳng cấu với nhau.BÀI TẬP10. Liệt kê các đồ thị đơn giản có 4 đỉnh không đẳng cấu nhau.11. Xây dựng đồ thị 6 đỉnh với tính chất sau : a. 3 đỉnh bậc 3 và 3 đỉnh bậc 1. b. các đỉnh có bậc 1, 2, 2, 3, 4, 5. c. các đỉnh có bậc 2, 2, 4, 4, 4, 4. Nếu không thể xây dựng được hãy giải thích lý do.12. Tìm tất cả đồ thị đều bậc 3 không đẳng cấu nhau có :  a. 4 đỉnh. b. 5 đỉnh. c. 6 đỉnh. d. 8 đỉnh.BÀI TẬP13. Chứng minh hai đồ thị liên thông v đỉnh tất cả các đỉnh bậc 2 thì đẳng cấu.14. Độ liên thông đỉnh của đồ thị Kv là bao nhiêu ?.15. Độ liên thông cạnh của đồ thị Kv là bao nhiêu ?.16. Chứng minh đồ thị liên thông có 3 đỉnh trở lên có ít nhất 2 đỉnh không là đỉnh cắt.17. Chứng minh Đồ thị không khả tách  mọi cặp đỉnh thuộc một chu trình không giao nhau.BÀI TẬP18. Chứng minh : Một đồ thị đơn giản là không khả tách  mọi cặp cạnh trong đồ thị có một chu trình chứa chúng.19. Chứng minh một đồ thị v đỉnh có độ liên thông đỉnh là k phải có ít nhất kv/2 cạnh. Một trường hợp đặc biệt của kết quả này là bậc của mọi đỉnh trong đồ thị không khả tách ít nhất là 2.20. Mọi đồ thị đều bậc  3 là không khả tách ?.21. Xây dựng đồ thị có độ liên thông cạnh là 4, độ liên thông đỉnh là 3 và bậc của mọi định  5.BÀI TẬP22. Cho thí dụ hai đồ thị có cùng hạng và cùng độ không mà không đẳng cấu bậc 2.23. Hai đồ thị đẳng cấu cạnh nếu có một tương ứng 1-1trên giữa tập cạnh của chúng sao cho hai cạnh là kề trong đồ thị này nếu và chỉ nếu cũng kề trong đồ thị kia.24. Cho một thí dụ đồ thị đẳng cấu cạnh nhưng không đẳng cấu.BÀI TẬP LOẠI 41. Chỉ ra có 6 cây không đẳng cấu nhau có sáu đỉnh. a. 2 đỉnh bậc 1 b. 3 đỉnh bậc 1 c. 4 đỉnh bậc 1 d. 5 đỉnh bậc 12. Chứng minh trong cây mọi đỉnh có bậc lớn hơn 1 là đỉnh cắt.3. Cho đồ thị với , là hai cây phủ. Gọi H', K' là phần phụ cuả H, K. Chứng minh xHK'  yH'K, (H{x}){y}, (K{y}){x} là 2 cây phủ.BÀI TẬP4. Chứng minh mọi đồ thị con cuả đồ thị liên thông  được chứa trong một cây phủ nào đó cuả  không chứa chu trình.5. Có thể xây dựng một đồ thị nếu biết tất cả những cây phủ của nó ? tại sao ?.6. Chứng minh đồ thị có mọi đỉnh có bậc  2 phải chứa chu trình.7. Chứng minh đồ thị có n đỉnh và có ít nhất n cạnh phải chứa chu trình.BÀI TẬP8. Cây có 3 đỉnh bậc 2, 2 đỉnh bậc 3, 1 đỉnh bậc 4, những đỉnh còn lại bậc 1. Cây có bao nhiêu đỉnh. 9. Chứng minh mọi chu trình trong liên thông phải có ít nhất một cạnh chung với tập hợp các dây.10. Tìm hai cây phủ không đẳng cấu cuả K3,3.11. Độ không cuả đồ thị Kn là bao nhiêu ?.12. Chỉ rằng đường Hamilton là một cây phủ.BÀI TẬP13. Chứng minh độ không của một đồ thị không đổi nếu ta thêm một đỉnh vào giữa một cạnh hoặc nối liền thành một cạnh của hai cạnh tới đỉnh bậc 2. 14. Chứng minh bất kỳ một cạnh của đồ thị liên thông là một nhánh cuả một cây phủ nào đó của đồ thị. Điều này cũng đúng đối với một cạnh bất kỳ là một dây của một cây phủ nào đó ?.15. Chứng minh đồ thị không khả tách có độ không bằng 1  đồ thị là chu trình không giao nhau.BÀI TẬP LOẠI 51. Vẽ lại đồ thị trong hình sau để miền 2 trở thành miền vô hạn.BÀI TẬP2. Vẽ đồ thị đối ngẫu của đồ thị sau :BÀI TẬP3. Tìm K5 hoặc K3,3 trong các đồ thị sau :BÀI TẬP4. Tìm K5 hoặc K3,3 trong các đồ thị sau :BÀI TẬP5. Tìm K5 hoặc K3,3 trong các đồ thị sau :BÀI TẬP6. Tìm K5 hoặc K3,3 trong các đồ thị sau :BÀI TẬP7. Một đồ thị đơn giản phẳng tối đại nếu thêm vào một cạnh sẽ mất đi tính chất phẳng. Chứng minh mọi miền trong đồ thị đơn giản phẳng tối đại là tam giác.8. Cho một thí dụ chứng minh rằng không đẳng cấu với nhưng đẳng cấu bậc 2 với  ( là đối ngẫu cuả ).BÀI TẬP9. Chứng minh rằng K4 là tự đối ngẫu. Cho một thí dụ tự đối ngẫu khác.10. Nếu một đồ thị phẳng tất cả bậc 4 có 10 miền thì có bao nhiêu đỉnh ?.11. Chứng minh đồ thị phẳng liên thông có một đỉnh bậc  5. Có thể tổng quát hoá phát biểu trên vào trường hợp đồ thị phẳng bất kỳ (không liên thông).BÀI TẬP LOẠI 61. Tìm sắc độ cạnh của các đồ thị sau :ABCDEFABCDEBÀI TẬP2. Tìm sắc độ của các đồ thị sau :ABCDEFGHABCDEFGABCDEFGABCBÀI TẬP LOẠI 71. Tìm số lượng tăng tối đa của mỗi dòng sau :STAB1,53,32,4STAB1,51,32,4SCABT1,53,30,40,3BÀI TẬP2. Tìm một đường tăng dòng có giá trị 136. Có một đường tăng dòng khác hay không ?.AD38,50SCB40,40ETF36,3630,3040,4040,6048,4854,7013,1515,1510,2420,2022,2220,2012,1812,1216,30BÀI TẬP3. Trong mạng sau cung AD, BE, CD, ET là bảo hòa và dòng của các cung SA, SB, SC là như nhau. Tìm tất cả các dòng bị thiếu.AD?,2SCB?,5TE?,9?,6?,4?,4?,7?,3?,3?,2?,4BÀI TẬP4. Tìm tất cả đường tăng dòng và giá trị cực đại của chúng.AD5,10SC8,9TE1,12,47,79,103,62,42,5BÀI TẬP5. Aùp dụng thuật toán tìm dòng cực đại của dòng sau.AD2,5SC4,9TE2,77,87,99,100,52,7AD3SCB8TE9428749735265FHẾT BÀI TẬP