plagiat merupakan tindakan tidak terpuji graf … · contoh graf lengkap k 4 dan graf bipartite...

65
GRAF PLANAR Skripsi Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika Oleh: Josef Arnoldus Ruba NIM : 003114015 PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SANATA DHARMA YOGYAKARTA 2007 i PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Upload: phungkhue

Post on 02-Mar-2019

250 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

GRAF PLANAR

Skripsi

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains

Program Studi Matematika

Oleh: Josef Arnoldus Ruba

NIM : 003114015

PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SANATA DHARMA YOGYAKARTA

2007

i

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 2: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

ii

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 3: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

iii

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 4: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

Skripsi ini Kupersembahkan untuk:

My Almighty Jesus Christ yang selalu mendampingiku

Mama dan Papa tercinta

yang senantiasa mendoakan setiap Langkahku

My Lovely Brother’s and Sister’s

Kakek dan Nenekku

Semua keluarga dan

Sahabat-sahabatku

”Pada hari aku berseru, Engkaupun menjawab aku,

Engkau menambahkan kekuatan dalam jiwa ku”

(Mazmur 138 : 3)

iv

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 5: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

ABSTRAK Suatu graf G disebut graf planar jika dapat digambarkan pada bidang tanpa adanya

ruas yang berpotongan, kecuali simpul dimana mereka bertemu.

Dalam tulisan ini akan dibahas karakterisasi graf planar.Salah satunya adalah bahwa

sebuah graf G adalah planar jika dan hanya jika G tidak mengandung subgraf yang

isomorfik dengan K5 atau K3,3 atau sebuah bagian dari K5 atau K3,3.

v

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 6: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

ABSTRACT

A graph G is called planar graph if it can be drawn in a plane without any

edges which is intersected, except at a vertex to which they are incident. In this thesis

will be discussed the characterizations of the planar graph. One of them is that a

graph G is planar if and only if G contains no subgraph which is isomorphic to or

, or a subdivision of or

5K

3,3K 5K .3,3K

vi

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 7: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

KATA PENGANTAR

Dengan mengucap puji dan syukur Tuhan Yang Maha Esa yang telah

memberikan rahmat-Nya sehingga skripsi yang berjudul “Graf Planar” ini dapat

diselesaikan dengan baik.

Penyusunan skripsi ini dimaksudkan untuk memenuhi salah satu persyaratan

untuk memperoleh gelar Sarjana Sains (S.Si) pada Fakultas Matematika dan Ilmu

Pengetahuan Alam Universitas Sanata Dharma.

Pada kesempatan ini juga penulis mengucapkan banyak terima kasih pada

berbagai pihak yang telah ikut membantu dalam menyelesaikan Makalah ini,

khususnya pada:

1. My hero Jesus Christ dan Holy Mary yang selalu mendampingiku disaat susah

maupun senang.

2. M. V. Any Herawati, S.Si.,M.Si, selaku dosen pembimbing dan Dosen

Matematika Universitas Sanata Dharma

3. Y.G. Hartono, S.Si. M.Sc, selaku Kepala Program Studi Matematika.

4. Ir. Ig. Aris Dwiatmoko, M.Sc, selaku Dekan Fakultas Matematika dan Ilmu

Pengetahuan Alam.

5. Maria Agustiani, S.Si, M.Si.(Alm), selaku Dosen matematika yang selalu

memberikan semangat dan dorongan.

vii

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 8: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

6. Seluruh Dosen Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas

Sanata Dharma

7. Ibu Warni, Pak Tukijo, dan Ibu Erma selaku staf administrasi FMIPA

Universitas Sanata Dharma.

8. Mama, Papa dan Adik-adikku Kons, Marlin, Lius, Elfrida Atas semua doa,

kasih sayang, dan dorongannya. Buat Mama dan Papa terima kasih atas semua

kepercayaan dan cinta yang selalu kalian berikan walaupaun terkadang aku

selalu mengecewakan kalian.

9. Tante Mia tercinta yang selalu membrikan doa dan dukungannya.

10. Tante Elis dan Om Lius atas bantuannya selama ini.

11. Suster Kristofora KKS dan kongregasi, terimakasih atas tempat tinggal dan

dukungannya.

12. Om Sil Ratu dan keluarga.

13. My best friend Tika, sahabatku dari pertama kali aku kuliah sampai

sekarang.Semangat tik, aku tau suatu hari semua yang kamu cita-citakan akan

berhasil,jangan putus asa.

14. Teman-temanku di matematika angkatan 2000 terimakasih atas kebersamaan

kalian dan hari-hari yang indah selama menjalani perkuliahan

15. Teman-teman tercintaku Sinta(thanx ya atas semua pengertian dan

dorongannya, jangan bosen jadi tempat curhatku), Nissa(semangat Nis kamu

bisa!!), Devi, Diah, Hendi, Pri, Mayang(terima kasih pinjaman motornya dan

bantuin ngedit), Desi( Thanx dah mau menerima semua keadaanku, cepet

Pulang kita dugem lagi), Beny(dUgem yok!!), Nadi(Thanx abstracnya).

viii

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 9: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

16. My best friend Ical thanx ya bro dah selalu support aku, ayo cepet lulus.

17. Teman-temanku di edutaiment vesta Oktan, Diaz, Ryan, Ebel, Hery, Enox,

Agus, Bayu, keep on dancing!!!!.

18. Untuk semua teman-teman yang belum bisa kusebutkan satu-persatu

terimakasih banyak atas semua bantuannya selama ini.

Penulis menyadari bahwa tugas akhir ini jauh dari sempurna, oleh sebab itu

penulis mengharapkan saran dan kritik yang membangun. Akhir kata penulis

berharap semoga dengan tersusunnya makalah ini dapat bermanfaat bagi mahasiswa

Jurusan matematika khususnya dan bagi Mahasiswa Universitas Sanata Dharma pada

umumnya.

Yogyakarta, 2007

Penulis

(Josef Arnoldus Ruba)

ix

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 10: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

PERNYATAAN KEASLIAN KARYA

Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini tidak

memuat karya atau bagian karya orang lain, kecuali yang telah disebutkan dalam

kutipan daftar pustaka, sebagaimana layaknya karya ilmiah.

Yogyakarta, 2007

Penulis

Josef Arnoldus Ruba

x

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 11: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

DAFTAR ISI

HALAMAN JUDUL .....................................................................................................i

HALAMAN PERSETUJUAN PEMBIMBING ...........................................................ii

HALAMAN PENGESAHAN .....................................................................................iii

HALAMAN PERSEMBAHAN ..................................................................................iv

ABSTRAK ....................................................................................................................v

ABSTRACT ................................................................................................................vi

KATA PENGANTAR ................................................................................................vii

PERNYATAAN KEASLIAN KARYA ......................................................................x

DAFTAR ISI .............................................................................................................. xi

BAB I PENDAHULUAN ...............................................................................1

A. Latar belakang masalah ..................................................................1

B. Perumusan masalah ........................................................................2

C. Manfaat penulisan ...........................................................................2

D. Metode penulisan ............................................................................2

E. Sistematika penulisan......................................................................3

BAB II GRAF....................................................................................................4

A.Graf....................................................................................................4

B. Perjalanan, perjalanan kecil, lintasan dan putaran........................... 7

C. Derajat suatu graf.......................................................................... 11

xi

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 12: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

BAB III GRAF PLANAR............................................................................... 27

A. Graf planar ....................................................................................27

B. Formula Euler untuk graf planar....................................................30

C. Karakterisasi dari graf planar........................................................ 40

BAB IV PENUTUP ........................................................................................ 52

Kesimpulan .........................................................................................52

DAFTAR PUSTAKA

xii

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 13: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

BAB I

PENDAHULUAN

A. LATAR BELAKANG MASALAH

Dalam berbagai masalah yang berkaitan dengan relasi biner, representasi

grafik seringkali merupakan bentuk penyajian yang memudahkan. Hal inilah

yang mendasari pembelajaran tentang teori graf.

Secara umum graf dapat digambarkan dengan berbagai macam cara,sebagai

contoh graf lengkap K4 dan graf bipartite lengkap K3,3 bisa digambarkan

sebagai berikut.

