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

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.

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.

=== 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:

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

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.

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

== Đố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ó:

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

=== 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ị.

==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