Teorema Kuratowski dan Sifat-Sifatnya

TEOREMA KURATOWSKI (Kashimir Kuratowski, Polandia) untuk menentukan keplanaran suatu graf.

1.       Teorema  Kuratowski :

    “ Graf  G bersifat  planar   jika  dan  hanya  jika ia tidak  mengandung  subgraf yang  sama  dengan  salah  satu  graf  kuratowski  atau  homomorfis  dengan  salah  satunya, atau Sebuah Graf G non Planar jika dan hanya jika G memuat sebuah graph bagian G yang hemeomorfik dengan graph K_3,3 atau K₅ “

2.      Sifat  GRAF Kuratowski adalah :

a)      Kedua graf  Kuratowski adalah graf  teratur.

b)      Kedua graf  kuratowski  graf  non-planar.

c)      Penghapusan sisi atau simpul dari graf  kuratowski  menyebabkan  menjadi  graf planar.

d)     K₅ adalah  graf  non-planar  dengan  jumlah  simpul  minimum,  K_3,3  adalah  graf  non-planar  dengan  jumlah  sisi  minimum  (Graf Kuratowski pertama adalah  graf  tidak-planar  dengan  jumlah  simpul  minimum, dan graf  Kuratowski  kedua  adalah  graf  tidak-planar  dengan  jumlah  sisi  minimum).

Graf  kuratowski berguna untuk menentukan dengan tegas keplanaran suatu graf.

Gambar :
(a) Graf  Kuratowski  pertama (K₅)
(b) Graf  Kuratowski  kedua (K_3,3)
(c) Graf  yang  isomorfik dengan graf  Kuratowski  kedua.

Graf  G bersifat planar jika dan hanya jika ia tidak mengandung upagraf yang isomorfik dengan salah satu graf Kuratowski atau homeomorfik (homeomorphic) dengan salah satu dari keduanya.

Gambar : Tiga buah graf yang homemorfik satu sama lain.
Contoh : Kita gunakan Teorema Kuratowski untuk memeriksa keplanaran graf. Graf G di bawah ini bukan graf  planar karena ia mengandung upagraf (G₁) yang sama dengan K_3,3.

Graf G tidak planar karena ia mengandung upagraf yang sama dengan K_3,3.
Graf G tidak planar karena ia mengandung upagraf (G₁) yang homeomorfik dengan K₅ (dengan membuang simpul-simpul yang berderajat 2 dari G₁, diperoleh K₅).

Gambar : Graf  G,  upagraf  G₁ dari  G  yang  homeomorfik dengan K₅.