Dalam menggambarkan suatu graf yang menjadi masalah adalah bagaimana

menentukan apakah suatu graf bisa digambarkan pada suatu bidang rata tanpa

adanya ruas yang berpotongan. Hal inilah yang mendasari penulis untuk

membahas mengenai graf planar. Graf planar merupakan salah satu bagian

dari topik teori graf. Seperti yang telah didefinisikan, graf planar ialah suatu

graf yang dapat digambarkan tanpa adanya ruas yang berpotongan. Pada

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 14: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

2

contoh diatas graf lengkap K4 merupakan graf planar, sedangkan graf bipartite

lengkap K3,3 merupakan graf non planar.

B. PERUMUSAN MASALAH

Sifat-sifat apa yang berlaku pada graf planar?

C. MANFAAT PENULISAN

Manfaat yang diharapkan dari penulisan ini adalah untuk memperdalam

pemahaman tentang graf planar.

D. METODE PENULISAN

Metode yang digunakan adalah metode studi pustaka yaitu mempelajari

buku-buku yang berkaitan dengan graf planar sehingga didalam skripsi ini

tidak ditemukan hal-hal yang baru.

E. SISTEMATIKA PENULISAN

BAB I PENDAHULUAN

A. Latar Belakang Masalah

B. Perumusan Masalah

C. Manfaat Penulisan

D. Metode Penulisan

E. Sistematika Penulisan

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 15: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

3

BAB II GRAF

A. Graf

B. Perjalanan,Perjalanan kecil,Lintasan,dan Putaran

C. Derajat suatu Graf

BAB III GRAF PLANAR

A. Graf Planar

B. Formula Euler untuk Graf Planar

C. Karakterisasi dari graf planar

BAB IV PENUTUP

Kesimpulan

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 16: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

BAB II

GRAF Dalam bab ini akan dijelaskan mengenai graf yang menjadi dasar dalam

mempelajari tentang graf planar pada bab 3. Definisi mengenai graf akan

diberikan berikut ini. Pada bab ini juga akan diberikan hal-hal yang berkaitan

dengan graf.

A.Graf

Definisi 2.1

Suatu graf G, lengkapnya G (V,E) terdiri atas 2 himpunan :

1. Himpunan V, yang elemen-elemennya disebut simpul (vertex).

Himpunan V elemen-elemennya berhingga tetapi tidak kosong.

2. Himpunan E , yang merupakan himpunan pasangan tidak terurut

dari simpul-simpul elemen V yang disebut ruas (edge).

3. Setiap ruas terletak antara dua simpul.

Graf dapat digambarkan pada bidang datar, simpul digambarkan sebagai simpul,

sedangkan ruas digambar sebagai kurva yang menghubungkan dua simpul.

Banyaknya simpul dari sebuah graf disebut order, ditulis n(G) sedangkan

banyaknya ruas dari sebuah graf G disebut ukuran (size), ditulis m(G).Suatu (n,m)

graf mempunyai order n dan ukuran(size) m.

Contoh 2.1 :

Misal G adalah graf dengan V = {v1,v2,v3,v4} dan E = {e1,e2,e3,e4,e5} dimana

e1=(v1,v4), e2=(v1,v2), e3=(v2,v3), e4= (v3,v4), e5=(v1,v3).n=4 dan m=5

Maka G dapat digambarkan seperti gambar 2.1.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 17: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

5

Definisi 2.2

Dua atau lebih ruas yang menghubungkan pasangan simpul yang sama disebut

ruas ganda, dan sebuah ruas yang menghubungkan suatu simpul dengan simpul

itu sendiri disebut loop. Suatu graf yang tidak mempunyai loop atau ruas ganda

disebut graf sederhana.

Contoh 2.2 :

Dalam gambar 2.2, e1 dan e2 adalah ruas ganda sedangkan e5 adalah loop.

Graf tersebut bukan graf sederhana.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 18: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

6

Definisi 2.3

Dua simpul yang langsung dihubungkan oleh suatu ruas disebut simpul-simpul

yang adjacent (bertetangga).

Definisi 2.4

Dua buah graf G(E,V) dan G*(E*,V*) disebut isomorfik, jika G*(E*,V*) dapat

diperoleh dengan memberi nama simpulnya lagi, yaitu jika ada korenspondensi

satu-satu antara simpul G(E,V) dan simpul G*(E*,V*), sedemikian hingga banyak

sisi yang menghubungkan setiap pasang simpul G(E,V) sama dengan banyak sisi

yang menhubungkan pasangan simpul yang berkorespondensi di G*(E*,V*).

Dua graf G1 dan G2 yang isomorfik dinotasikan dengan G1 ≈ G2 .

Contoh 2.3 :

v4

3

21

241

3

Gambar 2.3

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 19: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

7

B. Perjalanan, Perjalanan Kecil, Lintasan, dan Putaran

Definisi 2.6

Perjalanan (walk) pada suatu graf G ialah barisan simpul dan ruas yang

bergantian, dimulai dan diakhiri dengan simpul, dimana setiap ruas bertemu

dengan simpul di kanan kirinya.

Contoh 2.4 :

v1

v5

v4

v2

v3

e1e2

e4e3

e5

e6e7

Gambar 2.4

Pada graf G di atas contoh perjalanan ialah lintasan P v1e3v3e4v4e4v3 dan biasa

ditulis perjalanan v1-v3 .

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 20: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

8

Menyajikan suatu perjalanan dapat dilakukan dengan hanya menulis simpul-

simpul yang dilaluinya, sehingga perjalanan di atas dapat ditulis v1v3v4v3 (ruas-

ruas tidak ditulis).

Dalam suatu perjalanan simpul dan ruas boleh di ulang (dapat muncul lebih dari

satu kali).

Apabila simpul awal sama dengan simpul akhir maka perjalanan itu disebut

tertutup, contohnya v1v3v4v3v2v3v1 pada graf G dalam gambar 2.4 diatas. Apabila

tidak demikian maka perjalanannya disebut terbuka.

Definisi 2.7

Perjalanan kecil (trail) adalah perjalanan dimana semua ruas dalam barisan

tersebut berbeda (tidak diulang), tetapi simpul-simpul boleh diulang.

Contoh 2.5 :

Perjalanan kecil pada graf G dalam gambar 2.4 di atas adalah v1v2v3v1v4. Tampak

bahwa semua ruas yang dilalui berlainan tetapi v1 diulang.

Definisi 2.8

Lintasan (path) ialah suatu perjalanan kecil dimana semua simpul-simpulnya

berlainan (kecuali jika perjalanan kecil itu itu tertutup sehingga simpul awal sama

dengan simpul akhir).

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 21: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

9

Contoh 2.6 :

Lintasan pada graf G dalam gambar 2.4 di atas ialah lintasan Q = v1v2v3v4 dan

biasa ditulis lintasan v1-v4 .

Berdasarkan definisi-definisi diatas maka : Pada suatu perjalanan, simpul maupun

ruas boleh diulang. Pada suatu perjalan kecil, simpul-simpulnya boleh diulang,

namun ruas-ruasnya semua berlainan. Sedangkan pada suatu lintasan, simpul-

simpul maupun ruas-ruasnya semua berlainan (kecuali lintasan tertutup).

Definisi 2.9

Putaran (cycle ) adalah suatu lintasan yang tertutup.

Jika putaran itu mempunyai 3 ruas maka disebut segitiga.

Contoh 2.7 :

Gambar 2.5

Pada graf tersebut salah satu putaran adalah v1v2v3v4v1.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 22: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

10

Definisi 2.10

Panjang suatu perjalanan ialah banyaknya ruas yang muncul pada perjalanan itu.

Suatu ruas yang muncul dua atau tiga kali, dihitung dua atau tiga kali juga pada

perhitungan panjang perjalanan itu.

Sebagai catatan bahwa panjang tidak ditentukan dengan menggunakan sentimeter

melainkan dengan menggunakan definisi di atas.

Contoh 2.8 :

v1

v5

v4

v2

v3

e1e2

e4e3

e5

e6e7

G

Gambar 2.6

Perjalanan pada graf G dalam gambar 2.6 misalnya v1v2v3v1v3v4 memilki

panjang 5.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 23: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

11

Teorema 2.1

