Đồ thị đối ngẫu

Trong toán học, đồ thị đối ngẫu của một đồ thị mặt 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. Thuật ngữ "đối ngẫu" được dùng để chỉ tính đối xứng này: nếu H là đối ngẫu của G thì G cũng là đối ngẫu của H (nếu G liên thông).

Hình 1: G' là đồ thị đối ngẫu của G

Tính chất

Hình 2: G' và H' là hai đồ thị không đẳng cấu với nhau

• Đồ thị đối ngẫu của một đồ thị phẳng là một đa đồ thị phẳng và gồm nhiều cạnh.
• Nếu G là một đồ thị liên thông và G' là đồ thì đối ngẫu của G thì G và G' là 2 đồ thị đẳng cấu với nhau.
• Nếu G và H là hai đồ thị liên thông và là hai đồ thị đẳng cấu với nhau, G' và H' lần lượt là đồ thị đối ngẫu của G và H thì G' và H' có thể không đẳng cấu với nhau.^[1](Xem hình 2)

Cách xác định đồ thị đối ngẫu

Xác định đồ thị đối ngẫu từ một đồ thị phẳng

Bước1: 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 tứ giác ABCDE.

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.

Tương tự ta xét với tam giác BCE và tam giác ABE.

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.

• 
  Đồ thị phẳng G
• 
  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
• 
  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
• 
  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

Xác định đồ thị phẳng từ đồ thị đối ngẫu

Bước 1: Xác định các miền của đồ thị đối ngẫu. Ta có đồ thị đối ngẫu H, ta xác định được các miền như sau:

Miền trong gồm các điểm: A, B, D, E.

Miền ngoài gồm các điểm: C.

Bước 2: Nối các vùng tiếp xúc với nhau:

Nối vùng A với vùng B và E.

Nối vùng B với vùng A, C và E.

Nối vùng C với vùng B, D và E.

Nối vùng D với vùng C và E.

Kết luận: Gọi G' là đồ thị phẳng vừa tìm được, ta thấy từ một đồ thị đối ngẫu H, sẽ tìm được một đồ thị phẳng G' đẳng cấu với đồ thị phẳng G ban đầu.

• 
  Đồ thị đối ngẫu H và các miền
• 
  Nối vùng A với vùng B và E
• 
  Nối vùng B với vùng A, C và E
• 
  Nối vùng C với vùng B, D và E
• 
  Nối vùng D với vùng C và E

Một số ví dụ về đồ thị đối ngẫu của đường tròn

Đường tròn đơn

Hình 12: Đồ thị đối ngẫu đường tròn đơn.

Hai đường tròn tiếp xúc với nhau

Hình 13: Đồ thị đối ngẫu đường tròn tiếp xúc.

Hai đường tròn riêng biệt

Hình 14: Đồ thị đối ngẫu đường tròn riêng biệt.

Một số ví dụ về đồ thị đối ngẫu của hình học không gian

Đa giác

Tương ứng với mỗi mặt của đa giác sẽ có một điểm đại diện cho G’. Hai đỉnh trong được kết nối bởi một cạnh đồ thị nếu giữa hai mặt của đa giác có một ranh giới (cạnh) chung.

Hình tròn

Đồ thị đối ngẫu của hình tròn là một hình tròn.

• 
  Đồ thị đối ngẫu của đa giác trong không gian
• 
  Đồ thị đối ngẫu của hình tròn trong không gian

Đối ngẫu đại số

Giả sử G là một đồ thị liên thông, một đối ngẫu đại số của G là G' thì ta có:

• G và G' cùng tập hợp các cạnh (số cạnh bằng nhau).
• Mỗi chu trình của G đều cắt G' và ngược lại, mỗi chu trình của G' đều cắt G.

=>Như vậy, một đồ thị phẳng đều có đối ngẫu đại số, điều này đúng với giả thuyết của Hassler_Whitney: "Một đồ thị G là một đồ thị phẳng khi và chỉ khi G có đối ngẫu đại số".^[2]

Ứng dụng của đồ thị đối ngẫu

Giao thông

• Đồ thị đối ngẫu trong không gian phẳng là một phương thức xét các cạnh và các đỉnh và các đỉnh có liên quan đến nhau(có chung cạnh).
• Trong mạng lưới giao thông tại thành phố lớn, các đại lộ sẽ trở nên quá tải trong khi đó, nếu ta áp dụng đồ thị đối ngẫu vào hạ tầng giao thông thì sẽ tạo ra sự lưu thông trong thành phố.
• Sử dụng đồ thị đối ngẫu, phương thức đó đặc biệt có ích cho cấu trúc trong mạng lưới giao thông.
• Từ mô hình thực tế của mạng lưới giao thông ở thành phố(A), không gian, cách thức để suy xét đường đi khác biệt với truyền thống của lý thuyết đồ thị, khi cạnh là những đường đi từ vùng này qua vùng khác(nếu 2 vùng đó có cạnh chung với nhau).
• ở trong sơ đồ (B), đầu tiên ta khai báo tất cả các đường cơ bản (tên các con đường được xét theo một vài phẩm chất tiêu chuẩn khác nhau).
• Đồ thị đối ngẫu(C) đại diện cho mô hình giao thông thực tế tại thành phốtrên (thay mặt cho các đỉnh và các cạnh giao nhau).
• Nó cho phép phát hiện ra bản chất của cấu trúc ẩn của mặt phẳng cũng giống như thứ bậc truyền dữ liệu và kết nối trong mô hình mạng.

• 
  Mô hình giao thông thành phố thực tế
• 
  Mô tả mạng lưới giao thông qua các cạnh
• 
  Mô tả mạng lưới giao thông qua đồ thị đối ngẫu

Tô màu đồ thị

• Mỗi bản đồ trên mặt phẳng có thể biểu diễn bằng một đồ thị, trong đó mỗi miền của bản đồ được biểu diễn bằng một đỉnh; các cạnh nối hai đỉnh, nếu các miền được biểu diễn bằng hai đỉnh này là kề nhau. Đồ thị nhận được bằng cách này gọi là đồ thị đối ngẫu của bản đồ đang xét. Rõ ràng mọi bản đồ trên mặt phẳng đều có đồ thị đối ngẫu phẳng. Bài toán tô màu các miền của bản đồ là tương đương với bài toán tô màu các đỉnh của đồ thị đối ngẫu sao cho không có hai đỉnh liền kề nhau có cùng một màu, mà ta gọi là tô màu đúng các đỉnh của đồ thị.

Chú thích

1. Bondy, Adrian; Murty, U.S.R. (2008). “Planar Graphs”. Graph Theory. Graduate Texts in Mathematics. 244 (ấn bản thứ 2008). Springer. tr. 267. ISBN 9781846289699.
2. Whitney, Hassler (1932), “Non-separable and planar graphs”, Transactions of the American Mathematical Society, 34 (2): 339–362, doi:10.1090/S0002-9947-1932-1501641-2.

Tham khảo

1. http://www.eulerdiagrams.com/tutorial/VLHCC%202009%20Tutorial%202.1.pdf
2. http://www2.math.uu.se/~andersj/graphtheory/lec5.pdf
3. http://people.hofstra.edu/geotrans/eng/methods/dual_graph.html Lưu trữ 2013-11-25 tại Wayback Machine