Định lý Kuratowski

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Đồ thị phẳng

Định lý 1[sửa | sửa mã nguồn]

Đồ thị đủ K5 không phẳng.

Hình 1: Đồ thị đủ K5 không phẳng.

Định lý 2[sửa | sửa mã nguồn]

Đồ thị lưỡng phân đủ K3,3 không phẳng.

Hình 2: Đồ thị lưỡng phân đủ K3,3 không phẳng.
  • Nhận xét: hai đồ thị K5 và K3,3 là các đồ thị không phẳng đơn giản nhất với các tính chất sau
  1. Nếu xóa đi 1 đỉnh hay 1 cạnh của 2 đồ thị trên thì chúng ta sẽ có được đồ thị phẳng.
  2. Đồ thị K5 là đồ thị không phẳng có ít đỉnh nhất.
  3. Đồ thị K3,3 là đồ thị không phẳng có ít cạnh nhất.

Định lý 3[sửa | sửa mã nguồn]

  • Điều kiện cần và đủ để một đồ thị liên thông G có tính phẳng là G không chứa bất kỳ đồ thị con nào đồng phôi với K5 hay K3,3.
Hình 3: Định lý 3

Chú thích[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]