Tiap perjalanan u-v dalam graf mengandung lintasan u-v.

Bukti:

Misal W sebuah adalah perjalanan u-w dalam graf G.Jika W tertutup, jelas

mengandung lintasan. Diberikan W:u=u0,u1,u2,…,uk=v sebuah perjalanan terbuka

u-v dari graf G.Jika tidak ada simpul dari G terdapat dalam W lebih dari

sekali,maka W adalah lintasan u-v. Dilain pihak,jika terdapat simpul dari G yang

terdapat dalam W dua kali atau lebih.

Misal i dan j bilangan positif yang berbeda,dengan i≤ j, sedemikian hingga

ui=uj.Jika ui,ui+1,…,uj-1 dihapus dari W, sebuah perjalanan u-v, diperoleh memiliki

simpul lebih sedikit dari W. Jika tidak terdapat pengulangan dari simpul-simpul

dalam W1, maka W1 adalah lintasan u-v. Jika terdapat pengulangan simpul dalam

W1, lanjutkan langkah di atas sampai akhirnya mendapatkan perjalanan u-v yang

mengandung lintasan u-v. ■

C. Derajat Suatu Graf

Definisi 2.11

Derajat (degree) suatu simpul adalah banyaknya ruas yang bertemu di simpul itu.

Sedangkan jumlah derajat semua simpul graf G disebut derajat Graf G.

Derajat terkecil dari suatu graf G adalah derajat terkecil dari simpul-simpul dari

G, biasa dituliskan dengan δ(G). Sedangkan derajat terbesar dari suatu graf G

adalah derajat terbesar dari simpul-simpul dari G,biasa ditulis dengan Δ(G) .

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 24: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

12

Contoh 2.9 :

v1

v5

v4

v2

v3

e1e2

e4e3

e5

e6e7

G

Gambar 2.7

Pada graf G diatas derajat (degree) dari v1 (disingkat deg v1) adalah 4, deg v2 = 2,

deg v3 = 2, deg v4 = 3, dan deg v5 = 2. δ(G)=2 dan Δ(G)=4

Teorema 2.2 (The Handshaking Lemma)

Hasil penjumlahan derajat-derajat dari semua simpul pada setaip graf adalah sama

dengan dua kali banyaknya ruas dari graf tersebut.

Apa bila banyaknya simpul dari graf G di sajikan dengan huruf n dan banyaknya

ruas disajikan dengan huruf m ( disingkat suatu (n,m) graf ) maka teorema 2.1

diatas dapat disajikan dengan rumus :

∑ deg vi = 2m

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 25: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

13

Bukti :

Menurut definisi 2.1 datum 3 tentang konsep graf, setiap ruas terletak antara dua

simpul. Sehingga sumbangan tiap ruas pada ∑ deg vi adalah 2. Karena banyaknya

ruas adalah m maka di dapat ∑ deg vi = 2m. ■

Definisi 2.12

Suatu simpul dengan derajat nol disebut simpul terasing (isolated vertex)

sedangkan simpul dengan derajat satu disebut simpul akhir (end vertex).

Definisi 2.13

Sebuah graf sebuah graf G adalah beraturan dengan derajat r jika deg v=r untuk

tiap simpul v dari G.

Contoh 2.10 :

Dibawah ini disajikan graf-graf beraturan dengan derajat masing- masing simpul

0, 1, dan 3.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 26: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

14

Gambar 2.8

Suatu fakta yang harus diperhatikan adalah bahwa pada suatu putaran,

banyaknya simpul = banyaknya ruas.

Contoh 2.11 :

C5 : Putaran dengan 5 simpul dan 5 ruas

Gambar 2.9

Definisi 2.14

Graf G disebut terhubung (connected) jika dan hanya jika setiap dua simpul yang

berlainan dihubungkan dengan sekurang-kurangnya satu lintasan.

Apabila tidak demikian, yaitu jika ada dua simpul yang tidak dihubungkan dengan

suatu lintasan, graf itu disebut tidak terhubung (disconnected).

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 27: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

15

Contoh 2.12 :

Gambar 2.10

Definisi 2.15

Suatu graf G disebut lengkap (complete) jika setiap dua simpulnya bertetangga.

Jadi suatu graf lengkap berorder n dan berukuran m adalah sebuah graf beraturan

berderajat n-1 dan mempunyai m=n(n-1)/2, dan graf ini ditulis dengan Kn.

Contoh 2.13 :

Graf K5

Gambar 2.11

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 28: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

16

Definisi 2.16

Suatu graf G disebut bipartite (disingkat bigraf) jika dan hanya jika dipenuhi :

1. Himpunan simpul-simpul dari G dapat dipisahkan atas dua himpunan V1

dan V2 yang saling asing ( V1∩V2 = φ ).

2. Setiap ruas x dari G menghubungkan simpul di V1 dengan simpul di V2.

Sehingga tidak ada simpul-simpul di V1 yang terhubungkan satu dengan

yang lain. Demikian juga dengan simpul-simpul di V2.

Apabila setiap simpul di V1 bertetangga dengan setiap simpul di V2 maka disebut

bipartite lengkap graf. Jika V1 mempunyai m simpul dan V2 mempunyai n simpul

maka complete bipartite tersebut disajikan dengan Km,n . Bigraf lengkap K1,n

disebut “star” (bintang).

Contoh 2.14 :

Graf bipartite

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 29: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

17

Graf bipartite lengkap

Gambar 2. 12

Definisi 2.17

Suatu pohon (tree) adalah graf terhubung yang tidak memuat putaran

(cycle).

Contoh 2.15 :

Pohon

Gambar 2.13

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 30: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

18

Definisi 2.18

Misal suatu graf G dengan himpunan simpul V dan himpunan ruas E. Suatu

subgraf dari G adalah graf yang semua simpulnya menjadi bagian dari V dan

semua ruasnya menjadi bagian dari E.

Contoh 2.16 :

Jika G suatu graf terhubung dibawah ini, dimana V = {v1,v2,v3,v4 } dan

E = { e1,e2,e3,e4,e5 } dengan e1 = (v1,v2), e2 = (v1,v3), e3 = (v2,v4), e4 = (v2,v3),

e5 = (v3,v4) maka graf berikut ini adalah subgraf dari G.

4

Graf G

Gambar 2.14

Gambar 2.15

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 31: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

19

V = {v1,v2,v3,v4}

E = {e1,e2,e3} dimana e1= (v1,v3 ), e2 = (v2,v3 ), e3 = (v3,v4 )

Gambar 2.15 merupakan subgraf dari graf G di atas.

Definisi 2.19

Jika U adalah subhimpunan tidak kosong dari himpunan simpul V(G) dari graf G,

maka subgraf ⟨U⟩ dari G diinduksi oleh U adalah graf yang memiliki simpul U

dan yang himpunan ruasnya terdiri dari ruas-ruas dari G yang bertemu dengan dua

anggota dari U.

Sebuah subgraf H dari G disebut simpul-induksi atau diinduksi sederhana jika

H = ⟨U⟩ untuk suatu subhimpunan U dari V(G).

Contoh 2.17:

V(G) = {v1,v2,v3,v4,v5,v6}

⟨U⟩ = {v1,v2,v5}

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 32: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

20

⟨U⟩ :

Gambar 2.16

Definisi 2.20

Graf trivial adalah graf yang tidak memiliki ruas.

Definisi 2.21

Misal G suatu graf terhubung. Suatu pohon penyangga (spanning tree) pada G

adalah suatu subgraf dari G yang memuat semua simpul dari G dan juga

merupakan suatu pohon. Ruas dari pohon disebut cabang (branches).

Contoh 2.18 :

xyz

v w

z y x

wv

graf G pohon penyangga

Gambar 2.17

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 33: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

21

Definisi 2.22

Sebuah simpul dari graf terhubung adalah cut-vertex jika penghapusannya

menghasilkan graf yang tidak terhubung.

Teorema 2.3

Sebuah simpul v dari graf G disebut cut-vertex jika dan hanya jika terdapat

simpul-simpul u dan w (u,w≠ v) dimana v berada dalam tiap lintasan u-w dari G.

Bukti:

Cukup dibuktikan untuk graf terhubung. Misal v sebuah cut-vertex dari G;maka

