graph euler umg

18
1. Jalan (Walk), Jejak (Trail), dan Lintasan (Path) a. Jalan (Walk) Misalkan G adalah suatu graph. Jalan di graph G adalah suatu barisan berhingga (tak kosong) w=v 0 e 1 v 1 e 2 v 2 ... e k v k yang suku-sukunya bergantian titik dan sisi sedemikian hingga v i-1 dan v i adalah titik-titik ujung sisi e i untuk . k i 1 D. GRAPH EULER DAN GRAPH HAMILTON Jalan w=v 0 e 1 v 1 e 2 v 2 ... e k v k dapat ditulis w=v 0 v 1 v 2 ... v k atau w=(v 0 ,v k ) dengan v 0 sebagai titik awal dan v k sebagai titik akhir. Sedangkan titik-titik v 1 , v 2 , v 3 , dan v k-1 disebut titik-titik internal dan k disebut panjang jalan w. Panjang suatu jalan menyatakan banyak sisi pada jalan itu. Jalan tertutup adalah jalan yang titik awal dan titik akhirnya sama. Contoh 1: Perhatikan graph di bawah ini ! a b c d e f abdcbce adalah jalan yang panjangnya 6. badfdcdb adalah jalan tertutup yang panjangnya 7.

Upload: san-ha-san

Post on 31-Jan-2016

282 views

Category:

Documents


0 download

DESCRIPTION

Teori Graph

TRANSCRIPT

Page 1: Graph Euler UMG

1. Jalan (Walk), Jejak (Trail), dan Lintasan (Path)

a. Jalan (Walk)

Misalkan G adalah suatu graph. Jalan di graph G adalah suatu barisan berhingga (tak kosong) w=v0e1v1e2v2 ... ekvk yang suku-sukunya bergantian titik dan sisi sedemikian hingga vi-1 dan vi adalah titik-titik ujung sisi ei untuk . ki 1

D. GRAPH EULER DAN GRAPH HAMILTON

Jalan w=v0e1v1e2v2 ... ekvk dapat ditulis w=v0v1v2 ... vk atau w=(v0,vk) dengan v0 sebagai titik awal dan vk sebagai titik akhir. Sedangkan titik-titik v1, v2, v3, dan vk-1 disebut titik-titik internal dan k disebut panjang jalan w. Panjang suatu jalan menyatakan banyak sisi pada jalan itu. Jalan tertutup adalah jalan yang titik awal dan titik akhirnya sama.

Contoh 1:

Perhatikan graph di bawah ini ! a b c

d ef

abdcbce adalah jalan yang panjangnya 6.

badfdcdb adalah jalan tertutup yang panjangnya 7.

Page 2: Graph Euler UMG

b. Jejak (Trail)

Misalkan G adalah suatu graph dan w adalah sebuah jalan di graph G. Jika semua sisi pada jalan w berbeda maka w disebut jejak (trail). Jejak tertutup disebut sirkit.

Contoh 2:

Perhatikan graph di bawah ini ! b c

d ef

afdabdce adalah trail yang panjangnya 7.

afdbcda adalah sirkit yang panjangnya 6.

a

b. Lintasan (Path)

Misalkan G adalah suatu graph dan w adalah sebuah jalan di graph G. Jika semua sisi dan semua titik pada jalan w berbeda maka w disebut lintasan (path). Lintasan tertutup disebut siklis (cycle).

Page 3: Graph Euler UMG

Contoh 3:

Perhatikan graph di bawah ini ! b c

d ef

afdbce adalah path yang panjangnya 5.

afdcba adalah cycle yang panjangnya 5.

a

2. Jejak Euler, Sirkit Euler dan Graph Euler

Misalkan G adalah suatu graph. Jejak di graph G yang memuat semua sisi graph G disebut jejak Euler. Sirkit di graph G yang memuat semua sisi graph G disebut sirkit Euler. Suatu graph yang memuat sirkit Euler disebut graph Euler.

3. Lintasan Hamilton, Cycle Hamilton dan Graph Hamilton

Misalkan G adalah suatu graph. Lintasan di graph G yang memuat semua titik graph G disebut lintasan Hamilton. Cycle di graph G yang memuat semua titik graph G disebut cycle Hamilton. Suatu graph yang memuat cycle Hamilton disebut graph Hamilton.

Page 4: Graph Euler UMG

Contoh 4:

Perhatikan graph-graph di bawah ini !

a

b c

de p

q

r s t

Graph G

u

vwGraph H

2 3

41Graph P

Graph G hanya memuat jejak Euler tetapi tidak memuat sirkit Euler sehingga graph G bukan merupakan graph Euler.

Graph H memuat sirkit Euler sehingga graph H merupakan graph Euler.

Graph P dan Q tidak memuat jejak Euler maupun sirkit Euler sehingga graph P dan Q bukan merupakan graph Euler.

Graph G, H, dan P memuat cycle Hamilton sehingga graph G, H, dan P merupakan graph Hamilton.

