Chương 1 Một số kiến thức sơ lược về lý thuyết đồ thị Chương này trình bày sơ lược các khái niệm cơ bản của lý thuyết đồ thị để bổ trợ cho một số cách chứng minh công thức đặc trưng Euler dựa trên lý thuyết đồ thị trong chương sau. Nội dung chính của chương được tham khảo từ tài liệu [2,3,9]. Định nghĩa đồ thị 1. Định nghĩa 1 Đồ thị (graph) G = (V, E) là một bộ gồm các đỉnh V và các cạnh E, trong đó V 6= ∅ và mỗi cạnh nối với hai đỉnh (không nhất thiết phân biệt).
Nếu cạnh e tương ứng với hai đỉnh u, v thì ta nói u và v là hai đỉnh kề nhau. Hai cạnh phân biệt cùng tương ứng với một cặp đỉnh được gọi là hai cạnh song song hay cạnh bội. Cặp đỉnh không sắp thứ tự được gọi là cạnh vô hướng (cạnh). Cặp đỉnh sắp thứ tự được gọi là cạnh có hướng (cung).
Định nghĩa 2 Đồ thị G được gọi là đồ thị vô hướng nếu tất cả các cạnh của G đều là cạnh vô hướng.2 Bậc của một đỉnh trong đồ thị vô hướng là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Kí hiệu là: deg(v). - Đỉnh bậc 0 được gọi là đỉnh cô lập. - Đỉnh có bậc bằng 1 được gọi là đỉnh treo.
Cho đồ thị sau: Hình 1. Định nghĩa 3 Đồ thị G được gọi là đồ thị có hướng nếu tất cả các cạnh của G đều là cạnh có hướng. Định nghĩa 4 Đồ thị G1 được gọi là đồ thị con của đồ thị G nếu tập đỉnh và tập cạnh của G1 tương ứng là tập con của tập đỉnh và tập cạnh của G. Chu trình Đường đi (path) có độ dài n từ v0 đến vn với n là một số nguyên dương, trong một đồ thị vô hướng là một dãy các cạnh liên tiếp v0 v1 , v1 v2 ,.
Đỉnh v0 được gọi là đỉnh đầu, đỉnh vn được gọi là đỉnh cuối. Đường đi có đỉnh đầu trùng với đỉnh cuối gọi là chu trình. Chu trình đơn chứa tất cả các cạnh của đồ thị được gọi là chu trình Euler. Đồ thị vô hướng được gọi là đồ thị Euler nếu nó có chu trình Euler.5, đồ thị G1 có chu trình Euler: a, e, c, d, e, b, a.
Cả hai đồ thị G2 và G3 không có chu trình Euler. Một số dạng đồ thị 1. Đồ thị phẳng Đồ thị G là đồ thị phẳng nếu có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh. Đồ thị đối ngẫu 0 Đồ thị đối ngẫu của một đồ thị phẳng G là một đồ thị G trong đó có một đỉnh tương ứng cho mỗi miền mặt phẳng của đồ thị G và có mỗi cạnh tương ứng với mỗi cạnh của G kết nối hai miền kề nhau của G.7: Đồ thị đối ngẫu Xác định đồ thị đối ngẫu từ một đồ thị phẳng Bước 1: Xác định các miền của đồ thị phẳng.
Ta có đồ thị phẳng G, xác định các miền như sau: • Miền trong 1: Miền bị giới hạn bởi tam giác CDE. • Miền trong 2: Miền bị giới hạn bởi tam giác BCE. • Miền trong 3: Miền bị giới hạn bởi tam giác ABE. • Miền ngoài: Miền không bị giới hạn bởi hình ngũ giác ABCDE.8: Nối miền trong tam giác CDE với miền mà 3 cạnh DE , CD và CE tiếp xúc Bước 2: Xác định miền tiếp xúc với mỗi miền vừa xác định ở bước 1.
Xét tam giác CDE (miền trong 1) ta thấy: • Cạnh DE, CD tiếp xúc với miền ngoài. • Cạnh CE tiếp xúc với tam giác BCE (miền trong 2). Ta thực hiện vẽ các đường cong nối từ tam giác CDE sang miền ngoài và tam giác BCE. 10 Tương tự ta xét với tam giác BCE và tam giác ABE.9: Nối miền trong tam giác BCE với miền mà 3 cạnh BC , BE và CE tiếp xúc Bước 3: Gọi H là đồ thị mới vừa tìm được, ta có H là đồ thị đối ngẫu của G.10: Nối miền trong tam giác ABE với miền mà 3 cạnh AB , AE và BE tiếp xúc 1.
Đồ thị liên thông Một đồ thị liên thông nếu luôn tồn tại đường đi giữa mọi cặp đỉnh phân biệt của đồ thị.11 đồ thị G là liên thông và đồ thị H là không liên thông. Đơn đồ thị Đồ thị không có khuyên và cạnh bội được gọi là đơn đồ thị. Ngược lại, được gọi là đa đồ thị. Đồ thị đầy đủ Là đơn đồ thị bao gồm n đỉnh mà mọi đỉnh đều có bậc n − 1 (mỗi đỉnh đều nối với n − 1 đỉnh còn lại).
Đồ thị phân đôi đầy đủ Là đơn đồ thị trong đó: - Các đỉnh của đồ thị chia làm hai tập con. - Mỗi cạnh nối một đỉnh từ tập này đến một đỉnh ở tập kia. 12 Kí hiệu: Km,n Ví dụ. Cây Cây là một đồ thị mà trong đó hai đỉnh bất kì đều được nối với nhau bằng đúng một đường đi.
Cây là đồ thị vô hướng, liên thông và không có chu trình đơn.14: Cây Cây bao trùm (spanning tree) còn được gọi là cây khung của đồ thị G là cây con của đồ thị G , chứa tất cả các đỉnh của G. Hay nói cách khác, cây bao trùm của một đồ thị G là một đồ thị con của G, chứa tất cả các đỉnh của G, liên thông và không có chu trình. Cây khung của đồ thị liên thông G là một đồ thị con liên thông nhỏ nhất của G.15: Cây khung 14 Chương 2 Một số cách chứng minh công thức đặc trưng Euler Chương này trình bày một số cách chứng minh công thức đặc trưng Euler. Chứng minh dựa trên lý thuyết đồ thị Biểu diễn phẳng của một đồ thị chia mặt phẳng thành các miền, kể cả miền vô hạn.
Ví dụ biểu diễn phẳng của đồ thị trên hình 2.1 chia mặt phẳng thành 6 miền. Chúng được gán nhãn như hình vẽ.1 Euler đã chứng minh rằng tất cả các biểu diễn phẳng của một đồ thị đều chia mặt phẳng thành cùng một số miền như nhau. Ông đã tìm ra mối quan hệ giữa số miền, số đỉnh và số cạnh của một đồ thị phẳng. Khi đó công thức đặc trưng Euler đối với đồ thị phẳng được phát biểu như sau Định lí.
Nếu G là một đồ thị phẳng liên thông có V đỉnh, E cạnh và F 15 miền thì V − E + F = 2. Sau đây là một số cách chứng minh công thức đặc trưng Euler dựa trên cơ sở lý thuyết đồ thị. Gọi G là một đơn đồ thị phẳng liên thông với E cạnh và V đỉnh. Gọi R là số miền trong biểu diễn phẳng của G.
Cần chứng minh R = E − V + 2. Trước tiên ta xác định biểu diễn phẳng của G. Ta sẽ chứng minh bằng cách xây dựng một dãy các đồ thị con G1 , G2 , ., Ge = G, mỗi bước ghép thêm một cạnh vào đồ thị ở bước trước. Điều này làm được khi sử dụng phương pháp quy nạp toán học như sau.
Lấy tùy ý một cạnh của G để nhận được G1. Để nhận được Gn từ Gn−1 ta thêm tùy ý một cạnh liên thuộc với một đỉnh của Gn−1 và thêm một đỉnh khác liên thuộc với cạnh mới đó, nếu nó chưa có trong Gn−1. Điều này làm được vì G liên thông. G sẽ nhận được sau khi e cạnh được ghép thêm vào các đồ thị tạo ra trước.
Gọi Rn , En và Vn tương ứng là số miền, số cạnh và số đỉnh của biểu diễn phẳng của Gn do biểu diễn phẳng của G sinh ra. Ta sẽ chứng minh bằng quy nạp. Với n = 1, hệ thức R1 = E1 − V1 + 2 là đúng với G1 vì E1 = 1, V1 = 2 và R1 = 1.2 Giả sử Rn = En − Vn + 2. Gọi {an+1 , bn+1 } là cạnh gộp vào Gn để được Gn+1.
Có hai khả năng xảy ra. Trường hợp 1. Cả hai đỉnh an+1 , bn+1 đã thuộc Gn. Khi đó chúng phải ở trên biên của miền chung R nếu không thì không thể gộp cạnh {an+1 , bn+1 } vào Gn mà không có các cạnh cắt nhau (Gn+1 là phẳng).
Cạnh mới này sẽ chia miền R thành hai miền con.3 Do đó Rn+1 = Rn + 1, En+1 = En + 1 và Vn+1 = Vn. Vì vậy ta có công thức Rn+1 = En+1 − Vn+1 + 2. Trường hợp 2. Một trong hai đỉnh an+1 , bn+1 chưa thuộc Gn .4 Giả sử an+1 thuộc Gn còn bn+1 không thuộc Gn.
Thêm cạnh này không sinh ra một miền mới nào, vì bn+1 phải ở trong miền có an+1 ở trên biên của nó. Do đó, Rn+1 = Rn. Nhưng En+1 = En + 1 và Vn+1 = Vn + 1. Vì vậy Rn+1 = En+1 − Vn+1 + 2.
Vậy với mọi n ta đều có Rn = En − Vn + 2. Vì đồ thị gốc là Ge nhận được sau khi thêm e cạnh, Định lí được chứng minh. Công thức Euler được minh họa trong ví dụ sau: Ví dụ 2.1 Giả sử đơn đồ thị phẳng liên thông có 20 đỉnh, mỗi đỉnh đều có bậc bằng 3. Biểu diễn phẳng của đồ thị này chia mặt phẳng thành bao nhiêu miền? Giải.
Đồ thị phẳng này có 20 đỉnh, mỗi đỉnh đều có bậc bằng 3, do 17 vậy V = 20. Vì tổng số bậc của các đỉnh, 3V = 3.20 = 60, bằng hai lần số cạnh, tức là 2E, ta có E = 60 : 2 = 30. Do vậy theo công thức Euler, số các miền là R = E − V + 2 = 30 − 20 + 2 = 12. Đồ thị trong Hình 2.5 có năm đỉnh, bảy cạnh, bốn miền và 5 − 7 + 4 = 2.5 Nếu không tính vùng không giới hạn là miền thì công thức Euler trở thành V − E + F = 1.
Xét một cây (một đồ thị phẳng liên thông và không có chu trình). Vì cây không có chu trình, miền duy nhất là miền không bị giới hạn, nên công thức Euler V − E + 1 = 2 hay V = E + 1. Do đó, số đỉnh của cây lớn hơn số cạnh 1 đơn vị. Ta dùng cách loại bỏ các cạnh ra khỏi đồ thị để chứng minh định lí.
Xét một đồ thị phẳng liên thông. Chọn một cạnh bất kì. Cạnh có thể liên thuộc hai đỉnh hoặc là một khuyên.6 18 Giả sử cạnh liên thuộc hai đỉnh. Ta thu nhỏ cạnh cho đến khi nó biến mất hoàn toàn và trở thành một đỉnh.
Điều này có thể thực hiện trong đồ thị phẳng (xem loại bỏ cạnh a, c, d trong Hình 2.