graf G − v tidak terhubung. Jika u dan w simpul-simpul dalam komponen berbeda

dari G − v, maka tidak terdapat lintasan u-w dalam G − v. Bagaimanapun,karena G

terhubung, terdapat lintasan u-w dalam G. Selanjutnya, tiap lintasan u-w dari G

mengandung v.

Kebalikannya, anggap bahwa terdapat simpul u dan w dalam G yaitu simpul v

berada pada tiap lintasan u-w dari G. Maka tidak terdapat lintasan u-w dalam

G − v. Akibatnya G − v tidak terhubung dan v adalah cut-vertex dari G. ■

Definisi 2.23

Sebuah graf terhubung yang tidak kosong tanpa cut-vertices disebut graf yang

tidak dapat dipisahkan.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 34: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

22

Definisi 2.24

Sebuah ruas dalam graf terhubung adalah jembatan jika penghapusannya

mengakibatkan sebuah graf tidak terhubung.

Teorema 2.4

Sebuah ruas e dari graf G adalah jembatan jika dan hanya jika e tidak terdapat

dalam putaran dari G.

Bukti :

Anggap, tanpa kehilangan keadaan umum,bahwa G adalah terhubung, karena

e=(u,v) sebuah ruas dari G, dan anggap bahwa e berada pada putaran C dari

G.Selanjutnya, diberikan w1 dan w2 sembarang simpul-simpul berbeda dari G.Jika

e tidak berada pada w1-w2 lintasan P dari G, maka P juga merupakan lintasan

w1-w2 dalam G − e. Jika,bagaimanapun e berada pada lintasan w1-w2 dari G,

kemudian menggantikan e dengan lintasan u-v (atau lintasan v-u) dan C tidak

mengandung e menghasilkan perjalanan w1-w2 dalam G − e.Dengan teorema 2.1

terdapat lintasan w1-w2 dalam G − e. Karena w1 dan w2 terhubung dalam G − e

sehingga e bukan jembatan.

Kebalikannya, anggap bahwa e bukan jembatan dari G.Karena G − e terhubung.

Oleh karena itu terdapat lintasan u-v dalam G − e; bagaimanapun P bersama

dengan e menghasilkan putaran dalam G mengandung e. ■

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 35: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

23

Teorema 2.5

Sebuah graf G yang mempunyai order paling sedikit 3 adalah tidak dapat

dipisahkan jika dan hanya jika setiap dua simpul dari G berada pada suatu simpul

umum dari G.

Bukti:

Diberikan G sebuah graf yang tiap dua dari simpul-simpulnya berada pada

putaran.Sehingga G terhubung.Anggap bahwa G dapat dipisahkan.Oleh karena itu

G mengandung sebuah cut-verrtex v.Dengan teorema 2.3, terdapat simpul u dan w

sedemikian hingga v berada pada lintasan u-w dalam G. Diberikan C sebuah

putaran dari G yang mengandung u dan w. Putaran C menentukan u-w dua

lintasan yang berbeda;satu yang tidak mengandung v, berlawanan dengan fakta

bahwa tiap lintasan u-w mengandung v. Karena itu, G tidak dapat dipisahkan.

Sebaliknya, diberikan G sebuah graf yang tidak dapat dipisahkan dengan paling

sedikit tiga simpul. Tunjukkan bahwa tiap dua simpul dari G berada pada putaran

umum dari G. Diberikan u sebuah simpul sembarang dari G, dan ditulis dengan U

himpunan dari semua simpul-simpul yang berada pada sebuah lintasan yang

mengandung u.

Tunjukkan bahwa U=V=V(G). Anggap bahwa U≠ V; maka terdapat sebuah

v .UV −∈

Karena G tidak dapat dipisahkan, sehingga tidak mengandung cut-vertice, dan

lebih lanjut,karena derajat dari G paling sedikit 3, graf G tidak mengandung

jembatan. Berdasarkan teorema 2.3, setiap ruas dari G berada pada suatu putaran

dari G; karena itu, setiap simpul bertetangga pada u merupakan suatu anggota dari

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 36: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

24

U. Karena G terhubung, terdapat sebuah lintasan u-v, u = u0, u1,u2 ,...,uk=v dalam

G. Ambil i bilangan bulat terkecil, 2≤ i≤k, yakni ui∉U; demikian ui-1∈U. Ambil

C menjadi sebuah putaran mengandung u dan ui-1. Karena ui-1 buka cut-vertex

dari G, terdapat suatu lintasan ui-u : ui = v0,v1,v2,…vl = u tidak mengandung ui-1.

Jika hanya simpul umumnya pada P dan C adalah u, maka terdapat suatu putaran

bertetangga pada u dan ui, yang menghasilkan suatu kontradiksi. Karena itu P dan

C memiliki sebuah simpul yang umumnya berbeda dari u. Ambil j menjadi

bilangan bulat terkecil 1 j≤ ≤ l, yakni vj termasuk pada keduannya P dan C. Suatu

putaran mengandung u dan ui sekarang dapat di kontruksikan yang awalnya

dengan ui-vj bagian lintasan dari P, pada sepanjang C dari vj ke u dan lalu ke ui-1,

dan akhirnya mengambil ruas ui-1ui kembali ke ui. Demikian, kontradiksi timbul

lagi, berarti bahwa tidak terdapat simpul v dan bahwa setiap dua simpul berada

pada sebuah putaran. ■

Definisi 2.25

Sebuah blok dari graf G adalah maximal subgraf yang tidak dapat dipisahkan

dari G.

Jika suatu graf terhubung G mengandung sebuah blok, maka G adalah graf yang

tidak dapat dipisahkan. Dengan alasan ini, suatu graf yang tidak dapat dipisahkan

juga merupakan sebuah blok untuk dirinya sendiri.Tiap dua blok mempunyai

paling banyak satu simpul bersama,disebut suatu cut-vertex.

Pada gambar dibawah ini memiliki lima blok Bi, 1 , yang

dismpulkan.Simpul v

5≤≤ i

3,v5 dan v8 adalah cut-vertices.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 37: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

25

Gambar 2.18

Definisi 2.26

Setiap graf tidak terhubung dapat dibagi menjadi sejumlah subgraf terhubung

yang disebut komponen.

Nilai dari komponen dari graf G dilambangkan dengan k(G).

Definisi 2.27

Sebuah jembatan yang bertemu dengan sebuah simpul akhir disebut ruas

melingkar(pendant edge).

Definisi 2.28

Sebuah simpul bagian dalam dari lintasan u-v dalam P adalah banyaknya simpul

dari P yang berbeda dari u atau v.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 38: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

26

Definisi 2.29

Suatu himpunan {P1,P2,…,Pk} dari lintasan dikatakan memisah secara internal

jika tiap simpul dari Pi(i=1,2,…,k) tidak berada pada lintasan Pj(j i). Secara

khusus, dua lintasan u-v disebut memisah secara internal jika mereka tidak

memiliki simpul secara umum, selain dari u dan v.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 39: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

BAB III

GRAF PLANAR

Dalam bab ini akan dibahas tentang graf planar beserta beberapa metode

yang berkaitan, dimana diberikan graf yang dapat digambarkan tanpa adanya ruas

yang berpotongan. Pada Bab ini juga akan yang diberikan hasil dari metode Euler

dan Kuratowski.

A.Graf Planar

Secara umum sebuah graf dapat digambarkan dengan berbagai cara. Sebagai

contoh, graf lengkap K4 dan graf bipartite lengkap K3,3 dapat digambarkan sebagai

berikut

Gambar 3.1

Untuk beberapa graf, seperti K4 memungkinkan untuk digambarkan tanpa

berpotongan, akan tetapi untuk yang lain seperti K3,3 tidak dapat digambarkan

tanpa berpotongan. Inilah yang membuat kita membuat definisi berikut ini.

Definisi 3.1

Suatu graf G adalah graf planar jika dapat digambarkan pada bidang datar tanpa

ada dua ruas yang berpotongan, kecuali simpul dimana mereka bertemu.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 40: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

28

Contoh 3.1 :

Graf K4 di atas adalah graf planar.

Sebagai catatan dalam mempelajari graf planar, kita bisa membatasi perhatian kita

pada graf sederhana.