Graph Q hanya memuat lintasan Hamilton tetapi tidak memuat cycle Hamilton sehingga graph Q bukan merupakan graph Hamilton.

2 3

41Graph Q

5

Page 5: Graph Euler UMG

1. Graph Terhubung (Connected Graph)

Graph terhubung adalah suatu graph yang setiap dua titiknya terdapat lintasan yang menghubungkan kedua titik itu.

Graph tidak terhubung adalah suatu graph yang terdapat dua titik yang tidak terhubung oleh suatu lintasan.

Contoh 1:

Perhatikan graph-graph di bawah ini !

E. GRAPH TERHUBUNG, POHON DAN HUTAN

12

3

4 56

Graph G1

a

b c

d e

fg h

Graph G2

Graph G1 merupakan graph terhubung, sedangkan graph G2 merupakan graph tidak terhubung yang terdiri dari dua komponen

Page 6: Graph Euler UMG

2. Pohon (Tree) dan Hutan (Forest)

Graph terhubung yang tidak memuat cycle disebut pohon (tree), sedangkan Graph tidak terhubung yang setiap komponennya berupa pohon disebut hutan (forest).

Contoh 2:

Perhatikan graph-graph di bawah ini !

Graph G1 merupakan pohon sedangkan graph G2 bukan merupakan pohon.

Graph G1 Graph G2

Page 7: Graph Euler UMG

Contoh 3:

Perhatikan graph-graph di bawah ini !

Graph G1 merupakan hutan yang terdiri dari 2 komponen sedangkan graph G2 merupakan hutan yang terdiri dari 3 komponen.

Graph G1 Graph G2

Page 8: Graph Euler UMG

1. Derajat Titik Graph

Misalkan v adalah sebuah titik di graph G. Derajat titik v yang dinotasikan dengan dG(v) atau d(v) adalah banyak sisi G yang terkait dengan titik v. Graph yang setiap titiknya berderajat sama disebut graph beraturan.

Contoh 1:

Perhatikan graph-graph di bawah ini !

F. DERAJAT TITIK DAN GRAPHIC

Pada graph G, d(p)=3, d(q)=3, d(r)=4, d(s)=5, d(t)=3, d(u)=0.

Graph H disebut graph beraturan-4 karena derajat setiap titiknya sama yaitu 4. Graph komplit merupakan graph beraturan

p q r

s tu Graph G Graph H

a

b

c

d e

Page 9: Graph Euler UMG

2. Derajat Graph

Misalkan G adalah suatu graph. Derajat minimum graph G dinotasikan dengan dan didefinisikan sebagai :

Derajat maksimum graph G dinotasikan dengan dan didefinisikan sebagai :

Contoh 2:

Perhatikan graph-graph di bawah ini !

