graph planar.doc

7/22/2019 graph planar.doc

1/23

GRAPH PLANAR

Pengertian Graph Planar

Graph G disebut graph planar jika G dapat digambar pada bidang datar sedemikianhingga sisi-sisinya tidak ada yang saling berpotongan kecuali mungkin pada titik-titik dari sisi-sisi tersebut.

Contoh Graph Planar :

Graph yang termasuk planar antara lain :

Tree / Pohon

Kubus

Bidang mpat

Bidang !elapan Beraturan

Graf Non-Planar"ebuah gra# yang tidak dapat disajikan $secara geometri% tanpa adanya ruas yang berpotongan dikenal

sebagai gra# non planar.

K&'& ( )tility Graph K *( Bintang

Pembuktian Graph K5 dan K3,3non planar

Graf Planar

K4

Penyajian Planar


2/23

)ntuk membuktikannya diperlukan de#inisi dari graph planar dan +Teorema Kur,a ordan yang

berbunyi : 0isalkan sebuah titik sesuai kur,a tertutup sederhana pada bidang datar !. Titik 1

terletak di interior dan titik y terletak di eksterior ' ika di buat sebuah kur,a yangmenghubungkan titik 1 dan y pada bidang ! ' maka kur,a tersebut pasti memotong kur,a .2

Berdasarkan teorema ini dapat dibuktikan lemma berikut:

Lemma : graph bipartisi komplit K3,3 dan graph komplit K5 adalah graph-graph non planar.

Bukti: perhatikan graph bipartisi komplit K&'&pada gambar berikut:

a3 a4 a& b3 b3

a3 a4 a3 a4

b& b4 b& b4

b3 b4 b& a& a&