Jika graf planar mempunyai ruas ganda atau loop-loop, kita sederhanakan ruas

ganda menjadi satu ruas dan menghilangkan loop-loop. Setelah menggambarkan

hasil dari graf sederhana tanpa berpotongan, kita dapat kemudian memasukkan

loop-loop dan ruas ganda.

Hapus loop dan

Ruas Ganda

C D

A B B

CD

A A

C BD

A

BC

Gambartanpa

Memotong

Masukan loop-loop

danRuasGanda

Gambar 3.2

Definisi 3.2

Penggambaran dari graf planar dimana tanpa ada ruas yang berpotongan disebut

graf bidang.

Setiap graf bidang dari graf planar G membagi bidang menjadi beberapa bagian

yang disebut region.

Definisi 3.3

Setiap graf bidang dari graf planar G membagi bidang menjadi beberapa bagian

yang saling asing disebut region.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 41: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

29

Batas setiap sisi region terdiri dari sebuah barisan ruas yang membentuk sebuah

perjalanan tertutup.

Derajat dari suatu region (dinotasikan dengan deg r) adalah panjang dari

perjalanan tertutup disekitarnya yang membatasi region tersebut.

JIka semua region mempunyai derajat yang sama (sebutlah g), maka G disebut

graf dengan region yang teratur berderajat g.

Contoh 3.2

Gambar 3.3

Jika graf G seperti pada gambar diatas, maka G memiliki empat region. Pada tiap

gambar diperoleh

deg r1 = 3, deg r2 = 4, deg r3 = 9, deg r4 = 8

Terema 3.1 (HandShaking lemma untuk Graf Planar):

Jumlah derajat semua region adalah sama dengan dua kali banyaknya ruas pada

graf G.

∑ deg ri = 2m

Bukti:

Setiap ruas akan membatasi dua region berbeda dan akan muncul dua kali dalam

suatu perjalanan sepanjang batas region tersebut. Sehingga setiap ruas termuat

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 42: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

30

dalam sebuah region yang akan di hitung dua kali dalam menunjukkan derajat dari

sebuah region. ■

B.Formula Euler untuk Graf Planar

Teorema 3.2 (Rumus Euler’s)

Jika G suatu graf planar terhubung, dan diberikan n, m, dan r menunjukan masing-

masing adalah banyaknya simpul, ruas dan region pada graf bidang dari G. Maka

n – m + r = 2

Bukti :

Setiap graf terhubung G dapat dibentuk dengan mengambil sebuah spanning tree

dan menambahkan ruas, sampai graf G terbentuk. Kita buktikan hasilnya dengan

menunjukan bahwa :

a) untuk sebuah pohon penyangga, n – m +r = 2;

b) pada tiap tingkatan, penjumlahan dari suatu ruas tidak berubah nilainya

dari n – m + r.

Pertama, kita buktikan a) Jika T adalah sebuah pohon penyangga dari G, kita bisa

gambarkan T pada bidang, sebagai contoh :

Gambar 3.4

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 43: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

31

Karena T mempunyai n simpul dan n-1 ruas, dan hanya ada 1 region, kita punya

n – m + r= n - (n-1) + 1 = 2

sebagai hasil.

Kedua akan dibuktikan b) Bila kita menabahkan sebuah ruas, sedemikian hingga

sebuah ruas harus menghubungkan dua simpul yang berbeda, atau

menghubungkan sebuah simpul dengan dirinya sendiri (bila itu adalah loop),

maka pada kasus kedua ruas tersebut memotong region tersebut menjadi dua

region,seperti ditunjukan oleh gambar dibawah :

Gambar 3.5

Ini tidak mengubah n, m bertambah 1, dan r bertambah 1, karena itu n - m + r

tidak berubah. Karena n - m + r = 2 sepanjang proses tersebut,pernyataan b)

terbukti.

Menggunakan rumus Euler, kita bisa memperoleh sejumlah hasil yang

bermanfaat.

Pada kasus khusus kita bisa memberikan bukti alternatif dari kenyataan bahwa K5

dan K3,3 adalah non planar. ■

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 44: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

32

Gambar 3.6

Teorema 3.3

Jika G suatu graf planar sederhana terhubung dengan n 3 simpul dan m ruas,

maka m=3n-6.

Bukti :

Untuk graf bidang dari G dengan r region.Batas dari tiap region adalah sebuah

segitiga,dan tiap ruas adalah batas dari dua region.Oleh karena itu,jika banyaknya

ruas pada batas suatu region di jumlahkan semua,hasilnya adalah 3r.Pada sisi lain,

penjumlahan tersebut menghitung ruas dua kali,jadi 3r =2m,diperoleh r = m32 .Ini

dikombinasikan dengan rumus Euler’s r = m – n +2,diperoleh m – n + 2

= m32 ,sehingga m = 3n-6.■

Akibat 3.1

Jika G suatu graf planar sederhana terhubung dengan n ≥ 3 simpul dan m ruas,

maka m ≤ 3n-6.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 45: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

33

Bukti :

Untuk graf bidang dari G dengan r region, berdasarkan handshaking lemma untuk

graf planar bahwa 2m ≥ 3r (karena derajat dari tiap region dari graf sederhana

paling sedikit 3)., diperoleh r ≤ 32 m. Ini dikombinasikan dengan rumus Euler’s r

= m – n + 2, diperoleh m – n + 2 ≤ 32 m, dan oleh karena itu m ≤ 3n – 6. ■

Contoh 3.3 :

K5 adalah graf nonplanar.

Bukti :

Andaikan bahwa K5 graf planar sederhana terhubung adalah graf planar. Karena

K5 mempunyai lima simpul dan sepuluh ruas, berdasarkan akibat 3. 1 bahwa m =

10 dan 3n – 6 = 9,jadi m > 3n-6. Kontradiksi ini menunjukan bahwa K5 adalah non

planar.

Akibat 3. 1 tidak dapat digunakan untuk membuktikan bahwa K3,3 adalah

non planar. Akan tetapi, kita dapat menggunakan akibat berikut ini.

Akibat 3.2

Jika G adalah graf planar sederhana terhubung dengan n simpul dan m ruas, dan

tidak memuat segi tiga maka m ≤ 2n-4.

Bukti :

Untuk gambar bidang dari G dengan r region, berdasarkan handshaking lemma

untuk graf planar bahwa 2m ≥ 4r (karena derajat dari tiap region dari graf sederhana

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 46: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

34

tanpa segitiga paling sedikit 4), sehingga r ≤ m21 . Ini dikombinasikan dengan

formula Euler r= m – n + 2, diperoleh m – n + 2 ≤ m21 , dan oleh karena itu m ≤ 2n –

4. ■

Contoh 3.4 :

K3,3 adalah non planar.

Bukti :

Kita tahu K3,3 bahwa adalah graf sederhana terhubung. Karena K3,3 mempunyai

enam simpul dan sembilan ruas dan tidak memuat segitiga, berdasarkan dari akibat

2 bahwa 9 ≤ (2 x 6) – 4 = 8. Kontradiksi ini menunjukan bahwa K3,3 adalah non

planar. ■

Akibat 3.3:

Jika G adalah graf planar sederhana terhubung.Maka G mempunyai sekurangnya

satu simpul berderajat 5 atau kurang.

Bukti :

Berdasarkan akibat 3.1, kita peroleh m≤ 3n-6.Andaikan bahwa setiap simpul pada

G mempunyai derajat 6 atau lebih.Maka kita peroleh 2m≥ 6n ( karena 2m adalah

penjumlahan dari derajat-derajat simpul ),sehingga m≥ 3n.

Kontradiksi ini menunjukan bahwa sedikitnya satu simpul mempunyai derajat 5

atau kurang. ■

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 47: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

35

Sekarang kita gunakan rumus Euler’s untuk menunjukkan mengapa hanya

ada lima polyhedra konvex beraturan yaitu tetrahedron, kubus, octahedron,

dodecahedron, and icosahedron.

tetrahedron kubus octahedron

icosahedron dodecahedron

Gambar 3.7

Definisi 3.4

Suatu polyhedron dikatakan konvex jika setiap garis lurus yang menghubungkan

tiap dua simpul dalam polyhedron tersebut berada didalam polyhedron itu juga.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 48: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

