Matematika Diskrit : Keplanaran Suatu Graf

Rumus Euler

Sisi-sisi pada graf bidang membagi bidang datar menjadi beberapa wilayah (region) atau muka (face).

Graf bidang pada gambar di bawah ini terdiri atas 6 wilayah (termasuk wilayah terluar):

Hubungan antara jumlah simpul (n), jumlah sisi (e), dan jumlah wilayah (f) pada graf bidang:

n โ€“ e + f = 2 (Rumus Euler)

Pada Gambar di atas, e = 11 dan n = 7, f = 6, maka 7 โ€“ 11 + 6 = 2.

Pada graf planar sederhana terhubung dengan f buah wilayah, n buah simpul, dan e buah sisi (e > 2) selalu berlaku:

\[ e โ‰ค 3n – 6 \]


Dinamakan ketidaksamaan Euler, yang dapat digunakan untuk menunjukkan keplanaran suatu graf sederhana.

Bila suatu graf planar, maka ia memenuhi ketidaksamaan Euler.

Bila suatu graf tidak planar, maka ia tidak memenuhi ketidaksamaan tersebut.

Contoh :

Pada K4, n = 4, e = 6, memenuhi ketidaksamaan Euler, sebab 6 โ‰ค 3(4) โ€“ 6. Jadi, K4 adalah graf planar.

Pada graf K5, n = 5 dan e = 10, tidak memenuhi ketidaksamaan Euler sebab 10 โ‰ฅ 3(5) โ€“ 6. Jadi, K5 tidak planar.

Ketidaksamaan e โ‰ค 3n โ€“ 6 tidak berlaku untuk K3,3 karena

e = 9, n = 6

9 โ‰ค (3)(6) โ€“ 6 = 12 (jadi, e โ‰ค 3n โ€“ 6)

Padahal, graf K3,3 bukan graf planar.

Meskipun suatu graf planar sederhana memenuhi ketidaksamaan Euler, itu tidak menjamin keplanaran suatu graf.

Buat asumsi baru: setiap daerah pada graf planar dibatasi oleh paling sedikit empat buah sisi, dari penurunan rumus diperoleh e โ‰ค 2n – 4.

Contoh:

Graf K3,3 pada Gambar di bawah memenuhi ketidaksamaan e โ‰ค 2n โ€“ 4, karena

e = 9, n = 6

9 โ‰ค (2)(6) โ€“ 4 = 8 (salah)

yang berarti K3,3 bukan graf planar.


Teorema Kuratoswki

Berguna untuk menentukan dengan tegas keplanaran suat graf.

Keterangan:

(a) Graf Kuratowski pertama (K5)
(b) Graf Kuratowski kedua (K3,3)
(c) Graf yang isomorfik dengan graf Kuratowski kedua

Sifat graf Kuratowski:

  1. Kedua graf Kuratowski adalah graf teratur.
  2. Kedua graf Kuratowski adalah graf tidak-planar.
  3. Penghapusan sisi atau simpul dari graf Kuratowski menyebabkannya menjadi graf planar.
  4. Graf Kuratowski pertama adalah graf tidak-planar dengan jumlah simpul minimum, dan graf Kuratowski kedua adalah graf tidak-planar dengan jumlah sisi minimum.

Teorema Kuratowski: 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.

Keterangan: 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 (G1) yang sama dengan K3,3

Keterangan: Graf G tidak planar karena ia mengandung upagraf yang sama dengan K3,3

Graf G tidak planar karena ia mengandung upagraf (G1) yang homeomorfik dengan K5 (dengan membuang simpul-simpul yang berderajat 2 dari G1, diperoleh K5).

Keterangan: Graf G, upagraf G1 dari G yang homeomorfik dengan K5


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Graf, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up