Đồ 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).

Tính chất

Đồ 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.(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.

Hình:DoThiG.jpg|Đồ thị phẳng G
Hình:DoThiG2.jpg|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
Hình:DoThiG3.jpg|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
Hình:DoThiG4.jpg|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.

Hình:dtdnpic5.jpg|Đồ thị đối ngẫu H và các miền
Hình:dtdnpic1.jpg|Nối vùng A với vùng B và E
Hình:Dtdn2 2.jpg|Nối vùng B với vùng A, C và E
Hình:dtdnpic3.jpg|Nối vùng C với vùng B, D và E
Hình:dtdnpic5 1.jpg|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

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

Hai đườ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.

Hình:dtdnhkkg.jpg|Đồ thị đối ngẫu của đa giác trong không gian
Hình:dtdnht.jpg|Đồ 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ố".

Ứ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.

Hình:Dualgrap gt1.jpg|Mô hình giao thông thành phố thực tế
Hình:Dualgrap gt2.jpg|Mô tả mạng lưới giao thông qua các cạnh
Hình:Dualgrap gt3.jpg|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

Tham khảo
http://www.eulerdiagrams.com/tutorial/VLHCC%202009%20Tutorial%202.1.pdf
http://www2.math.uu.se/~andersj/graphtheory/lec5.pdf
http://people.hofstra.edu/geotrans/eng/methods/dual_graph.html