36

Kita gunakan kenyataan bahwa kita dapat menyajikan tiap polyhedron sebagai

suatu graf planar dengan memproyeksikan pada suatu bidang.Hal ini tampak

seperti gambar dibawah ini :

Gambar 3.8

Metode dari proyeksi ini di kenal sebagai stereographic projection, dan telah

digunakan oleh A.L Cauchy pada 1813 dalam papernya Recherches surles

polyedres (Researches on polyhedra).Dalam paper ini dia mengambil perumusan

tentang graf planar dari rumus Euler, dan menggunakan itu untuk membuktikan

bahwa hanya ada lima polyhedra cembung beraturan.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 49: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

37

Torema 3.3 (Rumus Euler Untuk Polyhedron)

Jika V,E dan R adalah banyaknya titik, ruas dan region dari sebuah polyhedron ,

maka

V – E + R = 2

Bukti untuk teorema ini sama dengan teorema 3.1

Teorema 3.4

Jika P adalah sebuah polyhedron dan jika G adalah graf yang mewakilinya.

Andaikan P mempunyai V titik, E ruas dan R region.Untuk tiap k, Vk adalah

banyaknya titik dengan derajat k dan Rk adalah banyaknya region yang dibatasi

oleh suatu k-putaran,maka

∑≥3k

kkV = 2E = ∑≥3k

kkR

Bukti :

Karena tiap ruas dari suatu polyhedron tepat menyentuh dua titik dan dua region

berbeda maka ruas tersebut di hitung dua kali dalam perhitungan banyaknya titik

berderajat k dan banyaknya ruas yang membatasi suatu region,sehingga diperoleh

∑≥3k

kkV = 2E = ∑≥3k

kkR ■

Teorema 3.5

Paling sedikit ada satu region dari tiap polyhedron dibatasi oleh sebuah k-

putaran,dengan k = 3,4,5.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 50: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

38

Bukti :

Andaikan, untuk kebalikannya, bahwa R3 = R4 = R5 = 0.Dengan menggunakan

teorema 3.4 di peroleh

2E =∑≥6k

kkR ≥ ∑≥6

6k

kR =6 =6R. ∑≥6k

kR

Karena itu E≥ 3R.Juga

2E = =3 = 3V. ∑≥3k

kkV ≥ ∑≥3

3k

kV ∑≥3k

kV

Dengan teorema 3.2, V-E+R=2 dan jadi 3V-3E+3R=6.Karena 6=3V-3E+3R 2E-

3E+E=0,suatu kontradiksi. ■

Definisi 3.5

Sebuah polyhedron beraturan adalah sebuah polyhedron dengan region yang

dibatasi oleh segibanyak beraturan yang sama dan mempunyai sudut-sudut

polyhedral yang sama.

Khususnya,untuk sebuah polyhedron beraturan,R=Rs untuk suatu s dan V=Vt

untuk beberapa t.Sebagai contoh , sebuah kubus adalah polyhedron beraturan

dengan V=V3 dan R=R4.

Torema 3.6

Hanya ada lima polyhedral beraturan.

Bukti:

Jika P adalah sebuah polyhedron beraturan dan jika G(P) adalah sebuah graf

planar yang mewakilinya.Maka V - E + R = 2,dimana V,E dan R adalah

banyaknya simpul, ruas dan region dari P dan G(P).Oleh karena itu

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 51: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

39

-8 = 4E- 4V- 4R

= 2E + 2E – 4V – 4R

= ∑ + - 4 - 4 ≥3k

kkR ∑≥3k

kkV ∑≥3k

kV ∑≥3k

kR

=∑ + ≥

