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[sửa | sửa mã nguồn]
- Đồ 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[sửa | sửa mã nguồn]
Xác định đồ thị đối ngẫu từ một đồ thị phẳng[sửa | sửa mã nguồn]
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[sửa | sửa mã nguồn]
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[sửa | sửa mã nguồn]
Đường tròn đơn[sửa | sửa mã nguồn]
Hai đường tròn tiếp xúc với nhau[sửa | sửa mã nguồn]
Hai đường tròn riêng biệt[sửa | sửa mã nguồn]
Một số ví dụ về đồ thị đối ngẫu của hình học không gian[sửa | sửa mã nguồn]
Đa giác[sửa | sửa mã nguồn]
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.