Derajat minimum graph G adalah 0 dan derajat maksimum graph G adalah 5, sedangkan derajat minimum graph H adalah 4 dan derajat maksimum graph H adalah 4 atau dapat dikatakan bahwa derajat graph H adalah 4.

)(G )()()( GVvvdMinimumG

)(G

)()()( GVvvdMaksimumG

p q r

s tu Graph G Graph H

a

b

c

d e

Page 10: Graph Euler UMG

3. Derajat Titik Digraph

Misalkan v adalah sebuah titik di digraph G. Derajat masuk (in-degree) titik v yang dinotasikan dengan din(v) adalah banyak sisi digraph G yang masuk ke titik v. Derajat keluar (out-degree) titik v yang dinotasikan dengan dout(v) adalah banyak sisi digraph G yang keluar dari titik v.

Contoh 3:

Perhatikan digraph-digraph di bawah ini !

v1

v2 v3

v4

v5

Pada digraph G di atas, din(v1)=0, dout(v1)=2, din(v2)=1, dout(v2)=1, din(v3)=2, dout(v3)=2, din(v4)=3, dout(v4)=1, din(v5)=2, dan dout(v5)=2.Sedangkan pada digraph H , din(p)=1, dout(p)=2, din(q)=2, dout(q)=1, din(r)=2, dout(r)=2, din(s)=3, dout(s)=2, din(t)=1, dout(t)=2, din(u)=0, dout(u)=0.

p q r

s tu Digraph HDigraph G

Page 11: Graph Euler UMG

4. Hubungan antara Jumlah Derajat dan Banyak Sisi GraphPerhatikan graph-graph terhubung di bawah ini !

p q r

s tGraph G Graph P

a

b

c

d e Graph H

1 2 3 4

5 6 7

8 9

10 11

12

Berapakah banyak sisi pada masing-masing graph G, graph P, dan graph H?

Berapakah jumlah derajat titik-titik pada masing-masing graph G, graph P, dan graph H?

Dapatkah Anda menemukan hubungan antara banyak sisi pada suatu graph dan jumlah derajat titik-titiknya?

Teorema 3.1: (Lemma Jabat Tangan)

Pada setiap graph G berlaku , dengan adalah banyak sisi graph G.

)(

)(2)(GVv

GEvd )(GE

Page 12: Graph Euler UMG

5. Graphic

Barisan derajat dari graph G adalah barisan monoton turun dari derajat titik-titik G. Barisan derajat dari graph sederhana disebut graphic.

Contoh 4:

Perhatikan graph-graph di bawah ini !

Akibat Teorema 3.1 (Lemma Jabat Tangan) muncul pernyataan (Korolari) sebagai berikut:

Korolari 3.1.a

Banyak titik yang berderajat ganjil pada suatu graph adalah genap.

Dari graph G di samping dapat diperoleh barisan derajat :

5, 4, 3, 3, 3, 0 yang bukan merupakan graphic.

p q r

s tu Graph G

Page 13: Graph Euler UMG

a

b c

deGraph P

2 3

41Graph Q

5

Dari graph P dan Q di atas, berturut-turut dapat diperoleh barisan derajat :

4, 4, 3, 3, 2 dan 4, 3, 2, 2, 1 yang merupakan graphic.

Contoh 5:

Manakah dari barisan-barisan di bawah ini yang merupakan barisan derajat graph dan manakah yang merupakan graphic?

a. 5, 5, 4, 3, 2, 1, 0 b. 5, 4, 3, 3, 2, 2, 2

c. 5, 3, 3, 3, 3, 2, 1 d. 6, 5, 5, 4, 3, 2, 2, 1Jawab:

a. barisan derajat graph b. bukan barisan derajat graph

c. graphic d. barisan derajat graph

Page 14: Graph Euler UMG

6. Derajat Titik pada Graph EulerPerhatikan graph-graph terhubung di bawah ini !

a

b c

deGraph G1

t

p q

rsGraph G2

u

v

w

n m

lkGraph G3

Manakah diantara graph G1, G2, dan G3 yang memuat jejak Euler?

Manakah diantara graph G1, G2, dan G3 yang memuat sirkit Euler?

Manakah diantara graph G1, G2, dan G3 yang merupakan graph Euler?

Pada graph G1, ada berapa titik yang berderajat ganjil dan ada berapa titik yang berderajat genap?

Pada graph G2, ada berapa titik yang berderajat ganjil dan ada berapa titik yang berderajat genap?

Pada graph G3, ada berapa titik yang berderajat ganjil dan ada berapa titik yang berderajat genap?

Page 15: Graph Euler UMG

Tahukah Anda kaitan antara derajat titik pada suatu graph dan graph Euler ?

Kriteria apakah yang dapat digunakan untuk menentukan suatu graph itu merupakan graph Euler atau bukan graph Euler ?

Teorema 6.1: (Eulerian Graph)

Teo 6.1.a. Suatu graph dikatakan memiliki jejak Euler jika dan hanya jika graph itu terhubung dan tidak memiliki titik berderajat ganjil atau memiliki dua titik berderajat ganjil.

Teo 6.1.b. Suatu graph dikatakan memiliki sirkit Euler jika dan hanya jika graph itu terhubung dan tiap titiknya berderajat genap.

Teo 6.1.c. Suatu graph dikatakan graph Euler jika dan hanya jika graph itu terhubung dan tiap titiknya berderajat genap.

Page 16: Graph Euler UMG

Setelah kita pelajari tentang kriteria graph Euler, maka dapatkah Anda menjawab permasalahan jembatan Königsberg (Königsberg Bridge Problem) yang berada di sungai pregel yang membagi kota Königsberg menjadi empat wilayah daratan, yaitu:

“Rute manakah yang harus dipilih seseorang untuk dapat menyeberangi setiap jembatan hanya satu kali dari suatu wilayah daratan kembali ke wilayah daratan semula?”

A

B

C

D

Page 17: Graph Euler UMG

LATIHAN 41. Hitunglah derajat titik-titik pada graph G di bawah ini:

3. Dapatkah digambarkan graph sederhana 5 titik dengan derajat masing-masing titiknya adalah:a. 5, 2, 3, 2, 4 b. 4, 4, 3, 2, 3c. 3, 3, 2, 3, 2 d. 4, 4, 1, 3, 2Jika dapat, gambarkan salah satu contohnya, jika tidak dapat, berikan alasannya!

2. Hitunglah derajat masuk dan derajat keluar titik-titik pada digraph H di bawah ini:

a

b f

c

d eg

hij

1

3

4

2 7

8

695

10

Page 18: Graph Euler UMG

4. Perhatikan graph-graph di bawah ini:

a. Graph manakah yang memiliki jejak Euler? Sebutkan jejaknya! b. Graph manakah yang memiliki sirkit Euler? Sebutkan sirkitnya!

c. Graph manakah yang merupakan graph Euler? Berikan alasannya!5. Manakah dari barisan-barisan di bawah ini yang merupakan barisan derajat graph dan manakah yang merupakan graphic?a. 5, 2, 3, 2, 4 b. 4, 4, 3, 2, 3c. 3, 3, 2, 3, 2 d. 4, 4, 1, 3, 2

Graph G1Graph G2 Graph G3