(a K3,3 (b !ikel " (" G# K 3,3-a$b3

GraphK&'&tersebut memuat sikel C ( $a3'b3'a4'b4'a&'b&% seperti tampak pada Gambar(b%0isalkansisi a3b4digambar didalam sikel C maka sisi a &b3pada K&'&harus digambar diluar sikelC sehingga diperoleh graph G ( K&'&-a4 b& ' kemudian pandang sikel C3 ( $a3'b4'a4'b3'a3% pada

graph G. terhadap sikel C3tersebut titik a4terletak di interior C3 dan titik b&terletak di eksterior

C3. 0aka berdasarkan teorema kur,a ordan' jika a4 dan b&dihubungkan dengan sebuah sisimaka pasti sisi a4b&akan memotong sisi sikel C3. 5ni berarti tidak mungkin menggambar K&'&pada bidang datar sedemikian sehingga tidak ada sisi yang saling berpotongan. !engan kata lain

graph K&'&non planar.

"elanjutnya perhatikan graph komplit K* pada gambar *.6 berikut:

&$ &$

73 7& 73 7& 7&

7* 76 7* 76

$a%graphkomplit K* $b% graph 8( K*-,&,*


3/23

Graph K*tersebut memuat sikel C($,3',4',&',6',*',3%. 9ndaikan sisi-sisi ,4,*dan ,4,6 digambar di

dalam sikel C' maka sisi-sisi ,3,6dan ,3,&pada K*harus digambar di luar sikel C' diperolehgraph 8( K*-,&,*seperti gambar $b%. kemudian panjang sikel C3($,3',4',6',*% di graph 8. pada

sikel C3tersebut titik ,*terletak di interior C3dan titik ,&terletak di eksterior C3. Berdasarkan

teorema kur,a ordan' jika ,* dan ,&dihubungkan dengan sebuah sisi ,*,&maka sisi tersebut pastiakan memotong sisi sikel C3. adi K*adalah non planar.

Karena Graph K* dan K&'&merupakan graph non planar' maka setiap graph subdi,isi K* dan K&'&juga non planar. akta ini bersama-sama dengan homeomor#isme graph' diperoleh lemma

berikut

Lemma: setiap graph yang homeomorfik dengan K5 dan K3,3adalah graph non planar.

Kurato;ski menemukan bah;a setiap graph non planar memuat graph bagian yang isomor#ik

dengan subdi,isi dari K* dan K&'&. )ntuk membuktikan pernyataan tersebut diperlukan sederetan

lemma dan teorema serta sekumpulan konsep berikut.

Planarita' dan keterhubungan graph

Pada bagian ini akan dibahas keterkaitan antara planaritas dan kerhubungan graph. )ntuk itu kitaa;ali dengan pengertian graph non planar minimal berikut ini.

Graph G disebut graph non planar minimaljika graph G non planar dan setiap bagian sejati dari

G adalah graph planar.

"elanjutnya akan ditunjukan bah;a graph non planar minimal yang memiliki sisi sesedikit

mungkin merupakan graph terhubung-&. )ntuk membuktikan hal tersebut diperlukan beberapakonsep dan lemma pendukung berikut ini

a b c e


4/23

5ngat kembali graph planar disebut graph bidang. Graph bidang G mempartisi bidang

datar menjadi daerah daerah yang disebut muka $#ace%. "ebuah muka dibatasi oleh sisi sisi G."ebuah muka graph G disebut muka terbatas jika luas muka tersebut terbatas."ebaliknya' muka

tak terbatas adalah muka yang luasnya tak terbatas. 0isalnya gambar muka #3pada graph bidangG yang di batasi oleh sisi sisi e 3'e4' e&'e6 adalah muka terbatas. "edangkan muka #4yang dibatasi

oleh sisi sisi e&' e6' e*'e


5/23

dilakukan dengang memikirkan bola bola tersebut terbuat dari karet dan memotong bola

sepanjang sisi 3 lalu membeber kulit bola pada bidang datar dengan cara menarik keluar sisi

sisi 3%. "ebagai ilustrasi' perhatikan gambar

c a a

a d b c

d b d b

e3 c

$a% $b% $c%

$a% pajangan graph planar G' 3( pembatas muka terbatas

$b% pajangan G pada bola

$c% pajangan G pada bidang datar 3( pembatas muka tak terbatas

"elanjutnya akan ditunjukkan bah;a setiap graph non planar minimal adalah graph terhubung

dan tidak memiliki titik pemutus.

eorema ) *ika graph G non planar minimal maka G graph terhubung-$

Bukti : andaikan G tak terhubung . 0isal G3 G4. . .Gkadalah komponen komponen G ' makauntuk setiap i ' 3= i =k ' Gimerupakan graph bagian sejati dari G. karena G non planar minimal

maka' Gigraph planar untuk setiap i ' sehingga G planar. Kontradiksi bah;a G non planar. adi

G terhubung.

"elanjutnya andaikan G memiliki titik pemutus' dan misalkan titik , adalah titik pemutus G. jikaG3 G4. . . Gk adalah blok di G yang bersekutu di , maka komponen komponen dari G-,

merupakan graph bagian planar dari G $karena G non planar minimal%. 9kibatnya graph G

planar. Kontradiksi bah;a G non planar . karena G terhubung dan tidak memiliki pemutus maka

G graph terhunbung-4. !engan demikian teorema terbukti.

!engan menggunakan lemma *.6 kita buktikan teorema berikut


6/23

Lemma 5.!: misal "# adalah himpunan titik pemutus dari graph G dan G1, G$ adalah

graph-graph bagian dari G sedemikian sehingga G1 G$ # G dan %&G1' %&G$' #". misalkan

(1#Gi ). *ika G non planar, maka (1non planar atau ($non planar.

Bukti: andaikan 83dan 84planar maka menurut lemma *.6 kita bisa memajang 83sedemikian

sehingga sisi 1y menjadi salah satu batas muka terluar $muka tak terbatas%. Begitu juga dengan

84' kita bisa memajang pada bidang datar sedemikian sehingga sisi 1y menjadi salah satu batasmuka terluar. !engan menghimpitkan sisi 1y yang terletak di pajangan 8 3dan 84maka akan

diperoleh pajangan G. akibatnya G graph planar' kontradiksi dengan G non planar. adi 8 3non

planar atau 84non planar. !engan demikian lemma terbukti.

)ntuk selanjutnya graph bagian dari graph G yang homeomor#ik dengan k&'& atau k*disebut graph-graph kurato;ski. 0enggunakan teorema *.* dan lemma *.< kita buktikan

teorema berikut.

Lemma 5.+: misal graph G non planar dan tidak memiliki graph bagian kuratoski. *ika G

memiliki sisi sedikit mungkin diantara graph-graph ang demikian maka G terhubung-3.

0isalkan G sebuah graph dan e(u, sebuah sisi di G ' pengkontraksian sisi e dari G

adalah penghapusan sisi e dari G dan menyatukan titik u dan titik , . graph baru yang diperolehdilambangkan dengan G.e. misalnya graph G dan graph G.e !apat dilihat pada gambar berikut

e

gambar *.> :graph G dan graph G.e


7/23

lemma 5.: misalkan G sebuah graph terhubung-3 dengan . aka G memuat sisi e

sedemikian sehingga graph G.e adalah graph G terhubung-3.

Bukti: andaikan bah;a untuk setiap e di $G%' graph G.e tak terhubung-&. karena G.e tak

terhubung-& maka ada 4 titik di G.e' missal titik u dan titik ,' sedemikian sehingga G.e ?

graph tak terhubung dan himpunan titik pemutus tersebut pasti memuat sebuah titik di G.e yang

diperoleh dengan mengkontraksi2 sisi e(1y. Tanpa menghilangkan keumuman' misal titik

+1y(u maka adalah himpunan titik pemutus di G. dengan kata lain G-

merupakan graph tak terhubung.

0isal 8 adalah sebuah komponen dari G- yang memiliki titik sebanyak mungkin dan 8

adalah sebuah komponen yang lain dari G- $seperti tampak pada gambar *.@%

7

gambar *.@

karena G terhubung-& maka merupakan titik pemutus minimal di G. sehingga

setiap titik tersebut memiliki persekitaran di 8 dan 8. missal a sebuah titik persekitaran , di 8.

missal b adalah sebuah titik di G sedemikian hingga merupakan himpunan titik pemutus

di G. jelas bah;a graph bagian G yang dibangun oleh 7$8% atau G


8/23

adalah graph terhubung' jika b adalah sebuah titik di G ' maka G

adalah graph terhubung' sebab jika tidak maka G- tak terhubung' hal

ini kontradiksi dengan G terhubung-&. Aleh sebab itu G adalah sebuah

komponen dari G- yang memiliki titik melebihi titiknya 8' kontradiksi dengan 8

memiliki titik sebanyak mungkin.

Berikut akan ditunjukan pengkontraksian sisi graph melesterikan graph bagian

kurato;ski' namun sebelumnya diperlukan terminology berikut. ika G graph dengan

!an 8 adalah sebuah sub di,isi dari G' maka titik-titik 8 yang memiliki derajat paling sedikit

tiga disebut titik original.

/eorema 5.0: missal G sebuah graph dan . jika G.e memiliki graph bagian kuratoski

maka G juga memiliki graph bagian kuratoski.

Bukti: misalkan G3(G.e' 8 adalah graph bagian kurato;ski di G3 dan adalah sebuah titik di

G3 yang didapat dari mengkontraksi sisi e(1y. ika 8 adalah sub graph kurato;ski' maka 8

adalah sub di,isi dari K* dan K&'&.

Kasus 3.misalkan 8 adalah sub di,isi dari K* .

"ubkasus 3.3. titik bukan titik original dari 8. dalam hal ini titik diekspansi menjadi sebuah

sisi e(1y di G' maka graph G juga memuat graph bagian kurato;ski seperti tampak pada gambar

berikut

y

1


9/23

X

G3 G

subkasus 3.4. titik adalah titik original dari 8

subkasus 3.4.3. terdapat paling banyak satu dari sisi-sisi yang terkait ke 1 di G. mmaka dapatdiekspansi menjadi sebuah sisi e(1y' sehingga G juga memuat sub graph kurato;ski' seperti

tampak pada gambar berikut:

G3 G

"ubkasus 3.4.4. misalkan titik 1 dan y di G masing-masing terkait dengan dua sisi dari empat sisi

8 terkait . maka dapat diekspansi menjadi sebuah sisi e(1y' sehingga G juga memuat subgraph kurato;ski' seperti tampak pada gambar berikut.

y

G3 G


10/23

Z

X X

X

Y Y

Y

YYYYYYYYYYYYYYYY

YYYYYYY

Kasus 4. 0isalkan 8 subdi,isi dari K&'&

"ubkasus 4.3. titik bukan titik originaldari 8. dalam hal ini titik diekspansi menjadi sebuah

sisi e(1y di G' maka graph G juga memuat sub graph kurato;ski' seperti pada gambar berikut.

G3 G

"ubkasus 4.4. titik merupakan titik original dari 8 dalam hal ini titik di ekspansi menjadi sisi

e(1y di G $seperti tampak pada gambar% maka G juga memuat sub graph kurato;ski

G3 G

dengan demikian bukti teorema lengkap.


11/23

0isalkan graph G adalah graph planar jika setiap muka dan pajangan G dibatasi oleh segi

n polygonal kon,eks maka pajangan G yang demikian disebut pajangan kon,eks sebagai contoh'

perhatikan grph planar Ggambar *.3D. graph G3adalah pajangan tak kon,eks dari G sedangkangraph G4adalah pajangan kon,eks dari G

Gambar *.3D. G graph planarE G3 pajangan tak kon,eks dari GE G4 pajangan

kon,eks dari G

Teorema *.3D: jika G graph terhubung-& tanpa sub di,isi K* atau K&'&maka G mempunyai

pajangan kon,eks pada bidang

Bukti: $induksi pada panjang %. Karena graph G terhubung-& maka satu-satunya

graph G terhubung-& yang memiliki titik paling banyak 6 adalah K6kita tahu bah;a K6memiliki

pajangan kon,eks seperti G4pada gambar *.3D

9sumsikan pernyataan benar untuk graph G dengan. -3 dan n F*. 9rtinya jika G

graph terhubung -& tanpa sub di,isi K* atau K&'& dan -3 maka G mempunyai

pajangan kon,eks pada bidang. "elanjutnya akan ditunjukknan pernyataan benar untuk 7$G%

( n . karena G terhubung -& ' berdasarkan lemma *.> terdapat sisi e( 1 y di G sedmikian

sehingga G.e terhubung -& . misalkan adalah sebuah titik yang didapat dari mengkontraksi sisi

e tersebut . karena G tidak memuat sub graph Kurato;ski' . -3

Berdasarkan asumsi' graph G.e memiliki pajangan kon,eks pada bidang. Graph bidang yang

didapat dari menghapus semua sisi G.e yang terkait di memiliki sebuah muka yang memuat

titik $mungkin saja muka ini adalah muka tak terbatas %. 0issal C adalah sikel di grapah bidangini yang memmbatasi muka tersebut . karena G.e tadi memiliki pajangan kon,eks maka semua

G1

G G2


12/23

sisi di G.e yang terkait di berupa ruas garis . misal 13'14 ' . . . '1k adalah titik titik persekitaran dari

1 di C kita tinjau 4 kasus .

Kasus 3. "emua persekitaran y terletak di sebuah segmen dari 1 ike 1iH3 di C. maka kita perolehsebuah pajangan kon,eks dari G dengan meletekkan 1 di pada G.e dan meletakkan y dekat ke

seperti terlihat pada gambar berikut

Ii I IiH3 y I

y

IiH3

Kasus 4' jika kasus 3 tidak terjadi maka terdapat 4 kemungkinan.

"ub kasus 4.3 persekitaran 1 dan y memiliki & titik persekutuan di C. dalam hal ini graph G akan

memuat sub di,isi K* seperti tampak pada gambar berikut

"ub kasus 4.4 titik y mempunyai 4 persekitaran di C. misal u dan , ' yang terletak di komponen

komponen graph bagian C . yang di peroleh dengan menghapus titik 1 idan 1iH3untuk suatu i .

dalam hal ini C bersama sama dengan lintasan $u'y',% ' $1 i'1'1iH3% dan $1'y% membentuk sebuahsub di,isi dari K&'& di G seperti tampak pada gambar berikut

Ii

u ,

IiH3

X

Y

X

Y


13/23

!engan demikian hanya kasus pertama yang mungkin terjadi dan G dengan n titik memiliki

pajangan kon,eks. !engan demikian teorema terbukti

5%+ *embatan Pada Graph Planar

!alam mempelajari graph planar' graph-graph bagian tertentu' yang disebut jembatan2'

memegang peranan penting. Kita bahas si#at-si#at graph bagian demikian di bagian ini .

0isalkan G sebuah graph dan 8 sebuah graph bagian dari G. kita de#enisikan relasi J pada

himpunan $G% - $8%' dengan syarat bah;a e3Je4jika terdapat sebuah jalan sedemikianhingga (e3 dan e4berturut-turut adalah sisi pertama dan sisi terakhir dari dan ($jalan

pisah ?internal dengan 8 $atau tidak ada titik internal yang terletak di 8%.

Perhatikanlah bah;a relasi J adalah relasi ekui,alen pada $G% - $8%. "ebuah graph

bagian dari G-$8% yang diinduksi oleh klas eki,alen atau relasi J disebut sebuah jembatan2dari 8 di dalam G. Konsep jembatan seperti ini hanya dipakai dalam graph planar. 9kibatnya

jika B jembatan dari 8 maka B graph terhubung. lebih lanjut' setiap dua titik di B dihubungkan

oleh sebuah lintasan yang titik internalnya tidak terletak di 8. disamping itu setiap dua jembatandari 8 tidak memilki titik persekutuan kecuali mungkin titik di 8 .

0isalkan B sebuah jembatan dari 8 kita tulis 7$B% 8% dan kita sebut tititk ini

sebagai titik kaki jembatan B pada 8. jika maka B disebut jembatan-k. pada

pembicaraan selanjutnya kita hanya tertarik dengan jembatan dari sebuah sikel C. "ebagaicontoh perhatikanlah graph G pada gambar *.33. graph-graph bagian B 3B4B&B6dan B*adalah

jembatan-jembatan dari sikel C. jembatan B3 adalah jembatan-& begitu juga dengan B&sedangkan B* adalah jembatan-4 dan B4 adalah jembatan-3.


14/23

B3

bb

G

Gambar *.33. B3B4B&B6dan B* adalah jembatan ?jembatan

!ari sikel C pada graph G

!ua jembatan yang himpunan titik kaki nya sama disebut dua jembatan ekiu,alen.

0isalnya B3dan B& adalah dua jembatan yang ekiu,alen misalkan B adalah sebuah jembatan-kdari sikel C dengan KF4 maka titik titik kaki B mempartisi sikel C mejadi lintasan lintasan lepas

sisi yang disebut segmen segmen B . 4 jembatan B3 dan B4 dikatakan saling menghindar $tidak

bertindihan%. ika seluruh kaki B3 terletak di salah satu segmen B4 . jika sebaliknya ' jembatan B3dan B4 disebut bertindihan . misalnya ' dalam contoh pada gambar *.33' jembatan B & dan B6saling menghindar ' sedang kan B3dan B&bertindihan.

!ua jembatan B3 dan B4 dikatakan berselingan jika terdapat 6 titik u','u3dan ,3$berurutan secara

siklik % pada sikel C sedmikan hingga u dan , adalah kaki kaki dari B3 dan u3 ',3 adalah kaki kaidari B4. dari contoh di atas ' jembatan B6dan B*berselingan.

Teorema *.33. misalkan B3 dan B4 adalah 4 jembatan dari sikel C jika B3 dan B4berindihan maka

B3 dan B4 berselingan atau B3 dan B4 4 jembtan -& eki,alen.

Bukti : karena B3 dan B4bertindihan maka B3 dan B4masing masing mempunyai paling sedikit 4titik kaki.jika B3 dan B4adalah jembatan-4 maka jelas bah;a B3 dan B4berselingan sehingga kita

bisa asumsikan B3 dan B4masing masing mempunyai & kaki .kita tinjau 4 kasus '

Kasus 3: B3 dan B4tidak eki,alen '

0aka B3 mempunyai sebuah titik kaki u3yang terletak di antara 4 titik kaki berurutan u dan ,

dari B4. karena B3 dan B4bertindihan maka ada titik kaki ,3dari B3 yang tidak terletak di segmenB4 yang menghubungkan u dan , . dengan demikian B3 dan B4berselingan.

B3

B

5

B4

B

2


15/23

Kasus 4: B3 dan B4 jembatan-k yang eki,alen dengan kF&. ika kF6' maka B3 dan B4 jelas

berselingan. ika k(&' jelas B3 dan B4 adalah jembatan-& yang ekui,alen. !engan demikian

teorema terbukti.

Teorema *.34 :isalkan sebuah jembatan dari sikel 2 di graph G. jika memiliki 3 titik kaki

%1,%$dan %3di 2, maka terdapat titik %di %&' %&2' dan tiga lintasan 1,$dan 3 di angmenghubungkan % se6ara berturut-turut ke %1, %$ dan %3, sedemikian sehingga, untuk i7j,

%&i'8%&j' 9%.

Bukti : 0isalkan pelintasan $73'74% di B yang titik-titik internalnya pisah dari C. maka P harus

mempunyai titik internal 7' sebab jika tidak jembatan B sama dengan P' dan tidak memuat titik

ketiga 7&. 0isalkan L adalah lintasan-$7&'7% di B yang pisah titik dari C' dan misalkan ,Dadalahtitik pertama dari L pada P. lambangkan : dengan P 3segmen-$,D',3% dari lintasan P' dengan P4segmen-$,D',4% dari lintasan P' dengan P&segmen-$,D',&% dari L' jelas P3' P4dan P&memenuhi

syarat dalam teorema. !engan demikian teorema terbukti.

"elanjutnya kita bahas jembatan pada graph planar. 0isalkan G graph bidang dan Csebuah sikel di C. maka C adalah sebuah kur,a ordan pada bidang datar' dan setiap sisi di $G%-

$c% termuat di salah satu dari dua daerah yaitu interior C dan eksterior C. ini berakibat' sebuah

jembatan dari C seluruhnya terletak di interior C atau di eksterior C. selanjutnnya sebuhjembatan yang terletak di interior C disebut jembatan dalam' yang terletak di eksterior C disebut

jembatan luar. 0isalnya' dari contoh pada gambar *.34 ' B3dan B4 adalah jembatan-jembatan

luar sedangkan B&dan B6adalah jembatan-jembatan dalam dari C.

Gambar *.34: B3dan B4adalah jembatan luar dari sikel C' B&dan B6adalah jembatan-

jembatan dalam dari sikel C.

Teorema *.3& : jembatan-jembatan dalam $luar% saling menghindar satu dengan yang lain.

Bukti : $ dengan kontradiksi%. 0isalkan B3dan B4dua jembatan dalam dari sikel C pada graph

bidang. 9ndaikan B3 dan B4 saling bertindihan berdasarkan teorema *.33' maka B3 dan B4berselingan atau jembatan yang ekui,alen.


16/23

Kasus 3 : B3 dan B4 berselingan.

berdasarkan de#enisi' terdapat dua titik kaki B3yaitu u dan ,' dan dua titik kaki B 4yaitu u3dan

,3' sedemikian ssehingga u'u3',',3 terurutnsecara siklik di C. misalkan P3 adalah lintasan-$u',%di B3dan P4adalah lintasan-$u3',3% di B4yang titik internalnya pisah dari C. karena P3dan P4terletak pada jembatan yang berbeda' maka titik internal P3dan P4tidak yang bersekutu. Karena

P3dan P4terletak di interior C' maka berdasarkan teorema kur,a ordan' P 3dan P4berpotongan.adi' C bukan graph bidang. Kontradiksi $lihat gambar *.3&%

u3

kasus 4 : B3 dan B4 jembatan-& ekui,alen.0isalkan ,3',4dan ,&kaki-kaki dari B3dan B4berdasarkan teorema *.34 terdapat titik ,Ddi B3

dan & lintasan P3' P4dan P&menghubungkan ,Dke ,3' ,4dan ,&sedemikian sehingga' untuk iMj'

$Pi%N7$Pj% ( O,D. Begitu juga terdapat titik ,D di B4 dan tiga lintasan P3'P4 dan P&menghubungkan ,Dke titik-titik ,3',4dan ,&sedemikin sehingga' untuk iMj' $Pi%N7$Pj% ( O,D.$lihat gambar *.36%

74

73

7

Gambar *.36

Perhatikan bah;a' lintasan P3' P4dan P&membagi interior C menjadi tiga daerah' dan ,Dharusterletak di salah satu dari tiga daerah tersebut. Karena hanya dua dari titik-titik , 3',4dan ,&yang

dapat terletak di pembatas daerah yang memuat ,Dkita dapat asumsikan dengan si#at simetri '

bah;a ,& tidak terletak di pembatas daerah ini. Berdasarkan teorema kur,a ordan lintasan P&pasti memotong salah satu dari P3' P4atau C ' karena B3dan B4keduanya jembatan- jembatan

dari sikel C' jadi G bukan graph bidang. Kontradiksi. adi terbukti B3dan B4 saling menghindar.

Bukti untuk jembatan luar serupa$analog%.

0isalkan G graph bidang . sebuah jembatan dalam B dari sikel C di G dikatakan dapatditrans#er jika terdapat pajangan planar G dari G yang identik dengan G' kecuali bah;a G

adalah jembatan uar dari C di G. graph bidang G dikatakan diperoleh dari G dengan cara

mentrans#er $memindah% B. sebagai ilustrasi lihat gambar *.3*

P1

P2

P1

P2

P2

P1

vvvvvvvvv


17/23

G G

Gambar *.3*: pertrans#eran jenbatan B. pada G' B adalahembatan-jembatan dalam. Pada G' B adalah jembatan luar.

Teorema berikut memegang peranan penting dalam pembuktian teorema kurato;ski.

Teorema *.36:sebuahjembatan dalam ang menghindari setiap jembatan kuar dapat ditrans;er.

Bukti: misalkan B sebuah jembatan dalam dari sikel C pada graph bidang G. karena B

menghindari setiap jembatan luar dari C maka titik-titik kaki seluruhnya terletak di pembatas

sebuah muka G eksterior C. sehingga B dapat digambar pada muka tersebut. $sebagai ilustrasilihat gambar *.3*%. sehingga B sekarang di eksterior C.

ormula .uler

Teorema *.3


18/23

7$8% ( 7$G% dan $8% ( $G%-3

0aka

7$G% - $G% H $G%( 7$8% - $$8%H3% H $$8%H3%

( 7$8% - $8% H $8%

( 4

adi teorema terbukti atas kasus ini

Kasus 4: G tidak memuat sikel

Karena G terhubung dan tidak memuat sikel' maka G adalah pohon . adi G akan memuat sebuah

titik yang berderajat 3 di G. 0aka graph T ( G?, tetap merupakan pohon' jadi graph bidang

terhubung dengan k sisi. "ehingga berdasar asumsi belaku

7$T% - $T% H $T% ( 4

Karena

7$T% ( 7$G%-3' $T% ( $G%-3' dan $T% ( $G%' maka

7$G% - $G% H $G% ( $7$T%H3% - $$T%H3% H $T%

( 7$T% - $T% H $T%

( 4

!engan demikan teorema terbukti

Teorema *.3R: ika G adalah graph planar sederhana dengan $G%Q3' maka $G% = &7$G%-

graph planar.doc

Documents