Page 76 - Modul Graf fix kali ya allaah
P. 76
Selanjutnya masih ada jalur yang bersilangan lainnya.
Perhatikan jalur (c,d) dapat digambar ulang dari kiri bawah,
menjadi seperti berikut:
Setelah ini, ternyata grafnya sudah tidak lagi memuat jalur
bersilangan. Misalnya graf terakhir ini kita beri nama graf H.
Diikarenakan graf G adalah graf yang memuat jalur
bersilangan dan dapat digambar ulang menjadi graf yang
tidak memuat jalur yang bersilangan, maka graf G disebut
graf planar, sedangkan graf H sebagai hasil penggambaran
ulangnya disebut dengan graf bidang dari graf planar G.
Contoh:
Ingat kembali graf bipartit komplit K3,3. Periksa apakah K3,3
planar?
P a g e 73 | 88
