representasi graf, graf isomorfik, graf plannar dan graf dual

44
Representasi Graf, Graf Isomork, Graf Planar dan Graf Bidang Oleh Kelompok II

Upload: risasi-febriani-ganda

Post on 01-Mar-2018

249 views

Category:

Documents


4 download

TRANSCRIPT

Page 1: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 1/44

Representasi Graf,

Graf Isomork,Graf Planar dan

Graf BidangOleh Kelompok II

Page 2: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 2/44

MATERIRepresentasi Graf 

Graf  Isomork 

Graf  Planar dan Graf

Bidang

Graf Dal

Page 3: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 3/44

RepresentasiGraf 

Terdapat beberapa macam representasi graf. Namun di sini hanya diberikan

tiga macam representasi yang sering digunakan, yaitu matriks ketetanggaan,

matriks bersisian dan senarai ketetanggaan.

!" Matriks Ketetanggaan #Ad$a%en%&Matri'(

( )

Matriks ketetanggan menyatakan ketetanggaan simpul-simpul di dalam

graf. adalah matriks dwimatra yang berukuran . Misalkan

, adalah graf dengan simpul, 1. Bila matriks tersebut

dinama

G n n

G V E n n×

= ≥

ij ij

ij

kan A !a ", maka a 1 jika simpul dan bertetangga,

sebaliknya a # jika simpul dan tidak bertetangga.

i j

i j

Page 4: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 4/44

1

$

%

&

1

%$

&

'1

& $

%

Matriks ketetanggaannyasimetri

Matriks ketetanggaannyasimetri

Matriksketetanggaannya tidak

Matriks ketetanggaan dinamakan juga matriks n(l-satu karena pada matriks

tersebut hanya berisi dari n(l dan satu. )elain angka # dan 1 elemen matriks

 juga dapat dinyatakan dengan nilai *menyataka false n #+ dan *menyatakan 1+.true

1 # 1 1 #

& 1 # 1 1

$ 1 1 # 1

% # 1 1 #

1 # 1 1 # #

& 1 # 1 # #

$ 1 1 # 1 #

% # # 1 # #

' # # # # #

1 & $ % '

1 & $ % 1 # 1 # #

& 1 # 1 1

$ 1 # # #

% # 1 1 #

1 & $ %

Page 5: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 5/44

1

&

$

%

e%

e

e

e&

e1

e'

e$

e

Matriks ketetanggaannyasimetri

1 # 1 & #

& 1 # 1 1

$ & 1 1 &

% # 1 & #

1 & $ %

/euntungan representasi dengan matriks ketetanggaan adalah elemen matriksnyadapat diakses langsung melalui indeks. )elain itu, kita juga dapat menentukan

dengan langsung apakah simpul dan simpuli j bertetangga.

&

0umlah elemen matriks

ketetanggan untuk graf

dengan n simpul adalah .n

1

1

erajat tiap simpul dapat dihitung dari matriks ketetanggan.

2ntuk graf tak-berarah, * +

)edangkan untuk graf berarah, * + jumlah nilai pada k(l(m

 

n

i ij

 j

n

 j ij

i

i

d v a

d v j a

=

=

=

=

1  * + jumlah nilai pada baris

n

i ij jd v i a=

=

  ∑

Page 6: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 6/44

)ontoh

1

$

%

&

1

%$

&

'

Berdasarkan gambar disamping,

tentukan derajat simpul & dan derajat simpul % 3

0awab 4

erajat simpul & 1 # 1 1 $

erajat simpul % # 1 1 # &

+ + + =

+ + + =

Berdasarkan gambar disamping,

tentukan derajat simpul % dan derajat simpul ' 3

0awab 4

erajat simpul % # # 1 # # 1

erajat simpul ' # # # # # #

+ + + + =

+ + + + =

Page 7: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 7/44

)ontoh

a

b

cd 

e

1# 1&

5

1%

1' 11

1

& $

%

Berdasarkan gambar disamping, tentukan

derajat simpul & 3

0awab 4