−3

)4(k

kRk ∑≥

−3

)4(k

kVk

Karena P adalah beraturan, sehingga ada bilangan bulat s( dan

t( ),demikian R=R

)3≥

3≥ s dan V=Vt. Karena itu -8 =(s-4)Rs+(t-4)Vt. Selain itu,kita

catat bahwa 3 s 5, 3 t≤ 5 dan sR≤ ≤ ≤ s=2E=tVt. Inii memberikan kita lima kasus

untuk dipikirkan.

Kasus 1.Anggap bahwa s=3 dan t=3.Kita peroleh

-8= -R3–V3 dan 3R3 = 3V3

Maka R3=V3= 4. Demikian P adalah tetrahedron

Kasus 2.Anggap bahwa s=3 dan t=4.Kita peroleh

-8=-R3 dan 3R3=4V4

Maka R3=8 dan V4=6,Demikian P adalah octahedron

Kasus 3.Anggap bahwa s=3 dan t=5.Kita peroleh

-8=-R3+V5 dan 3R3 dan 5V5

Maka R3=4 dan V5=12.Demikian P adalah icosahedron

Kasus 4.Anggap bahwa s=4 dan t=3.Kita peroleh

-8= -V3 dan 4R4 =3V3

Maka V3 = 8, R4 =6.Demikian P adalah kubus

Kasus 5. Anggap bahwa s=5 dan t=3.Kita peroleh

-8=R5-V3 dan 5R5=3V3

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 52: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

40

Maka R5= 12 dan V3=20.Demikian P adalah dodecahedron. ■

C. Karakterisasi dari Graf planar (Kuratowski)

Terdapat dua graf yaitu K5 dan K3,3 , yang berperan penting dalam mempelajari

graf planar.

Gambar 3.9

Teorema 3.7

Graf K5 dan K3,3 adalah nonplanar.

Bukti:

Bukti sama dengan contoh 3.3 dan 3.4. ■

Definisi 3.4

Sebuah bagian dari sebuah graf G yang tidak kosong adalah graf yang diperoleh

dari G dengan menghilangkan beberapa ruas e=(u,v) atau menambahkan simpul

baru w dan ruas-ruas (u,v) dan (v,w).

Pada gambar dibawah ini graf G1 dan G2 adalah bagian dari G3.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 53: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

41

Gambar 3.10

Jelas bahwa tiap bagian dari sebuah graf G adalah planar atau nonplanar

tergantung apakah G adalah planar atau nonplanar. Selain itu adalah suatu

pengamatan dasar bahwa jika sebuah graf G mengandung sebuah subgraf

nonplanar, maka G adalah nonplanar.

Teorema 3.8

Jika sebuah graf G berisi sebuah subgraf yang isomorfik dengan suatu bagian dari

salah satu K5 atau K3,3 maka G adalah nonplanar.

Bukti :

Karena G berisi sebuah subgraf yang isomorfik dengan K5 atau K3,3, sedangkan

seperti diketahui pada teorema 3.7 bahwa K5 atau K3,3 adalah nonplanar maka jelas

bahwa G adalah nonplanar. ■

Teorema 3.9

Sebuah graf adalah planar jika dan hanya jika masing-masing dari bloknya adalah

planar.

Bukti:

Jelas, graf G planar jika dan hanya jika masing-masing dari subgrafnya adalah

planar, jadi dapat diasumsikan G terhubung. Dapat dikatakan juga jika G planar

,maka masing-masing blok di G adalah planar. Untuk kebalikannya,digunakan

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 54: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

42

induksi pada banyaknya blok dari G. Jika G hanya memiliki satu blok dan

bloknya adalah planar, maka jelas G planar. Asumsikan bahwa setiap graf dengan

banyaknya blok lebih kecil dari k yang masing-masing dari blok tersebut

planar, maka grafnya planar dan andaikan G memiliki blok sebanyak k, salah

satunya adalah planar. Ambil B adalah blok terakhir G dan misalkan v adalah cut-

vertex untuk G bersama dengan B. Dihapus dari G semua simpul dari B berbeda

dengan v, namakan graf hasil tersebut G’. Dengan hipotesis induksi, G’ adalah

graf planar. Karena blok B planar,dapat disisipkan pada bidang sehingga v

terdapat pada bagian luar region. Dalam setiap region dari bidang yang menyisip

G’ memuat v, bidang blok B dapat dengan mudah ditempatkan, sehingga kedua

simpul dari G’ dan B yangt diberi nama sama yaitu “v” teridentifikasi. Hasilnya

adalah graf bidang dari G; akibatnya G adalah planar. ■

2≥

Definisi 3.5

Suatu vertex-cut dalam suatu graf adalah himpunan U yang terdiri atas simpul-

simpul di G sedemikian hingga G − U tidak terhubung.

Definisi 3.6

Keterhubungan titik atau disingkat keterhubungan, ditulis κ(G), dari suatu graf G

adalah kardinalitas minimum dari vertex-cut bila G tak lengkap dan κ(G)=n-1 jika

G=Kn untuk suatu bilangan positif n.

Dengan kata lain κ(G) adalah jumlah minimal titik-titk yang hasil penghapusan

titik-titik tersebut adalah suatu graf tak terhubung atau graf trivial.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 55: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

43

Definisi 3.7

Suatu graf G dikatakan k-terhubung, k≥1, bila κ(G) ≥k

Teorema 3.10

Jika G adalah graf 2−terhubung dengan banyaknya simpul paling sedikit 4 maka

suatu simpul v sedemikian hingga G-v yang juga merupakan graf 2−terhubung

atau G memuat suatu simpul berderajat 2.

Bukti :

Andaikan G tidak terdiri dari simpul v sedemikian hingga G-v adalah graf

2−terhubung. Maka, untuk setiap simpul x dari G ada sebuah simpul y dari G-x

sedemikian hingga G-x-y tidak terhubung. Diantara semua pasangan simpul-

simpul x,y di G, pilih suatu pasangan u,v sehingga G-u-v tidak terhubung dan

terdiri dari bagian G1 dengan banyaknya simpul minimum k. Masing-masing

komponen dari u dan v bertetangga paling sedikit satu simpul dalam tiap

komponen dari G-u-v. Jika k=1 maka simpul dari G1 dapat bertetangga hanya

dengan u dan v dan berakibat memiliki derajat 2 dalam G. Kemudian dapat

dianggap bahwa k≥ 2. Ambil G2 adalah suatu graf yang gabungan komponen-

komponen di G-u-v berbeda dari G1. Kemudian ambil H= ⟨ V(G) {u,v} ⟩ . ∪

Misal w1∈V(G1). Maka terdapat suatu simpul w2 pada G-w1 yaitu G-w1-w2 yang

tidak terhubung.Simpul w2 termasuk dalam H atau dalam G2.Diperoleh dua kasus

dibawah ini

Kasus 1:

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 56: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

44

Misal w2∈V(H),karena tiap anggota ⟨ V(G2) {u} ⟩ ,∪ ⟨ V(G2) {v} ⟩ dan

V(G

⟨ 2)∪ {u,v} terhubung,beberapa komponen dari G-w⟩ 1-w2 mempunyai order

lebih sedikit dari k, yang tidak mungkin.

Kasus 2:

Misal w2∈V(G2), karena G-w1-w2 tidak terhubung,simpul u dan v harus tidak

bertetangga dan menjadi komponen yang berbeda dalam G-w1-w2.Akibatnya H-w1

mempunyai tepat dua komponen,sebut komponen Hu mengandung u dan

komponen Hv mengandung v. Jika Hu trivial, dan akibatnya hanya memuat u,

maka u bertetangga pada G hanya dengan w1 dan w2 dan degG u=2. Begitupun

degG v=2 jika Hv nontrivial.Maka G-w1-u dan G-w1-v adalah graf tidak terhubung

yang mengandung sebuah komponen yang beroder lebih sedikit dari k, terdapat

suatu kontradiksi.

Gambar 3.11 menunjukkan sebuah graf 2−terhubung G1 tidak mengandung simpul

v sedemikian hingga G1−v juga graf 2−terhubung.Sehingga,berdasarkan teorema

3.10, G1 mengandung sebuah simpul berderajat 2, sedemikian hingga ini

merupakan kasus. Di lain pihak, G1 mengandung sebuah ruas, disebut w1x1, yang

merupakan hasil penghapusan dari G1 dalam sebuah graf 2−terhubung. Graf G2

dalam gambar 3.11, tidak mengandung sebuah ruas. Bagaimanapun, G2

mengandung sebuah ruas, sebut w2, yang merupakan hasil penghapusan dari G2

dalam sebuah graf 2−terhubung. Sehingga, hasilnya analog dengan teorema 3.10

mengenai ruas-ruas. Ini merupakan akibat dari teorema 3.10. ■

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 57: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

45

Teorema 3.11

Jika G adalah graf 2−terhubung yang memiliki order paling sedikit 4, maka G

memuat e yaitu G-e yang juga merupakan graf 2−terhubung atau G memuat

simpul berderajat 2.

v1

z1

x1

u1

w1

y1

G1

v2y2

x2u2

w2

G2

2 - graf terhubung

Gambar 3.11

Bukti:

Andaikan bahwa G tidak mengandung ruas e sedemikian hingga G-e adalah graf

2−terhubung. Selanjutnya andaikan bahwa G tidak memuat simpul yang

berderajat 2. Dengan teorema 3.10, G terdiri dari suatu simpul v yaitu G-v adalah

graf 2−terhubung.misal e adalah suatu ruas yang berpotongan dengan v. Dengan

hipotesa, G-e bukan graf 2−terhubung. Akibatnya, G-e terdiri dari suatu cut-vertex

u yang biasanya berbeda dari v.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 58: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

46

Karena itu G-e-u = G-u-e tidak terhubung,yang mengakibatkan e adalah jembatan

pada graf G-u. Karena G-u-v = G-v-u terhubung, ruas e adalah suatu ruas

melingkar dalam G-u dan maka v adalah simpul akhir dari G-u. maka, v

mempunyai derajat 1 dalam G-u dan juga mempunyai derajat 2 dalam G,

diperoleh kontradiksi. ■

Teorema 3.12

Sebuah graf G adalah planar jika dan hanya jika G tidak mengandung subgraf

yang isomorfik dengan K5 atau K3,3 atau sebuah bagian dari K5 atau K3,3.

Bukti:

Telah diketahui adalah akibat dari teorema 3.8 : kemudian yang perlu dicari hanya

syarat cukupnya saja. Dengan melihat teorema 3.9, buktinya menunjukkan bahwa

jika graf 2−terhubung tidak mengandung K5 atau K3,3 atau sebuah bagian dari

salah satunya adalah subgraf, maka graf tersebut planar.Anggap, secara kebalikan,

terdapat graf 2−terhubung yang nonplanar yang tidak mengandung K5, K3,3 atau

sebuah bagian dari salah satunya sebagai subgraf. Diantara semua graf

2−terhubung yang nonplanar, misal G adalah yang mempunyai ukuran minimum.

Akan ditunjukkan bahwa δ(G)≥3. Karena G adalah graf 2−terhubung, δ(G)≥2.

Anggap bahwa G mengandung suatu simpul v dengan degG v = 2, dimana v

bertetangga dengan u dan w. Diperoleh dua kasus,menurut kondisi (u,w)∈E(G)

atau (u,w)∉E(G).

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 59: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

47

Kasus 1.

Anggap (u,w)∈E(G).Maka G-v adalah graf 2− terhubung yang juga tidak

mengandung K5,K3,3 atau sebuah bagian dari salah satunya sebagai subgraf.

Karena ukuran dari G-v kurang dari ukuran G, diperoleh G-v adalah planar.

Dalam penyisipan planar dari G-v , simpul v dan ruas (u,v) dan (v,w) dapat

dimasukkan ke dalam suatu region dari G-v yang dibatasi oleh ruas (u,w) yang

menghasilkan suatu graf G adalah bidang,tapi hal ini tidak mungkin.

Kasus 2.

Anggap bahwa (u,w)∉ E(G) maka G’= G-v + (u,w) adalah graf 2−terhubung yang

ukurannya lebih kecil dari ukuran G. Akan ditunjukkan bahwa G’ tidak

mengandung K5, K3,3 atau sebuah bagian dari salah satunya sebagai sebuah

subgraf ; Diasumsikan,kebalikannya, bahwa G’ mengandung suatu subgraf

F.Berarti, F harus mengandung ruas (u,w). Jika (u,w) diganti dengan simpul v dan

ruas (u,v) dan (v,w), maka menghasilkan graf F’ yang merupakan suatu bagian

dari F dan juga merupakan suatu bagian dari K5 atau K3,3. Maka, F’ adalah

subgraf dari G, yang tidak mungkin. Sehingga G’ adalah graf 2−terhubung yang

tidak mengandung keduanya K5, K3,3 maupun bagian dari salah satunya sebagai

subgraf, dan ukuran dari G’ lebih kecil dari G,sehingga G’ planar. Karena G

adalah suatu bagian dari G’ diperoleh G planar juga, sehingga menghasilkan suatu

kontradiksi.

Karena dari kedua kasus diperoleh kontradiksi, tidak ada simpul dalam G yang

mempunyai derajat 2 dan δ(G) 3, terbukti. Karena G adalah graf 2−terhubung ≥

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 60: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

48

yang memiliki order paling sedikit 4 dengan δ(G)≥3, menurut teorema 3.11

bahwa G mengandung suatu ruas e=(u,v) yaitu H=G-e yang juga merupakan graf

2−terhubung.

Karena H tidak mengandung K5, K3,3 atau sebuah bagian dari salah satunya

sebagai subgraf dan ukuran dari H lebih kecil dari yang terkandung pada G, graf

H adalah planar.Sekarang karena H adalah graf 2−terhubung, H mempunyai

putaran yang mengandung u dan v berdasarkan teorema 2.2. Diantara semua

penyisipan planar dari H, ambil H yang telah tersisip pada bidang sehingga H

memiliki sebuah putaran C yang mengandung u dan v yang mana banyaknya

bagian dalam region adalah maksimal. Kemudian dapat dianggap bahwa C :

u=v0,v1,…,vi=v,…,vk=u, dimana 2 2−≤≤ ki .

Beberapa pengamatan atas graf bidang H sekarang dapat dibuat. Dalam hal ini,

lebih mudah untuk mendefinisikan dua subgraf khusus dari H. Dengan bagian

luar subgraf (bagian dalam subgraf) dari H, dapat diartikan sebagai subgraf dari

G yang dihasilkan oleh ruas-ruas yang terdapat pada bagian luar (bagian dalam)

pada putaran C. Pertama, karena graf G tidak planar, kedua bagian dalam dan luar

subgraf ada, disisi lain ruas e dapat di tambahkan pada H (tidak pada bagian luar

C atau bagian dalam C) sehingga diperoleh graf hasil dinamakan graf G, adalah

planar.

Dapat dituliskan kemudian bahwa tidak ada dua simpul tertentu dari himpunan

{v0,v1,…,vi} yang terhubung oleh lintasan pada bagian dalam subgraf H, dengan

kata lain akan menimbulkan kontradiksi dengan pemilihan C sebagai suatu

putaran yang mengandung u dan v dan mempunyai jumlah maksimal pada bagian

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 61: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

49

dalam region, dengan cara yang sama dapat dibuat himpunan {vi,vi+1,…,vk}.

Pernyataan ini sesuai dengan kenyataan bahwa H+e adalah nonplanar

mengakibatkan adanya dari vs-vt pada lintasan P, 0<s<i<t<k, pada bagian luar

subgraf H sedemikian hingga tidak ada simpul P yang berbeda dari vs dan vt pada

C.Susunan ini ditunjukan oleh gambar 3.12. Selanjutnya dapat dituliskan bahwa

tidak ada simpul pada P yang berbeda dari vs dan vt yang bertetangga pada simpul

dari C lainnya daripada vs atau vt, dan lebih dari itu setiap lintasan

menghubungkan sebuah simpul dari P dengan sebuah simpul dari C harus

mengandung paling sedikit salah satu dari vs dan vt.

H

P

vs

vt

v=vi u = v0 = vk

Struktur dari graf H pada teorema 3.12

Gambar 3.12

Misal H1 komponen dari H - {vr | 0≤ r<k,r≠ s,t}yang mengandung P. Dengan

memilih C, subgraf H1 tidak dapat dimasukan pada bagian dalam dari C.

Bersamaan dengan anggapan diatas bahwa G tidak planar, mengimplikasikan

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 62: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

50

bahwa bagian dalam subgraf dari H harus mengandung salah satu dari pernyataan

berikut ini:

1. Suatu va-vb lintasan Q, 0<a<s, i<b<t (atau, sama, s<a<i dan t<b<k),

tidak semua simpul-simpul yang berbeda dari va dan vbberada di C.

2. Suatu simpul w yang tidak berada di C yang dihubungkan ke C oleh

tiga lintasan yang memisah secara internal yakni pada simpul akhir

dari lintasan P’ adalah satu dari v0, vs, vi dan vt.

Jika P’ berakhir pada v0, simpul-simpul akhir dari lintasan lain adalah

va dan vb, dimana s≤ a<i dan i<b≤ t tapi tidak keduanya a=s dan b=t

terhubung. Jika P’ berakhir pada setiap vs,vi atau vt maka terdapat tiga

kasus yang sama.

3. Suatu simpul w bukan dalam C yang dihubungkan ke C oleh tiga

lintasan yang memisah secara internal P1,P2,P3 seperti pada simpul-

simpul akhir dari lintasan (berbeda dari w), merupakan tiga dari empat

simpul v0, vs, vi, vt, katakan, v0, vi, vs berturut-turut, bersama dengan

suatu vc-vt lintasan P4 (vc≠ v0, vi, w) dimana vc terdapat pada P1 atau P2,

dan P4 tidak terhubung dari P1, P2 dan C kecuali untuk vc dan vt.

Pilihan yang tersisa untuk P1, P2, dan P3 menghasilkan tiga kasus yang

sama.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 63: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

51

4. Suatu simpul w bukan dalam C yang dihubungkan oleh simpul-simpul

v0, vs, vi, vt oleh empat lintasan yang memisah secara internal.

Empat kasus ini menyelesaikan berbagai kemungkinan. Dalam tiga kasus pertama,

graf G mempunyai sebuah subgraf yang mengandung K3,3 atau bagian dari K3,3

sebagai sebuah subgraf, sementara pada kasus keempat, G mengandung K5 atau

bagian dari K5 sebagai sebuah subgraf. Bagaimanapun ini bertentangan dengan

pengandaian. ■

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 64: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

BAB IV

PENUTUP KESIMPULAN Suatu graf G disebut graf planar jika dapat digambarkan pada bidang datar tanpa ada

dua ruas yang berpotongan, kecuali simpul dimana mereka bertemu.

Dalam menentukan suatu graf planar atau nonplanar dapat digunakan beberapa

teorema dibawah ini:

1. Graf K5 dan K3,3 adalah nonplanar.

2. Jika sebuah graf G berisi sebuah subgraf yang isomorfik dengan suatu bagian

dari salah satu K5 atau K3,3 maka G adalah nonplanar.

3. Sebuah graf adalah planar jika dan hanya jika masing-masing dari bloknya

adalah planar.

4. Jika G adalah graf 2−terhubung dengan banyaknya simpul paling sedikit 4

maka suatu simpul v sedemikian hingga G-v yang juga merupakan graf

2−terhubung atau G memuat suatu simpul berderajat 2.

5. Jika G adalah graf 2−terhubung yang memiliki order paling sedikit 4,maka G

memuat e yaitu G-e yang juga merupakan graf 2−terhubung atau G memuat

simpul berderajat 2.

6. Sebuah graf G adalah planar jika dan hanya jika G tidak mengandung subgraf

yang isomorfik dengan K5 atau K3,3 atau sebuah bagian dari K5 atau K3,3.

52

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Page 65: PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI GRAF … · contoh graf lengkap K 4 dan graf bipartite lengkap K 3,3 bisa digambarkan sebagai berikut. ... te tapi simpul-simpul boleh diulang

DAFTAR PUSTAKA

Chartrand, G. and Lesniak, L. 2005. Fourth Edition. Graph and Digraph. New

York : Chapman and Hall/CRC.

Liu,.C.L.1995. Dasar - Dasar Matematika Diskret. Edisi kedua. Jakarta :

Gramedia.

Lipschutz, S. dan Lipson,.M.L.2002.Matematika Diskrit. Jilid 2. Jakarta :

Salemba Teknika.

Suryadi,.H.S.1996. Teori Graf Dasar. Jakarta: Gunadarma.

Wilson.,J., and Watkins,.J.J. 1990. Graphs an Introductory approach. NewYork :

John wiley and sons,inc.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI