Pengertian Graph Euler Dan Semi Euler Lengkap

8/17/2019 Pengertian Graph Euler Dan Semi Euler Lengkap

http://slidepdf.com/reader/full/pengertian-graph-euler-dan-semi-euler-lengkap 1/15

1. Pengertian Graph Euler dan Semi Euler

Sebuah sirkit di graph G yang memuat semua sisi G disebut sirkit

euler. Jika graph G memuat sirkit Euler, maka graph G disebut graph Euler .

Sebuah jejak-buka yang memuat semua sisi graph disebut jejak Euler .

Graph G disebut graph semi-Euler jika G memuat jejak Euler. Sebagai

contoh, perhatikan gembar 1, graph G1 adalah graph Euler karena memuat

sirkit Euler S = (1, !, ", #, $, ", 1, $, %, 1&, graph G! adalah graph semi-

euler karena memuat jejak Euler buka J = (1, !, #, ", 1, #&, sedangkan

graph G# bukan graph Euler maupun semi-Euler.

Gambar 1 : G1 graph Euler ; G2 graph semi-Euler ; G3 bukan Euler dan

bukan semi-Euler

2. Karakterisasi Graph Euler dan Semi-Euler

'erhatikan graph G1 pada gambar 1, setiap titik G1 berderajat genap,

dan ternyata ini merupakan syarat perlu dan cukup untuk menyompulkan G1

graph Euler. ukti )ormal tentang hal tersebut dapat dillihat pada teorema

berikut.

Teorema 1 : misalkan G graph terhubung. Graph G Euler jika dan hanya jika

setiap titik G berderajat genap.

ukti: Jika G graph Euler maka G memuat sirkit Euler. *isalkan S sirkit Euler

di G yang bera+al dan berakhir di titik 1. 'andang sebuah titik sembarang di

G, sebut saja titik . karena G terhubung maka titik termuat di S. jika 1

maka adalah titik internal S. dalam menelusuri S, setiap kali mele+ati titik

Oleh : Chaerunnisa Darwis, Oky Markianto, Mufihatul irdausi



, digunakan dua sisi S yang terkait di , yaitu satu sisi saat menuju dan

satu sisi lain saat meninggalkan . jika dalam menelusuri S titik dile+ati

sebanyak k kali, maka banyaknya sisi S yang terkait di titik adalah !k dank

arena S memuat semua sisi G, maka banyaknya sisi G yang terkait di ititik

juga sama dengan !k. jadi derajat titik di G adalah !k (genap&. Jika = ,

maka titik a+al sekaligus titik akhir dari S. /alam menelusuri S, pada saat

pertama kali meninggalkan titik (titik sebagai titik a+al&, digunakan satu

sisi S dan pada saat mele+ati titik dan sebagai titik internal S, digunakan

dua sisi S dan akhirnya pada saat menuju titik (titik sebagai titik akhir S&,

digunakan satu sisi S. Jika dalam menelusuri semua sisi S, titik dile+ati

sebanyak k kali sebagai titik internal, maka banyaknya sisi S yang terkait di

titik adalah 10!k01. Jadi derajat titik di graph G adalah 10!k01 = !k0!

= !(k01&, genap.

Sebaliknya akan dibuktikan, dengan induksi kuat pada banyaknya sisi G.

ntuk 2E(G&2=1, jelas G adalah graph dengan satu titik dan satu gelung di

titik itu. Jadi G graph Euler. 3sumsi 4 jika G graph terhubung dan derajat

setiap titik G genap serta 2E(G&25 k, maka G graph Euler. *isalkan graph G

terhubung dengan k01 sisi. 6arena derajat setiap titik G genap, maka 7 (G&

8 !. Sehingga G memuat sikel. *isalkan sikel tersebut 9. hapus semua sisi 9

dari G, diperoleh graph : = G ; E(9&. Jelas setiap titik di : berderajat genap

dan sangat mungkin : tak terhubung. *isalkan :1, :!, < , :t adalah

komponen-komponen graph :. karena setiap komponen : memenuhi premis

asumsi, maka setiap komponen : adalah graph Euler. *isalkan Si adalah

sirkit Euler di :i,∀ , 15 i 5 t. Sirkit Euler di G dapat dikonstruksi sebagai

berikut 4

era+al dari sebuah titik di 9, telusuri sisi-sisi 9 samapai ke suatu titik,

katakan 1, yang termuat di sebuah komponen :, katakana :1 selanjutnya

telusuri sirkit Euler S1 di :1 bera+al dan berakhir di 1 selanjutnya telusuri

sisi-sisi 9 yang belum ditelusuri sampai ke sebuah titik, katakan !, yang




termuat di sebuah komponen : yang lain, katakana :! selanjutnya telusuri

sirkit Euler S! di :! bera+al dan berakhir di ! selanjutnya telusuri sisi-sisi 9

yang belum ditelusuri sampai ke sebuah titik di komponen : yang lain.

'roses ini dilanjutkan sampai tertelusuri sirkit Euler di komponen : yang

terakhir setelah itu telusuri sisi-sisi 9 yang belum tertelusuri sampai

akhirnya ke titik . Jelas sirkit yang diperoleh memuat semua sisi G. Jadi G

graph Euler. /engan demikian teorema terbukti.

>eorema di atas merupakan karakterisasi graph Euler. 6arakterisasi graph

semi-Euler diberikan dalam teorema berikut.

Teorema 2 : Misalkan G graph terhubung. Graph G semi!Euler jika dan

hanya jika G memuat tepat dua titik berderajat ganjil. "ebih jauh, jejak Euler

di G berawal di sebuah titik berderajat ganjil dan berakhir di sebuah titik

berderajat ganjil yang lainnya.

Bukti : Jika G graph semi-Euler, maka G memuat jejak-Euler-buka. *isalkan J

jejak-Euler-buka di G yang bera+al di titik u dan berakhir di titik . 6aren G

terhubung maka J memuat semua titik G. misalkan ϵ ?(G&. >erdapat tiga

kemungkinan yaitu = u, u dan .

Jika = u, maka dalam menelusuri jejak J pertama-tama digunakan satu sisi J

yang terkait di , kemudian setiap kali mele+ati dan sebagai titik internal

J digunakan dua sisi J yang terkait di . apabila dalam menelusuri J titik

mele+ati sebanyak k kali sebagai titik internal, maka banyaknya sisi J yang

terkait di titik adalah 10!k. /engan demikian derajat titik di G adalah

!k01 (ganjil&.

Jika = , maka sebagai titik akhir jejak J. /alam menelusuri jejak J, setiap

kali mele+ati titik dan titik sebagai titik internal J, digunakan dua sisi J

yang terkait di titik . /an akhirnya digunakan satu sisi J yang terkait di

saat menuju titi dan sebagai titik akhir. Jika dalam menelusuri J titik

dile+ati sebanyak r kali dan sebagai titik internal, maka banyaknya sisi J




yang terkait di titik adalah !r01. /engan demikian derajat titik di G

adalah !r01 (ganjil&.

Jika # $ u dan # $ % , maka # adalah titik internal jejak &. seperti

sebelumnya, jika menelusuri semua sisi & titik # dile+ati sebanyak m kali,

maka banyaknya sisi & yang terkait di titik # adalah 'm. Jadi derajat titik # di

graph G adalah 'm (genap&.

/engan demikian dapat disimpulkan graph G memiliki tepat dua titik

berderajat ganjil yaitu titik a+al dan titik akhir jejak .

Selanjunya akan dibuktikan kebalikannya. Graph G terhubung dan

memiliki tepat dua titik berderajat ganjil. *isalkan titik berderajat ganjil

tersebut adalah titik u dan titik % . entuklah graph ( dari G dengan caramenghubungkan titik u dan titik % dengan sebuah sisi baru, sebut sisi e. jadi

( ) ∪ *e+ dengan e ) u% dan e ∉ EG-. Jelas graph ( terhubung dan

setiap titik ( berderajat genap. erdasrkan >eorema %.1, graph tersebut

adalah graph Euler. *isalkan adalah sirkit Euler di ( yang bera+al dan

berakhir di titik % sedemikian hingga sisi e merupakan sisi pertama di .

*aka / *e+ merupakan jejak Euler buka di G yang bera+al di titik u dan

berakhir di titik % . 3kibatnya, G graph semi-Euler. /engan demikian bukti

lengkap.

agaimanakah caranya mengkonstruksi sebuah sirkit (jejak& Euler

graph Euler

(semi-Euler&@ Ja+abannya, dengan menggunakan 3goritma Aleury, yang

diberikan pada subbab berikut.

3. !lgoritma "leur#3lgoritma Aleury digunakan untuk mengkonstruksi sebuah sirkit Euler

pada graph Euler. erikut disajikan langkah-langkah sistematis dari algoritma

tersebut.

B'> 4 Graph Euler G




S>E' 1 4 0ilih sebuah titikV

0 di graph G. 1ulisJ 0=V

0

S>E' ! 4 *isalkan jejeka J i=(V 0 ,e 1 ,V 1 ,… ,V j−1 , ei ,V i) telah terpilih.

Selanjutnya, pilih sebuah sisi ei+1 dari E (G )−{e1 , e2 , ..., ei}

sedemikian hingga 4

(i& Sisiei+1 terkait di titik

V i , dan

(ii& Sisiei+1 bukan sisi-pemutus pada graph

Gi , dengan

Gi=G− {e1 , e2

,… ,ei } , kecuali tidak ada pilihan lain.

>ulis jejak J i+1=J i∪

{ei }

S>E' # 4 S>C' bila S>E' ! tidak bias dilanjutkan dan beri pesan D J

i+1

adalah jejak Euler tutup (sirkit Euler& di graph G

erikut diberikan contoh penerapan algoritm Aleury pada graph Euler G yang

terdapat pada Gambar !. 'erhatikan bah+a setiap titik G berderajat genap

dan G graph terhubung.

Gambar 2 : Graph Euler

STEP 1 4 'ilih titikV

1 . >ulis jejakJ 0=V

1 .

STEP 2 4 JejakJ 0 telah terpilih.

'ilih sisie1=V

1V

5 . >ulis jejak J 1=(V 1 , e1, V 5)




'ilih sisie2=V

5V

6 . >ulis jejak J 2=(V 1, e1,V 5 , e2 ,V 6)

'ilih sisie3=V

6V

2 . >ulis jejak J 3=(V 1, e1 ,V 5 , e2 ,V 6 , e3 ,V 2)

'ilih sisie4=V

2V

1

. >ulis jejakJ 4=(V 1 , e1 ,V 5, e2 ,V 6 , e3 ,V 2 , e4 ,V 1)

'ilih sisie5=V

1V

6 . >ulis jejak J 5=(V 1, e1 ,V 5 , e2 ,V 6 , e3 ,V 2, e4 , V 1, e5 ,V 6)

'ilih sisie6=V

6V

2 . >ulis jejak J 6=(V 1 ,e 1 ,V 5 , e2,V 6 , e3 ,V 2, e4 , V 1, e5 ,V 6 , e6 ,V 2)

'ilih sisie7=V

2V

3 . >ulis jejak

J 7=(V 1 ,e 1 ,V 5 , e2,V 6 , e3 ,V 2, e4 ,V 1, e5 ,V 6 , e6 ,V 2 , e7 , V 3)

'ilih sisie8=V

3V

6 . >ulis jejak

J 8=(V 1 ,e1 ,V 5 , e2,V 6 , e3 , V 2, e4 ,V 1, e5 ,V 6 , e6 ,V 2 , e7 ,V 3 , e8 , V 6)

'ilih sisie9=V

6V

7 .

>ulis jejak J 9=(V 1 ,e1 ,V 5 , e2,V 6 , e3 ,V 2, e4 , V 1, e5 ,V 6 , e6 ,V 2 , e7 ,V 3 , e8 , V 6 ,e9 , V 7)

'ilih sisie10=V

7V

3 .

>ulis jejak J 10=(V 1 , e1,V 5 , e2 , V 6 ,e3 ,V 2 , e4 ,V 1, e5 ,V 6 , e6 ,V 2 , e7 ,V 3 , e8 ,V 6 , e9 ,V 7 , e10 ,V 3)

'ilih sisie11=V

3V

4 .

>ulis jejakV

1,e

1,V

5, e

2,V

6, e

3,V

2, e

4, V

1, e

5,V

6, e

6,V

2, e

7,V

3, e

8,V

6,e

9,V

7, e

10,V

3,

J 11=¿

e11,V

4¿

'ilih sisie12=V

4V

8 .

>ulis jejakV

1,e

1,V

5, e

2,V

6, e

3,V

2, e

4, V

1, e

5,V

6, e

6,V

2, e

7,V

3, e

8,V

6,e

9,V

7, e

10,V

3,

J 12=¿

e11,V

4, e

12,V

8¿




'ilih sisie13=V

8V

7 .

>ulis jejakV

1,e

1,V

5, e

2,V

6, e

3,V

2, e

4, V

1, e

5,V

6, e

6,V

2, e

7,V

3, e

8,V

6,e

9,V

7, e

10,V

3,

J 13=¿

e11,V

4, e

12,V

8, e

13,V

7¿

'ilih sisie14=V

7V

4 .

>ulis jejakV

1,e

1,V

5, e

2,V

6, e

3,V

2, e

4, V

1, e

5,V

6, e

6,V

2, e

7,V

3, e

8,V

6,e

9,V

7, e

10,V

3,

J 14=¿

e11,V

4, e

12,V

8, e

13,V

7,e

14,V

4¿

'ilih sisie15=

V 4V

1 .

>ulis jejakV

1,e

1,V

5, e

2,V

6, e

3,V

2, e

4, V

1, e

5,V

6, e

6,V

2, e

7,V

3, e

8,V

6,e

9,V

7, e

10,V

3,

J 15=¿

e11,V

4, e

12,V

8, e

13,V

7,e

14,V

4, e

15,V

1¿

S>E' # 4 6arena S>E' ! tidak dapat dilanjutkan lagi maka S>C', danV

1,e

1,V

5, e

2,V

6, e

3,V

2, e

4,V

1, e

5,V

6, e

6,V

2, e

7,V

3, e

8,V

6,e

9,V

7, e

10, V

3, e

11,

J 15=¿

V 4, e

12,V

8,e

13,V

7, e

14,V

4, e

15,V

1¿ adalah sirkit Euler di graph G.

Fabel sisi sirkit EulerJ 15 dapat dilihat pada gambar berikut.




Gambar 3 : Sisi-sisi sirkit Euler J15 pada G secara berturut-

turut adalahe1, e

2, e

3, e

4, e

5,e

6, e

7, e

8,e

9, e

10, e

11, e

12, e

13, e

14, e

15

$!T!T!% 4

3lgoritma Aleury dapat dimodikasi sehingga bias digunakan untuk

mencari jejak-Euler-buka pada graph semi Euler yaitu dengan mengganti

DGraph Euler G pada B'> dengan Graph semi Euler G S>E' 1 diganti

menjadi 4 D'ilih sebuah titikV

0 yang berderajat ganjil di G. >ulis jejak

J 0=V

0,

pada S>E' #, pesannya menjadi 4 D J

i+1 jejak Euler buka di graph

G2 .

Sebagai contoh, perhatikan graph G pada Gambar " berikut. Graph G

terhubung dan memiliki tepat dua titik berderajat ganjil, yaitu titikV

3 dan

titikV

6 , titik-titik yang lainnya berderajat genap. Jadi G adalah graph semi

Euler.




Gambar & : Graph G adalah graph semi-Euler

/engan penerapan algiritma Aleury yang termodikasi, diperoleh4

S>E' 1 4 'ilih titik #. >ulis jejak JH = #.

S>E' ! 4 Jejak JH telah terpilih.

'ilih sisi e1 = #1. >ulis jejak J1 = (#,e1,1&

'ilih sisi e! = 1!. >ulis jejak J! = (#,e1,1,e!,!&

'ilih sisi e# = ! #. >ulis jejak J# = (#,e1,1,e!,! ,e#,#&

'ilih sisi e" = #". >ulis jejak J" = (#,e1,1,e!,! ,e#,#, e" ,"&

'ilih sisi e$ = "!. >ulis jejak J$ = (#,e1,1,e!,! ,e#,#, e" ,", e$ ,!&

'ilih sisi e% = !$. >ulis jejak J% = (#,e1,1,e!,! ,e#,#, e" ,", e$ ,!,

e% ,$&

'ilih sisi eI = $1. >ulis jejak JI = (#,e1,1,e!,! ,e#,#, e" ,", e$ ,!,

e% ,$, eI ,1&

'ilih sisi e = 1". >ulis jejak J = (#,e1,1,e!,! ,e#,#, e" ,", e$ ,!,

e% ,$, eI ,1, e ,"&

'ilih sisi eK = "%. >ulis jejak JK = (#,e1,1,e!,! ,e#,#, e" ,", e$ ,!,

e% ,$, eI ,1, e ,", eK ,%&

'ilih sisi e1H = %. >ulis jejak J1H = (#,e1,1,e!,! ,e#,#, e" ,", e$

,!, e% ,$, eI ,1, e ,", eK ,%, e1H ,&

'ilih sisi e11 = 1H. >ulis jejak J11 = (#,e1,1,e!,! ,e#,#, e" ,", e$

,!, e% ,$, eI ,1, e ,", eK ,%, e1H ,, e11 ,1H&

'ilih sisi e1! = 1HK. >ulis jejak J1! = (#,e1,1,e!,! ,e#,#, e" ,", e$

,!, e% ,$, eI ,1, e ,", eK ,%, e1H ,, e11 ,1H, e1! ,K&




'ilih sisi e1# = KI. >ulis jejak J1# = (#,e1,1,e!,! ,e#,#, e" ,", e$

,!, e% ,$, eI ,1, e ,", eK ,%, e1H ,, e11 ,1H, e1! ,K, e1# ,I&

'ilih sisi e1" = I1H. >ulis jejak J1" = (#,e1,1,e!,! ,e#,#, e" ,", e$

,!, e% ,$, eI ,1, e ,", eK ,%, e1H ,, e11 ,1H, e1! ,K, e1# ,I, e1" ,1H&

'ilih sisi e1$ = 1H%. >ulis jejak J1$ = (#,e1,1,e!,! ,e#,#, e" ,", e$

,!, e% ,$, eI ,1, e ,", eK ,%, e1H ,, e11 ,1H, e1! ,K, e1# ,I, e1" ,1H,

e1$ ,%&

'ilih sisi e1% = %I. >ulis jejak J1% = (#,e1,1,e!,! ,e#,#, e" ,", e$


e1$ ,%, e1% ,I&

'ilih sisi e1I = I$. >ulis jejak J1I = (#,e1,1,e!,! ,e#,#, e" ,", e$


e1$ ,%, e1% ,I, e1I ,$&

'ilih sisi e1 = $%. >ulis jejak J1 = (#,e1,1,e!,! ,e#,#, e" ,", e$


e1$ ,%, e1% ,I, e1I ,$, e1, %&

S>E' # 4 6arena S>E' ! tidak dapat dilanjutkan lagi, maka S>C', dan

J1 = (#,e1,1,e!,! ,e#,#, e" ,", e$ ,!, e% ,$, eI ,1, e ,", eK ,%, e1H

,, e11 ,1H, e1! ,K, e1# ,I, e1" ,1H, e1$ ,%, e1% ,I, e1I ,$, e1, %&

adalah jejak-Euler-buka di graph G. Fabel sisi-sisi jejak-Euler-

buka J1 dapat dilihat pada gambar berikut.




Gambar ' : Sisi-sisi jejak-(v 3 v ! " Euler J1# di G secara berturut-turut

adalahe1, e

2, e

3, e

4, e

5,e

6, e

7, e

8,e

9, e

10, e

11, e

12, e

13, e

14, e

15

&. Permasalahan Tukang Pos

Seorang tukang pos mempunyai tugas rutin mendistribusikan surat

dalam suatu +ilayah tertentu. Setiap hari dia harus berkeliling menelusuri

semua jalan dalam daerah tersebut untuk mendistribusikan surat-surat

berangkat dari kantor pos dan kembali ke kantor pos. *ungkinkah pak pos

menelusuri setiap jalan tepat satu kali@ 6alau mungkin, bagaimanakah

caranya@ 6alau tidak, jalan-jalan manakah yang harus dile+ati lebih dari satu

kali agar total jarak yang dia tempuh minimum@

ntuk menja+ab permasalahn ini, jaringan jalan di +ilayah

pendistribusian dapat dimodelkan dengan sebuah graph-bobot. >itik graph

berkorespondensi dengan persimpangan jalan, dan sisi graph

berkorespondensi dengan jalan yang menghubungkan dua persimpangan.

obot sisi berkorespondensi dengan panjang jalan yang di+akili oleh sisi

tersebut. /alam hal ini, kantor pos juga dipresentasikan dengan sebuah titik

graph.

Jika graph model yang diperoleh berupa graph Euler, jelas tukang pos

dapat menelusuri semua jalan yang ada sedemikian hingga setiap jalan

dile+ati tepat satu kali, bera+al dan berakhir di kantor pos. 9aranya dengan

mengikuti cara menelusuri sirkit Euler pada graph model. Lang menjadi




persoalan adalah jika graph model yang diperoleh bukan graph Euler.

/engan kata lain, graph model memuat titik berderajat ganjil dan titik

berderajat ganjil cukup banyak. erikut diberikan ilustrasi bila graph model

memiliki tepat dua titik berderajat ganjil. ngat, banyaknya titik berderajat

ganjil dalam sebuah graph selalu bernilai genap.

*isalkan graph model G yang diperoleh terhubung dan memiliki tepat

dua titik berderajat ganjil. *isalkan titik-titik yang berderajat ganjil tersebut

u dan . /engan algoritma /jikstra, dapat dicari sebuah lintasan terpendek '

yang menghubungkan titik u dan dan titik di graph G. entuk graph GM dari

G dengan menduplikat semua sisi G sepanjang lintasan '. Jelas graph GM

yang diperoleh berupa graph Euler, karena setiap titiknya berderajat genap./engan menelusuri sirkit Euler di GM bera+al dan berakhir di titik yang

berkorespondensi dengan kantor pos, dengan catatan, menelusuri duplikat

sisi berarti menelusuri jalan yang berkorespondensi dengan sisi yang

diduplikat, akan diperoleh jalan-tutup dengan panjang minimum. >otal

panjang jalan yang ditempuh sama dengan bobot graph G ditambah panjang

lintasan ' atau +(G& 0 +('&.

Gambar ( : Graph b$b$t G mereprese%tasika% jari%ga% jala%& 'itik v5 mereprese%tasika% ka%t$r p$s.

Sebagai contoh, perhatikan graph-bobot G pada gambar di atas

merepresentasikan suatu jaringan jalan di sekitas kantor pos tertentu.

*isalkan titik $ merepresentasikan kantor pos. dalam hal ini tukang pos




tidak mungkin menelusuri setiap jalan tepat satu kali bera+al dan berakhir di

kantor pos, karena graph G bukan graph Euler (perhatikan titik 1 dan titik 1H

berderajat ganjil&. ni berarti harus adal jalan-jalan yang harus ditelusuri lebih

dari satu kali. ntuk menentukan jalan-jalan yang harus ditelusuri lebih dari

satu kali agar total jarak yang ditempuh minimum, kita cari lintasan

terpendek yang menghubungkan titik 1 dan titik 1H. /engan menggunakan

algoritma /jikstra, diperoleh lintasan terpendek dari titik 1 ke titik 1H adalah

' = (1,",$,%,I,,1H&, seperti tampak pada gambar berikut (digambar

tebal atau ber+arna merah&.

Gambar ) : i%tasa% )(v 1 v 1* " terpe%dek di G adalah + ,

(v 1 v v 5 v ! v # v v 1* "

Selanjutnya, dibentuk graph GM dari graph G dengan menduplikat sisi-

sisi G sepanjang lintasan '. Graph GM yang dimaksud dapat dilihat pada

gambar berikut.




Gambar * : Graph G/ dibe%tuk dari graph G

'erhatikan bah+a setiap titik GM berderajat genap, jadi GM graph Euler.

*enggunakan algoritma Aleury, untuk mengkonstruksi sirkit-Euler yang

bera+al dan berakhir di titik $ pada graph GM diperoleh sirkit-Euler S =

($,#,",1,!,#,1,",K,$,",$,%,!,I,%,,I,1H,,K,1H,,I,%,$&. ngat

sirkit S ini tidak ada di graph G. jika menelusuri suatu Nsisi-duplikatM di GM

adalah menelusuri Nsisi yang diduplikatM di G, maka diperoleh jalan-tutup J =

($,#,",1,!,#,1,",K,$,",$,%,!,I,%,,I,1H,,K,1H,,I,%,$& pada

graph G yang memuat semua sisi G dengan bobot minimum. Jalan tutup J

dapat dilihat pada gambar di ba+ah. 'erhatikan dalam menelusuri jalan J

pada graph G, setiap sisi G pada lintasan ' ditelusuri tepat satu kali.

*isalnya, sisi 1" pada lintasan ' dengan bobot #, dalam menelusuri jalan J,

ditelusuri dua kali yaitu4 urutan ketiga dari titik " ke titik 1 dan urutan

ketujuh dari 1 ke " sisi 1" dilabel dengan ##,I. 9ontoh yang lain, sisi 1H

pada lintasan ' dengan bobot 1, dalam menelusuri jalan J, ditelusuri dua kali

yaitu4 urutan ke-1K dari titik ke titik 1H dan urutan ke-!! dari titik 1H ke

titik sisi 1H dilabel dengan 11K,!!. Secara lengkap, strategi menelusuri

jalan J dapat dilihat pada gambar berikut.




Gambar + : Jala% tutup J bera0al da% berakhir di titik v5 memuat

semua sisi G de%ga% b$b$t mi%imum.

'anjang jalan J adalah +(G& 0 +('& = $H 0 K =$K. /engan demikian,

strategi yang dapat dipilih oleh tukang pos agar semua jalan dile+ati dantotal jarak yang ditempuh minimum adalah mengikuti penelusuran jalan J.


Pengertian Graph Euler Dan Semi Euler Lengkap

Documents