erajat-masuk simpul & 1 # # 1 &

erajat-keluar simpul & 1 # 1 1 $

+ + + =

+ + + =

1& 1#1& 5 11

5 1%

11 1% 1'

1# 1'

ab

c

e

∞ ∞ ∞ ∞

∞ ∞ ∞

∞ ∞ ∞ ∞

a b c d e

i bawah ini merupakan gambar graf berb(b(t.

Tanda menyatakan bahwa

tidak ada sisi dari simpul

ke simpul atau dari simpul

ke simpul itu sendiri,

sehingga dapat diberi

nilai tak hingga.

ij

i

 j

i i

a

Page 8: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 8/44

*" Matriks Bersisian #In%iden%& Matri'(

Matriks bersisian menyatakan kebersisian simpul dengan sisi.

Matriks bersisian 6 adalah matriks dwimatra yang berukuran .n m×

Baris menunjukkan label simpul, sedangkan k(l(m menunjukkan label sisi.

Bila matriks tersebut dinamakan , maka 1 jika simpul bersesuaian

dengan sisi , sebaliknya # jika simpul

ij ij

ij

 A a a i

 j a i =

 tidak bersisian dengan sisi .

Matriks bersisian dapat digunakan untuk mempresentasikan graf yang mengandung

sisi ganda atau sisi gelang.

 j

Page 9: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 9/44

&

e%

1

$

%

e

e&

e1

e'

e$

i bawah ini diperlihatkan matriks bersisian untuk graf yang

direpresentasikannya. Maka jumlah elemen matriks bersisian

tersebut adalah % - &% elemen.× =

1 1 1 # 1 # #

& 1 1 1 # # #

$ # # 1 1 1 #

% # # # # 1 1

1 & $ % ' -e e e e e e

Page 10: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 10/44

+" enarai Ketetanggaan #Ad$a%en%&list(

1

$

%

&

1

%$

&

'

1

& $

%

/elemahan matriks ketetanggaan adalah bila graf memiliki jumlah sisi relatifsedikit atau bersifat jarang * +, yaitu banyak mengandung banyak elemen

n(l, sedangkan elemen yang bukan n(l sedikit.

 sparse

itinjau dari implementasinya

di dalam k(mputer, kebutuhan ruang mem(ri untuk matriks jarang b(r(s

karena k(mputer menyimpan elemen # yang tidak perlu.

)enarai ketetanggaan4

14 &, $

&4 1, $, %

$4 1, &, %

%4 &, $

)enarai ketetanggaan4

14 &, $

&4 1, $

$4 1, &, %

%4 $

'4 -

)enarai ketetanggaan4

14 &

&4 1, $, %

$4 1

%4 &, $

Page 11: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 11/44

Graf Isomork#Isomorphi%

Graph(

1 &ua buah graf, dan dikatakan is(m(rfik jika terdapat k(resp(ndensi

satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduanya

sedemikian sehingga jika sisi bersisian dengan simpul

G G

e u 1

&

&

 dan di ,

maka sisi 7 yang berk(resp(n di juga harus bersisian dengan simpul

7 dan 7 di .

v G

e G

u v G

ua buah graf yang is(m(rfik adalah graf yang sama, kecuali penamaan

simpul dan sisinya saja yang berbeda. 8ni benar karena sebuah graf dapat

digambarkan dalam banyaknya cara.

Page 12: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 12/44

$

&1

%

d c

ba

v w

 x y

1 & 1

&

9ada gambar diatas, is(m(rfik dengan . )impul 1, &, $, dan % di

 berk(resp(nden dengan simpul a, b, c, dan d di .

)isi *1,&+, *&,$+, *$,1+, *$,%+, *1,%+ dan *&,%+ berk(resp(nden dengan sisi *

G G G

G

a

1 &

1 & $ $

, +,

* , +, * , +, * , +, * , +, * , +. )emua simpul di dan berderajat $. maupun tidak is(m(rfik dengan , karena simpul-simpul di

dua buah berderajat dua dan dua buah lagi berderajat tig

b

b c c d a d a c b d G GG G G G

1 &

a, sedangkan

simpul-simpul di dan semua berderajat tiga.G G

1G 

&G 

$G 

Page 13: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 13/44

:(nt(h lain graf yang is(m(rfik.

ari definisi is(m(rfik kita menyimpulkan dua buah is(m(rfik memenuhiketiga syarat berikut4

1. Mempunyai jumlah simpul yang sama.

&. Mempunyai jumlah sisi yang sama.

$. Mempunyai jumlah simpul yang sama berderajat tertentu.

Page 14: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 14/44

u

 x

v

w

 y

*a+ *b+

 Namun ketiga syarat ini ternyata belum cukup menjamin keis(m(rfikan.

:(nt(hnya sebagai berikut.

ua buah graf di atas memenuhi ketiga syarat yang telah disebutkan

sebelumnya. 9adahal keduanya tidak is(m(rfik. i * + terdapat dua

simpul anting-anting *berderajat 1+ yang bertetangga dengan simpul

a

, sedangkan di * + hanya terdapat satu buah simpul anting-anting

yang bertetangga dengan . 8tulah sebabnya kedua graf di atas tidak

is(m(rfik.

 x b

 y

Page 15: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 15/44

)ontoh

c

e

 g 

h   f     b

a

 s

v

w   u q

 p

Apakah pasangan graf di bawah ini is(m(rfik;

  . /arena tidak ada k(resp(densi satu-satu antara simpul pada

kedua graf. Tinjau misalnya simpul , simpul bertetangga degan dua buah

simpul berderajat & * dan + dan sebuah simpul be

Tidak isomorfik 

d d 

a c rderajat $ * +. 6raf

disebelah kanannya tidak mempunyai simpul yang berk(resp(nden dengan

*jika dianggap sebagai simpul yang berk(resp(nden dengan , maka ini

 jelas tidak benar, sebab bertetangg

h

 s d 

 s a dengan sebuah simpul berderajat & * +

dan dua buah simpul berderajat $ * dan +.

 p w

Page 16: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 16/44

)ontoh

 s   r 

a

u

q p

 f  e

b

c

Apakah pasangan graf di bawah ini is(m(rfik;

, . /arena terdapat k(resp(nden satu-satu antara simpul pada

graf sebelah kiri dengan simpul-simpul pada graf sebelah kanan, yaitu4

  berk(resp(nden dengan <

  berk(resp(n

 Iya isomorfik 

a u

b den dengan <

  berk(resp(nden dengan <

  berk(resp(nden dengan <

  berk(resp(nden dengan <

  berk(resp(nden dengan <

q

c r 

d s

e p

 f t 

Page 17: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 17/44

b   c

a

ev

  

w

 x y

)AMA

/edua graf tersebut is(m(rfik 

2ntuk memperlihatkan bahwa dua buah graf is(m(rfik, kita dapat menunjukkan

 bahwa matriks ketetanggan kedua graf itu sama.

# 1 1 1 #

1 # 1 # #

1 1 # 1 #

1 # 1 # 1

# # # 1 #

a

b

c

e

Matriks ketetanggaannya

# 1 1 1 #

1 # 1 # #

1 1 # 1 #

1 # 1 # 1

# # # 1 #

w

 x

 y

v

  

a b c d e

Matriks ketetanggaannya

w x y v  

Page 18: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 18/44

)ontoh

Apakah graf sederhana yang disajikan (leh pasangan matriks ketetanggaan

di bawah ini is(m(rfik; 0elaskan jawaban, lalu gambarkan grafnya3

# 1 # 1

1 # # 1

# # # 1

1 1 1 #

# 1 1 1

1 # # 1

1 # # 1

1 1 1 #

1

&

0awab4

/eduanya tidak is(m(rfik karena jumlah sisi pada graf pertama dan graf kedua

tidak sama. 6raf pertama * + mempunyai % buah sisi, sedangkan graf kedua

* + mempunyai ' buah sisi.

G

G

1* +G

&* +G

Page 19: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 19/44

Graf Planar danBidang

6raf yang 7dapat digambar7 tanpa terjadinya perp(t(ngan antar dua sisi

disebut graf planar. 0ika tidak disebut graf tak-planar. 

6raf planar yang 7digambarkan7 tanpa ada perp(t(ngan antar sisi

disebut graf bidang.

6raf bidang pasti merupakan graf planar, tapi graf planar

 belum tentu graf bidang.

Page 20: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 20/44

)ontoh

%6raf / adalah 6raf 9lanar 

6raf / bukan 6raf 9lanar 

Page 21: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 21/44

)ontoh

 E 

 ! "   ! #   ! $   ! "   ! $ ! #

G%    E G% 

1 & $Terdapat tiga buah rumah , , dan , masing-masing dihubungkan

tiga buah utilitas -air* +, gas* +, dan listrik* +- dengan alat pengantar

*pipa, kabel, dsb+. Mungkinkah membangun utilitas sehingga

 ! ! ! 

% G E 

tidak ada

 pengantar yang saling berp(t(gan;*sebab kalau berp(t(ngan dikhawatirkan

timbul masalah yang serius, misalnya bila kabel listrik berp(t(ngan dengan

 pipa gas dapat terjadi ledakan+

$,$6raf / bukan 6raf 9lanar 

Page 22: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 22/44

)ontoh

6ambarkan graf planar di bawah ini sehingga tidak ada sisi-sisi yang berp(t(ngan *menjadi graf bidang+.

0awab4

)usun kembali sebuah simpul untuk mendapatkan sebuah s(lusi.

Page 23: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 23/44

RmsEler

)isi pada graf bidang membagi bidang datar menjadi beberapa wilayah

* atau +.

0umlah wilayah pada bidang datar termasuk wilayah luar.

0umlah wilayah pada graf planar sederhana dapat dihitung d

region face

engan rumus,

  &

atau

  &

yang dalam hal ini,

  jumlah simpul

  jumlah sisi

n e f  

 f e n

n

e

− + =

= − +

Page 24: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 24/44

)ontoh

 &"

 &' &$ &#

 &(

 &) 

Tentukan jumlah wilayah pada graf planar berikut3

0awab4

& 11 &

0adi, jumlah wilayahnya

 f e n= − + = − + =

Page 25: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 25/44

)ontoh

Misalkan graf sederhana planar dan terhubung memiliki &% buah simpul,

masing-masing simpul berderajat %. =epresentasi planar dari graf tersebut

membagi bidang datar menjadi sejumlah wilayah atau muka. Berapa banyak

wilayah yang terbentuk;

0awab4

iketahui &%, maka jumlah derajat seluruh simpul adalah &% % 5.

Menurut lemma jabat tangan, jumlah derajat & jumlah sisi, sehingga

 jumlah derajat 50umlah sisi * + %.& &

ari ru

n

e

×

×

mus >uler, - &, sehingga

& -

  & - &% %

  &

n e f  

 f jumlah wilayah n e

buah

+ =

= = +

= +

=

Page 26: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 26/44

KetidaksamaanEler

)etiap daerah pada graf planar dibatasi (leh tiga atau lebih sisi. 0adi,

t(tal banyaknya sisi lebih besar atau sama dengan $ . Tetapi, karena

suatu sisi barada pada batas paling banyak dua wilayah, mak 

 f  

a t(tal

 banyaknya sisi lebih kecil atau sama dengan & . 0adi,

&& $ atau

$dari rumus >uler, - &

&sehingga4 &

$

& 1

- & - - &$ $

1- & $ *ketidaksamaan >uler+

$

e

ee f f  

 f e n

ee n

e

e n e n

e n e n

≥ ≥

= +

≥ − +

− ≥ + ⇒ ≥ +

≤ ⇒ ≤ −

)uatu graf dikatakan planar jika memenuhi ketidaksamaan >uler.

0ika tidak memenuhi maka graf dikatakan tidak planar.

Page 27: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 27/44

 * (

)ontoh

%9ada graf / berikut, %, . Tentukan apakan graf tersebutmemenuhi ketidaksamaan >uler;

n e= =

%

0awab4

$ - $*%+ -

karena , maka graf / dikatakan memenuhi

ketidaksamaan >uler $ - . Maka graf tersebut merupakan graf plannar 

n

e

e n

= =

=

Page 28: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 28/44

)ontoh

 * '

'9ada graf / berikut, ', 1#. Tentukan apakah graf di bawah ini

memenuhi /etidaksamaan >uler;

n e= =

'

'

0awab4$ - $*'+ - 5

/arena 1# 5, maka graf / dikatakan

tidak memenuhi /etidaksamaan >uler $ - .

Artinya graf / tidak planar.

n

e

e n

= =

= >

Page 29: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 29/44

9erlu diketahui bahwa /etidaksamaan >uler

merupakan < 7bukan7 .

Artinya jika suatu graf memenuhi /etidaksamaan >uler,

maka belum tentu graf tersebut planar.

 syarat perlu syarat cukup

Page 30: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 30/44

 * $+$

)ontoh

$,$9ada graf bipartit / berikut, , 5. Tentukan apakah graf tersebutmemenuhi /etidaksamaan >uler;

n e= =

$,$

0awab4

$ - $*+ - 1&

idapat 5 1&. ?alaupun memenuhi ketidaksamaan >uler,

kita telah mengetahui bahwa graf / bukan graf planar.

n

e

= =

= <

Page 31: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 31/44

$,$2ntuk menunjukkan bahwa / bukan graf planar menurut

ketidaksamaan >uler, kita perlu membuat asumsi baru bahwa setiap wilayah

 pada graf bidang dibatasi (leh paling sedikit empat buah sisi *% +,

sehi

 f  

ngga berlaku ketidaksamaan4

  & % atau&

dari rumus >uler, - &

sehingga4 - &&

  - - & - - && &

  - & & - %

&

ee f f  

 f e n

e

e n

e ee n n

en e n

≥ ≥

= +

≥ +

≥ + ⇒ ≥ +

≤ ⇒ =

$,$

$,$

dengan demikian, graf tidak memenuhi ketidaksamaan & - %, karena

5<

5 &*+ - % * +

hal ini berarti bahwa bukan graf planar.

 * e n

e n

 salah

 * 

= =

≤ =

Page 32: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 32/44

TeoremaKrato-ski

)ifat graf /urat(wski4

1. /edua jenis graf /urat(wski adalah graf teratur.

&. /edua graf kurat(wski adalah graf tidak planar.

$. 9enghapusan sisi atau simpul dari graf kurat(wski menyebabkan menjadi

graf planar.%. 6raf kurat(wski pertama adalah graf tidak planar dengan jumlah simpul

minimum, sedangkan graf kurat(wski keda adalah graf tidak planar

dengan jumlah sisi minimum. /eduanya adalah graf tidak planar paling

sederhana.

'

Menurut /urat(wski terdapat & jenis graf tidak planar, yaitu4

1. 6raf lengkap yang mempunyai ' buah simpul */ +, adalah

graf tidak planar.

&. 6raf terhubung teratur dengan buah simpul dan 5 buah $,$sisi*/ +

adalah graf tidak planar.

Page 33: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 33/44

 f     e   d 

ca b

G

a b   c

d    e   f  

G"

' $,$

1

6raf adalah tidak planar jika dan hanya jika mengandung upagraf

yang is(m(rfik dengan atau atau h(m(erfik dengan

satu dari keduanya.

9erhatikan graf berikut. 6raf mengandung yang is(m(r 

G

 * * 

G G

$,$

fik

dengan graf , jadi tidak planar. * G

Page 34: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 34/44

d a

e f  

a

b c

 g d 

b   c

 f  

G"

G

a   b   c

d    e f     * $+$

e

1 $,$6raf tidak planar karena upagrafnya is(m(rfik dengan .G G * 

Page 35: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 35/44

v

 x

 y

 * 'G"G

.omeomork 

1 &ua graf 6 dan 6 dikatakan @(me(m(rfik jika salah satu dari kedua graf

tersebut dapat diper(leh dari graf yang lain dengan cara menyisipkan dan atau

membuang secara berulang-ulang simpul yang 7berderajat &7.

& 1

$ &

/etiga graf diatas adalah @(me(m(rfik satu sama lain.

6raf 6 didapat dengan menghilangkan simpul pada 6 .

)edangkan 6 didapat dari 6 dengan menambahkan simpul dan .

v

 x y

Page 36: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 36/44

)ontoh

%

&

1

' $

1#

5

%

&

1

' $

5

%

&

1

' $

%&

'$1

9erlihatkan dengan te(rema /urat(wski bahwa graf 9etersen di bawah

ini tidak 9lanar3

Buatlah sebuah upagrafnya

dengan membuang simpul-

simpul berderajat &.

&

1

/ita akan per(leh

yang h(me(m(rfik 

dengan .

G

G

* + 6raf 9etersenG1

* + 2pagraf dariG G

& 1* + @(me(m(rfik denganG G

$,$ &* +h(me(m(rfik dengan * G

Page 37: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 37/44

Terapan Graf

Planar9erhatikanlah bahwa te(rema /urat(wski lebih mudah digunakan untuk

menentukan bahwa sebuah graf tidak planar. 2ntuk membuktikan bahwa

suatu graf planar relatif lebih sulit.

Terapan graf planar , yaitu pers(alan utilitas dalam merancang jaringan pipa

air, pipa gas, dan kabel listrik bawah tanah agar ketiganya tidak saling

 bersilangan. Terapan graf planar lainnya adalah pada perancangan

integrated circuit *8:+ pada sebuah papan. /awat-kawat yang menghubungkan

simpul-simpul 8: harus dirancang sedemikian rupa agar tidak bersilangan,

sebab persilangan dua buah kawat yang beraliran listrik dapat menimbulkan

interferensi arus, yang mengakibatkan terganggunya fungsi 8: tersebut.

Page 38: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 38/44

GrafDal

Misalkan kita mempunyai sebuah graf planar yang direpresentasikan

sebagai graf bidang. /ita dapat membuat suatu graf bidang B yang secara

ge(metri merupakan dual dari graf tersebut dengan cara4

1.

G

G

 9ada setiap wilayah atau muka * + di , buatlah sebuah simpul B

yang merupakan simpul untuk B .

&. 2ntuk setiap sisi di , tariklah sisi B yang mem(t(ng sisi tersebut.

6raf yang ter 

 face f G v

G

e G e e

 bentuk dengan cara penggambaran demikian disebut graf dual

* + dari graf .dual geometri G

Page 39: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 39/44

v",

v#,

v$,

e,

)ebuah graf memiliki dual hanya jika graf tersebut merupakan graf plannar.

9embentukan graf dual 6B dari graf 6.

Page 40: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 40/44

e- 

e) e'

e(

e#

e$e"

e- 

e) e'

e#

e$

e"

e(

9erhatikan dua representasi bidang yang berbeda dari graf

yang sama di bawah ini.

Telah nyata bahwa kedua graf di atas adalah is(m(rfik.

Calu apakah graf dualnya juga akan is(m(rfik;

6raf dualnya akan dipaparkan pada slide selanjutnya.

Page 41: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 41/44

9erhatikan graf pertama di bawah ini.

i atas merupakan graf dualnya.

Page 42: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 42/44

9erhatikan graf pertama di bawah ini.

i atas merupakan graf dualnya.

Page 43: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 43/44

ari kedua graf dual tersebut dapat kita gambar sebagai berikut.

ari kedua graf dual di atas,

telah terlihat bahwa ternyata keduanya tidak is(m(rfik.

Page 44: Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

7/25/2019 Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

http://slidepdf.com/reader/full/representasi-graf-graf-isomorfik-graf-plannar-dan-graf-dual 44/44

Demikian presentasidari kami

emoga Bermanfaat

TERIMA KAI.