Đồ thị phẳng
Bách khoa toàn thư mở Wikipedia
Đồ thị được gọi là đồ thị phẳng nếu ta 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. Cách vẽ như vậy sẽ được gọi là biểu diễn phẳng của đồ thị. Ví dụ K4 là đồ thị phẳng.
Điều kiện cần và đủ để đồ thị là phẳng được chỉ ra trong định lí Kuratovski:
-
- Đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị con đồng phôi với K3,3 hoặc K5.
Đồ thị K3,3 và K5 không phải là đồ thị phẳng. Bài toán về tính phẳng của đồ thị K3,3 là bài toán ba căn hộ: xây dựng hệ thống cung cấp điện, hơi đốt và nước cho ba căn hộ sao cho mỗi căn hộ đều được nối với các nguồn cung cấp trên và đường dẫn của chúng không cắt nhau. Năm 1930, Kazimierz Kuratowski chứng minh rằng K3,3 là đồ thị không phẳng, tức là bài toán ba căn hộ không giải được.
Euler đã chứng minh được rằng các biểu diễn phẳng khác nhau của một đồ thì đều chia mặt phẳng ra thành cùng một số miền qua định lí sau (thường được gọi là công thức Euler):
-
- Giả sử G là đồ thị phẳng liên thông với n đỉnh, m cạnh. Gọi r là số miền của mặt phẳng bị chia bởi biểu diễn phẳng của G. Khi đó:
Một đồ thì được vẽ trên bề mặt S được gọi là nhúng trong S.
[sửa] Ứng dụng
Đồ thị phẳng có nhiều ứng dụng quan trọng trong công nghệ chế tạo mạch in. Biểu diễn phẳng của đồ thị sẽ chia mặt phẳng ra làm các miền, bao gồm cả miền không bị chặn.
Ngoài ra, một trong các ứng dụng là ánh xạ từ ảnh số 2 chiều sang một đồ thị phẳng. Trong đó, ảnh số được biểu diễn dưới dạng ma trận lưới ô vuông; mỗi ô đặc trưng cho 1 pixel. Đặc biệt với ảnh nhị phân, số giá trị có thể của pixel chỉ là hai.
