52227885 sirkuit euler

8/13/2019 52227885 Sirkuit Euler

http://slidepdf.com/reader/full/52227885-sirkuit-euler 1/33

Graf

• Graf digunakan untuk merepresentasikan objek-objek diskrit

dan hubungan antara objek-objek tersebut.

• Gambar di bawah ini sebuah graf yang menyatakan peta

jaringan jalan raya yang menghubungkan sejumlah kota di

Provinsi Jawa Tengah.

• Sejarah Graf: masalah jembatan önigsberg !tahun "#$%&

Gambar 1. 'asalah Jembatan önigsberg

• Graf yang merepresentasikan jembatan önigsberg:

Simpul !vertex& menyatakan daratan

Sisi !edge& menyatakan jembatan

"

( r e b e sT e g a l

S l a w i

P e m a l a n g

P u r w o k e r t o

) i l a * a p

( a n j a r n e g a r a

+ o n o s o b o

e b u m e n

P u r w o r e j o

e n d a lS e m a r a n g

P e k a l o n g a n

P u r b a l i n g g a

' a g e l a n g

S a l a t i g a

l a t e n

S o l o

P u r w o d a d i

, e m a k u d u s

- e m b a n g

( l o r a

S u k o h a r j o

+ o n o g i r i

S r a g e n( o y o l a l i

r o y a

T e m a n g g u n g

C

A

B

D

8/13/2019 52227885 Sirkuit Euler


• (isakah melalui setiap jembatan tepat sekali dan kembali lagi

ke tempat semula

Definisi Graf

Graf G / !V 0 E &0 yang dalam hal ini: V / himpunan tidak-kosong dari simpul-simpul !vertices&

/ 1 v" 0 v2 0 ... 0 vn 3

E / himpunan sisi !edges& yang menghubungkan sepasang

simpul

/ 1e" 0 e2 0 ... 0 en 3

G" G2 G$

Gambar 2. !a& graf sederhana0 !b& graf ganda0 dan !*& graf semu

Contoh 1. Pada Gambar 20 G" adalah graf dengan

V / 1 "0 20 $0 4 3

E / 1 !"0 2&0 !"0 $&0 !20 $&0 !20 4&0 !$0 4& 3

G2 adalah graf dengan

V / 1 "0 20 $0 4 3

E / 1 !"0 2&0 !20 $&0 !"0 $&0 !"0 $&0 !20 4&0 !$0 4&0 !$0 4& 3 / 1

e"0 e20 e$0 e40 e50 e%0 e#3

G$ adalah graf dengan

V / 1 "0 20 $0 4 3

E / 1 !"0 2&0 !20 $&0 !"0 $&0 !"0 $&0 !20 4&0 !$0 4&0 !$0 4&0 !$0 $& 3

2

1 1 1

2 3

4

2 3

4

2

4

3

e1

e2

e3

e4

e5

e6

e7

e1

e2

e3

e4

e5

e6

e7

e8

8/13/2019 52227885 Sirkuit Euler


/ 1 e"0 e20 e$0 e40 e50 e%0 e#0 e63

• Pada G20 sisi e$ / !"0 $& dan sisi e4 / !"0 $& dinamakan sisi-

ganda !multiple edges atau paralel edges& karena kedua sisi

ini menghubungi dua buah simpul yang sama0 yaitu simpul "

dan simpul $.

• Pada G$0 sisi e6 / !$0 $& dinamakan gelang atau kalang !loop&

karena ia berawal dan berakhir pada simpul yang sama.

Jenis-Jenis Graf

• (erdasarkan ada tidaknya gelang atau sisi ganda pada suatu

graf0 maka graf digolongkan menjadi dua jenis:

". Graf sederhana ! simple graph&.

Graf yang tidak mengandung gelang maupun sisi-ganda

dinamakan graf sederhana. G" pada Gambar 2 adalah

*ontoh graf sederhana

2. Graf tak-sederhana !unsimple-graph&.

Graf yang mengandung sisi ganda atau gelang dinamakan

graf tak-sederhana !unsimple graph&. G2 dan G$ pada

Gambar 2 adalah *ontoh graf tak-sederhana

• (erdasarkan jumlah simpul pada suatu graf0 maka se*ara

umum graf dapat digolongkan menjadi dua jenis:

". Graf berhingga !limited graph& Graf berhingga adalah graf yang jumlah simpulnya0 n0

berhingga.

2. Graf tak-berhingga !unlimited graph&

$

8/13/2019 52227885 Sirkuit Euler


Graf yang jumlah simpulnya0 n0 tidak berhingga banyaknya

disebut graf tak-berhingga.

• (erdasarkan orientasi arah pada sisi0 maka se*ara umum graf

dibedakan atas 2 jenis:

". Graf tak-berarah !undirected graph&

Graf yang sisinya tidak mempunyai orientasi arah disebut

graf tak-berarah. Tiga buah graf pada Gambar 2 adalah

graf tak-berarah.

2. Graf berarah !directed graph atau digraph&

Graf yang setiap sisinya diberikan orientasi arah disebutsebagai graf berarah. ,ua buah graf pada Gambar $ adalah

graf berarah.

!a& G4 !b& G5

Gambar 3 !a& graf berarah0 !b& graf-ganda berarah

Tabel 1 Jenis-jenis graf 78S99

Jenis Sisi Sisi ganda

dibolehkan

Sisi gelang

dibolehkan

Graf sederhana

Graf ganda

Graf semu

Graf berarah

Graf-ganda berarah

Tak-berarah

Tak-berarah

Tak-berarah

(earah

(earah

Tidak

;a

;a

Tidak

;a

Tidak

Tidak

;a

;a

;a

4

1 1

2 3

4

2 3

4

8/13/2019 52227885 Sirkuit Euler


Contoh Terapan Graf

". Rangkaian listrik .

!a& !b&

2. Isomer senyawa kimia karbon

metana !)<4& etana !)2<%& propana !)$<6&

$. Transaksi konkuren pada basis data terpusat

Transaksi T = menunggu transaksi T " dan T 2

Transaksi T 2 menunggu transaksi T "

Transaksi T " menunggu transaksi T $ Transaksi T $ menunggu transaksi T 2

5

AB

C

DEF

A

BC

E D

F

C

H

H

HH

8/13/2019 52227885 Sirkuit Euler


8/13/2019 52227885 Sirkuit Euler


eterangan:

a : = sen dimasukkan

b : 5 sen dimasukkanc : "= sen dimasukkan

d : "5 sen atau lebih dimasukkan

Terminologi Graf

G" G2 G$

Gambar 4. Graf yang digunakan untuk menjelaskan terminologi pada graf

1. Ketetanggaan ( Adjacent

,ua buah simpul dikatakan bertetangga bila keduanya terhubung

langsung.

Tinjau graf G" : simpul " bertetangga dengan simpul 2 dan $0simpul " tidak bertetangga dengan simpul 4.

2. !ersisian ( Incidency

Hntuk sembarang sisi e / !v 0 vk & dikatakan

e bersisian dengan simpul v 0 atau

e bersisian dengan simpul vk

Tinjau graf G": sisi !20 $& bersisian dengan simpul 2 dan simpul $0sisi !20 4& bersisian dengan simpul 2 dan simpul 40

tetapi sisi !"0 2& tidak bersisian dengan simpul 4.

3. "imp#l Terpen$il ( Isolated Vertex

#

1

32

4

1

2

3

4

5

1

2

e1

e2

e3

e4

e53

8/13/2019 52227885 Sirkuit Euler


"impul terpencil ialah simpul yang tidak mempunyai sisi yang

bersisian dengannya.

Tinjau graf G": simpul 5 adalah simpul terpen*il.

4. Graf Kosong (null graph ata# empty graph

Graf yang himpunan sisinya merupakan himpunan kosong ! # n&.

Graf # 5 :

%. Dera&at ( Degree

$eraat suatu simpul adalah jumlah sisi yang bersisian dengan

simpul tersebut.

Iotasi: d !v&

Tinjau graf G":

d !"& / d !4& / 2d !2& / d !$& / $

Tinjau graf G$: d !5& / = simpul terpen*il

d !4& / " simpul anting-anting ! pendant vertex&

Tinjau graf G2: d !"& / $ bersisian dengan sisi ganda

d !2& / 4 bersisian dengan sisi gelang !loop&

Pada graf berarah0

d in!v& / derajat-masuk !in-degree&

/ jumlah busur yang masuk ke simpul v

d out!v& / derajat-keluar !out-degree&

6

1

2

3

4

5

8/13/2019 52227885 Sirkuit Euler


8/13/2019 52227885 Sirkuit Euler


Tinjau graf G$: d !"& @ d !2& @ d !$& @ d !4& @ d !5&

/ 2 @ 2 @ $ @ " @ = / 6

/ 2 × jumlah sisi / 2 × 4

Contoh 2. ,iketahui graf dengan lima buah simpul. ,apatkah kita

menggambar graf tersebut jika derajat masing-masing simpul

adalah:

!a& 20 $0 "0 "0 2

!b& 20 $0 $0 40 4

Penyelesaian:!a&tidak dapat0 karena jumlah derajat semua simpulnya ganjil

!2 @ $ @ " @ " @ 2 / 9&.

!b& dapat0 karena jumlah derajat semua simpulnya genap

!2 @ $ @ $ @ 4 @ 4 / "%&.

. 'intasan ( Path

'intasan yang panjangnya n dari simpul awal v= ke simpul tujuan

vn di dalam graf G ialah barisan berselang-seling simpul-simpuldan sisi-sisi yang berbentuk v=0 e"0 v"0 e20 v20... 0 vn "0 en0 vn

sedemikian sehingga e" / !v=0 v"&0 e2 / !v"0 v2&0 ... 0 en / !vn-"0 vn&

adalah sisi-sisi dari graf G.

"=

8/13/2019 52227885 Sirkuit Euler


8/13/2019 52227885 Sirkuit Euler


Graf berarah G dikatakan terhubung jika graf tidak berarahnya

terhubung !graf tidak berarah dari G diperoleh dengan

menghilangkan arahnya&.

,ua simpul0 u dan v0 pada graf berarah G disebut terh#b#ng k#at! strongly connected & jika terdapat lintasan berarah dari u ke v dan

juga lintasan berarah dari v ke u.

Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak

berarahnya0 maka u dan v dikatakan terh#b#ng lemah !weakly

coonected &.

Graf berarah G disebut graf terh#b#ng k#at ! strongly connected

graph& apabila untuk setiap pasang simpul sembarang u dan v di G0terhubung kuat. alau tidak0 G disebut graf terh#b#ng lemah.

graf berarah terhubung lemah graf berarah terhubung kuat

+. ,pagraf ( Subgraph dan Komplemen ,pagraf

'isalkan G / !V 0 E & adalah sebuah graf. G" / !V "0 E "& adalah

#pagraf ! subgraph& dari G jika V " ⊆ V dan E " ⊆ E .

Komplemen dari upagraf G" terhadap graf G adalah graf G2 / !V 20 E 2& sedemikian sehingga E 2 / E - E " dan V 2 adalah himpunan

simpul yang anggota-anggota E 2 bersisian dengannya.

"2

1

2

3 4

1

2 3

8/13/2019 52227885 Sirkuit Euler


!a& Graf G" !b& Sebuah upagraf !*& komplemen dari upagraf !b&

Komponen graf !connected component & adalah jumlah maksimum

upagraf terhubung dalam graf G.

Graf G di bawah ini mempunyai 4 buah komponen.

Pada graf berarah0 komponen terhubung kuat ! strongly connected

component & adalah jumlah maksimum upagraf yang terhubung

kuat.

Graf di bawah ini mempunyai 2 buah komponen terhubung kuat:

"$

1

2

3

4 5

6

1

6

5

31

2

3

52

1

2 3 4

5

6 7

8

9

1 0

1 1

1 2

1 3

2 3

4

5

1

8/13/2019 52227885 Sirkuit Euler


8/13/2019 52227885 Sirkuit Euler


Gra! berbobot adalah graf yang setiap sisinya diberi sebuah harga

!bobot&.

!eberapa Graf "ederhana Kh#s#s

a. Graf 'engkap (Complete Graph

Graf lengkap ialah graf sederhana yang setiap simpulnya mempunyai sisi

ke semua simpul lainnya. Graf lengkap dengan n buah simpul dilambangkan

dengan & n. Jumlah sisi pada graf lengkap yang terdiri dari n buah simpul

adalah n!n "&K2.

& " & 2 & $ & 4 & 5 & %

b. Graf 'ingkaran

Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua.

Graf lingkaran dengan n simpul dilambangkan dengan % n.

"5

a

b

c d

e

1 0 1 2

8

1 5 91 1

1 4

8/13/2019 52227885 Sirkuit Euler


$. Graf Terat#r ( egular Graphs

Graf yang setiap simpulnya mempunyai derajat yang sama disebut graf

terat#r. Lpabila derajat setiap simpul adalah r 0 maka graf tersebut disebut

sebagai graf teratur derajat r . Jumlah sisi pada graf teratur adalah nr K2.

d. Graf !ipartite ( !ipartite Graph

Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan

bagian V " dan V 20 sedemikian sehingga setiap sisi pada G menghubungkan

sebuah simpul di V " ke sebuah simpul di V 2 disebut graf bipartit dan

dinyatakan sebagai G!V "0 V 2&.

V " V 2

Graf G di bawah ini adalah graf bipartit0 karena simpul-simpunya dapat

dibagi menjadi V " / 1a0 b0 d 3 dan V 2 / 1c0 e0 ! 0 g 3

G

"%

a b

c

d e

f

g

8/13/2019 52227885 Sirkuit Euler


graf persoalan utilitas0 topologi bintang

epresentasi Graf

1. 0atriks Ketetanggaan (adjacency matrix

' / 7ai0

"0 jika simpul i dan bertetangga

ai / 1

=0 jika simpul i dan tidak bertetangga

)ontoh:

4$2" 54$2"

4$2"

"#

H 2

H 3

W G E

1

32

4

1

23

4

5

1

2 3

4

8/13/2019 52227885 Sirkuit Euler


4

$

2

"

=""=

"=""

""="

=""=

=====

=="==

="=""

=="="

==""=

5

4

$

2

"

4

$

2

"

=""=

==="

""="

=="=

!a& !b& !*&

4$2"

4

$

2

"

=2"=

2""2

""="

=2"=

,erajat tiap simpul i:!a& Hntuk graf tak-berarah0

d !vi& / ∑=

n

ia

"

!b& Hntuk graf berarah0

d in !v & / jumlah nilai pada kolom / ∑=

n

i

ia

"

d out !vi& / jumlah nilai pada baris i / ∑=

n

ia"

"6

1

2

4

3

e1

e2

e3

e4

e5

e6

e7

e 8

8/13/2019 52227885 Sirkuit Euler


a b c d e

∞∞

∞∞

∞∞∞

∞

∞∞∞

"56"=

"5"4""

"49

6""9"2

"="2

e

d

c

b

a

2. 0atriks !ersisian (incidency matrix

' / 7ai0

"0 jika simpul i bersisian dengan sisi

ai / 1

=0 jika simpul i tidak bersisian dengan sisi

"9

a

b

c d

e

1 0 1 2

8

1 5 91 1

1 4

1 2

3

4

e1

e2

e3

e4

e5

8/13/2019 52227885 Sirkuit Euler


e" e2 e$ e4 e5

4

$

2

"

"====

"""==

=="""

="=""

3. "enarai Ketetanggaan (adjacency list

Simpul

Simpul Tetangga Simpul Simpul Tetangga Simpul Simpul Terminal

" 20 $ " 20 $ " 2

2 "0 $0 4 2 "0 $ 2 "0 $0 4

$ "0 20 4 $ "0 20 4 $ "

4 20 $ 4 $ 4 20 $

5 -

!a& !b& !*&

Graf somorfik ( Isomorphic Graph

• ,ua buah graf yang sama tetapi se*ara geometri berbeda disebut grafyang saling isomorfik .

• ,ua buah graf0 G" dan G2 dikatakan isomorfik jika terdapat

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

sisi keduaya sedemikian sehingga hubungan kebersisian tetap terjaga.

2=

1

32

4

1

23

4

5

1

2 3

4

8/13/2019 52227885 Sirkuit Euler


8/13/2019 52227885 Sirkuit Euler


Gambar .3 Graf !a& dan graf !b& isomorfik 7,M8#4

ed cba ( vw y x

'G" /

e

d

c

b

a

="===

"="="

="=""

=="="

="""=

'G2 /

(

v

w

y

x

="===

"="="

="=""

=="="

="""=

!a&

!b&

Gambar .3+ !a& ,ua buah graf isomorfik0 !b& tiga buah graf isomorfik

,ari definisi graf isomorfik dapat dikemukakan bahwa dua buah graf

isomorfik memenuhi ketiga syarat berikut 7,M8#4:

". 'empunyai jumlah simpul yang sama.

2. 'empunyai jumlah sisi yang sama

$. 'empunyai jumlah simpul yang sama berderajat tertentu

Iamun0 ketiga syarat ini ternyata belum *ukup menjamin. Pemeriksaan

se*ara visual perlu dilakukan.

22

8/13/2019 52227885 Sirkuit Euler


!a& !b&

Graf )lanar ( Planar Graph dan Graf !idang ( Plane Graph

Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak salingmemotong disebut sebagai graf planar0 jika tidak0 ia disebut graf tak-

planar.

Gambar .4/ & 4 adalah graf planar

2$

x

u

v

w

y

8/13/2019 52227885 Sirkuit Euler


Gambar .41 & 5 bukan graf planar

Graf planar yang digambarkan dengan sisi-sisi yang tidak saling

berpotongan disebut graf bidang ! plane graph&.

!a& !b& !*&

Gambar .42 Tiga buah graf planar. Graf !b& dan !*& adalah graf bidang

Contoh .2. Persoalan utilitas !utility problem&

!a& !b&

Gambar .43 !a& Graf persoalan utilitas ! & $0$&0 !b& graf persoalan utilitas

bukan graf planar.

Sisi-sisi pada graf planar membagi bidang menjadi beberapa wilayah

!region& atau muka ! !ace&. Jumlah wilayah pada graf planar dapat dihitung

dengan mudah.

24

H 2

H 3

W G E

H 2

H 3

W G E

H 1

H 1

R1

R2

R3

R5

R4

R6

8/13/2019 52227885 Sirkuit Euler


Gambar .44 Graf planar yang terdiri atas 4 wilayah

#m#s #ler

n ) e * ! / 2 !%.5&

yang dalam hal ini0

! + jumlah wilayah

e / jumlah sisi

n / jumlah simpul

Contoh .2*. Pada Gambar %.440 e / "" dan n / #0 maka ! / "" # @ 2 / %.

Pada graf planar sederhana terhubung dengan ! wilayah0 n buah simpul0 dan

e buah sisi !dengan e B 2& selalu berlaku ketidaksamaan berikut:

e ≥ $ ! K2

dan

e ≤ $n %

Contoh .2+. Pada Gambar %.44 di atas0 % ≥ $!4&K2 dan % ≤ $!4& 2.

etidaksaamaan

e ≤ $n %

tidak berlaku untuk graf & $0$

karena

e / 90 n / %

9 ≤ !$&!%& % / "2!jadi0 e ≤ $n %&

25

8/13/2019 52227885 Sirkuit Euler


padahal graf & $0$ bukan graf planar>

(uat asumsi baru: setiap daerah pada graf planar dibatasi oleh paling sedikit

empat buah sisi0

,ari penurunan rumus diperoleh

e ≤ 2n - 4

Contoh .2. Graf & $0$ pada Gambar %.4$!a& memenuhi ketidaksamaan e ≤

2n %0 karena

e / 90 n / %9 ≤ !2&!%& 4 / 6 !salah&

yang berarti & $0$ bukan graf planar.

Teorema K#ratoski

(erguna untuk menentukan dengan tegas keplanaran suat graf.

2%

8/13/2019 52227885 Sirkuit Euler


!a& !b& !*&

Gambar .4% !a& Graf uratowski pertama

!b& dan !*& Graf uratowski kedua !keduanya

isomorfik&

Sifat graf uratowski adalah:

". edua graf uratowski adalah graf teratur.

2. edua graf uratowski adalah graf tidak-planar

$. Penghapusan sisi atau simpul dari graf uratowski menyebabkannya

menjadi graf planar.

4. Graf uratowski pertama adalah graf tidak-planar dengan jumlah simpul

minimum0 dan graf uratowski kedua adalah graf tidak-planar dengan

jumlah sisi minimum.

T05 K#ratoski. Graf G bersifat planar jika dan hanya jika ia tidak

mengandung upagraf yang sama dengan salah satu graf uratowski atau

homeomorfik !homeomorphic& dengan salah satu dari keduanya.

G" G2 G$

Gambar .4 Tiga buah graf yang homemorfik satu sama lain.

Contoh .3/. Sekarang kita menggunakan Teorema uratowski untuk

memeriksa keplanaran graf. Graf G pada Gambar %.4# bukan graf planar

karena ia mengandung upagraf !G"& yang sama dengan & $0$.

2#

v

x

y

8/13/2019 52227885 Sirkuit Euler


8/13/2019 52227885 Sirkuit Euler


Sirkuit Muler ialah sirkuit yang melewati masing-masing sisi tepat satu kali..

Graf yang mempunyai sirkuit Muler disebut graf #ler ! Eulerian graph&.

Graf yang mempunyai lintasan Muler dinamakan juga graf semi-#ler

! semi-Eulerian graph&.

Contoh .31. Fintasan Muler pada graf Gambar %.42!a& : $0 "0 20 $0 40 "

Fintasan Muler pada graf Gambar 5.42!b& : "0 20 40 %0 20 $0 %0 50 "0 $

Sirkuit Muler pada graf Gambar %.42!*& : "0 20 $0 40 #0 $0 50 #0 %0 50 20 %0 "

Sirkuit Muler pada graf Gambar %.42!d& : a0 c0 ! 0 e0 c0 b0 d 0 e0 a0 d 0 ! 0 b0 a

Graf !e& dan !f& tidak mempunyai lintasan maupun sirkuit Muler

Gambar .42 !a& dan !b& graf semi-Muler

!*& dan !d& graf Muler

!e& dan !f& bukan graf semi-Muler atau graf Muler

T05 .2. Graf tidak berarah memiliki lintasan Muler jika dan hanya

jika terhubung dan memiliki dua buah simpul berderajat ganjil atau tidak ada

simpul berderajat ganjil sama sekali.

29

12

3 4

1 2

3

4

5 6

1

2 3

4

5

6 7

a

b

e

d

c

f

ba

c d

1 2

3

4 5 e

! a & ! b & ! * &

! d & ! e & ! f &

8/13/2019 52227885 Sirkuit Euler


T05 .3. Graf tidak berarah G adalah graf Muler !memiliki sirkuit

Muler& jika dan hanya jika setiap simpul berderajat genap.

!)atatlah bahwa graf yang memiliki sirkuit Muler pasti mempunyai lintasan Muler0 tetapi tidak sebaliknya&

T05 .4. Graf berarah G memiliki sirkuit Muler jika dan hanya jikaG terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar

sama. G memiliki lintasan Muler jika dan hanya jika G terhubung dan setiap

simpul memiliki derajat-masuk dan derajat-keluar sama ke*uali dua simpul0

yang pertama memiliki derajat-keluar satu lebih besar derajat-masuk0 dan

yang kedua memiliki derajat-masuk satu lebih besar dari derajat-keluar.

Gambar .43 !a& Graf berarah Muler !a0 g 0 c0 b0 g 0 e0 d 0 ! 0 a&

!b& Graf berarah semi-Muler !d 0 a0 b0 d 0 c0 b&

!*& Graf berarah bukan Muler maupun semi-Muler

Gambar .44 (ulan sabit 'uhammad

'intasan dan "irk#it 6amilton

$=

a

b

c

d e

f g

a b

c d

a b

c d

! a & ! b & ! * &

8/13/2019 52227885 Sirkuit Euler


8/13/2019 52227885 Sirkuit Euler


derajat tiap simpul paling sedikit nK2 !yaitu0 d !v& ≥ nK2 untuk setiap simpul v

di G&.

T05 .. Setiap graf lengkap adalah graf <amilton.

T05 .*. ,i dalam graf lengkap G dengan n buah simpul !n ≥ $&0

terdapat !n - "&>K2 buah sirkuit <amilton.

T05 .+. ,i dalam graf lengkap G dengan n buah simpul !n ≥ $ dan

n ganjil&0 terdapat !n - "&K2 buah sirkuit <amilton yang saling lepas !tidak

ada sisi yang beririsan&. Jika n genap dan n ≥ 40 maka di dalam G terdapat

!n - 2&K2 buah sirkuit <amilton yang saling lepas.

Contoh .33. !Persoalan pengaturan tempat duduk&. Sembilan anggota

sebuah klub bertemu tiap hari untuk makan siang pada sebuah meja bundar.

'ereka memutuskan duduk sedemikian sehingga setiap anggota mempunyai

tetangga duduk berbeda pada setiap makan siang. (erapa hari pengaturan

tersebut dapat dilaksanakan

Jumlah pengaturan tempat duduk yang berbeda adalah !9 - "&K2 / 4.

Gambar .4* Graf yang merepresentasikan persoalan pengaturan tempat

duduk.

$2

1

2

3

5

6

7

8

9

8/13/2019 52227885 Sirkuit Euler


(eberapa graf dapat mengandung sirkuit Muler dan sirkuit <amilton sekaligus0 mengandung sirkuit Muler

tetapi tidak mengandung sirkuit <amilton0 mengandung sirkuit Muler dan lintasan <amilton0 mengandung

lintsan Muler maupun lintasan <amilton0 tidak mengandung lintasan Muler namun mengandung sirkuit

<amilton0 dan sebagainya. Graf pada Gambar !a& mengandung sirkuit <amilton maunpun sirkuit Muler0

sedangkan graf pada Gambar %.46!b& mengandung sirkuit <amilton dan lintasan Muler !periksa>&.

!a& !b&

Gambar .4+ !a& Graf <amilton sekaligus graf Muler

!b& Graf <amilton sekaligus graf semi-Muler

6

5

4

1

3

2

5

1 2

34

52227885 sirkuit euler

Documents