diskret vii graph

Topik7 Pengatar Graph

7-1

Graph merupakan suatu cabang ilmu matematika yang sudah lama dikenal. Namun demikian, penerapan real dari teori graph, khususnya dalam komputer baru ditemukan dikemudian hari. Dalam bidang komputer, teori graph memberikan landasan yang baik dalam teori komputasi, konsep jaringan, dan juga berbagai konsep optimisasi dikembangkan dari teori graph. Pada bahasan ini akan dijelaskan terminology graph, dengan harapan akan memberikan kemudahan untuk memahami berbagai perkuliahan lanjut yang menggunakan konsep graph dalam implementasinya.

7.1 Pengertian Graph

Graph diperkenalkan oleh Leonhard Euler (1707 – 1783), seorang Matematikawan yang berasal dari Swiss. Graph merupakan pasangan yang terdiri dari himpunan V, yaitu himpunan titik-titik (atau disebut juga node atau vertek) dan himpunan E, yaitu himpunan edge-edge yang menghubungkan antar dua vertek tersebut.

V={v1, v2, v3, …, vn}

E={e1, e2, e3, …, em}

Dalam hal ini himpunan V tidak boleh himpunan kosong, sedangkan himpunan E mungkin saja himpunan kosong. Suatu edge, ei, menghubungkan antar vertek vk dengan vl, maka ditulis sebagai :

Jika arah diperhatikan :

ei=(vk,vl), dan digambarkan sebagai :

Oleh karena itu (vk,vl) (vl,vk)

Jika arah tidak diperhatikan :

ei={vk,vl}, dan digambarkan sebagai :

Oleh karena itu {vk,vl}={vl,vk}

Definisi :

Graph G=(V,E) adalah pasangan dari himpunan vertek-vertek V dan himpunan edge-edge E

yang menghubungkan antar dua vertek, atau dapat dituliskan EVxV. Jika arah diperhatikan, disebut digraph,sedangkan jika arah tidak diperhatikan, disebut undigraph.

Contoh :

V={Jakarta, Bogor, Bandung, Cianjur, Tangerang, Cikampek}

E={{jakarta,bogor}, {jakarta,bandung}, {jakarta,tangerang}, {jakarta,cikampek}, {bogor,cianjur}, {cianjur,bandung}, {bogor,tangerang}, {cikampek,bandung}}.

vk

vl

vk

vl


7-2

Maka Graph G=(V,E) dapat digambarkan sebagai :

Berikut disajikan beberapa istilah dalam graph :

1. Incident : Jika edge ei={vk,vl}maka dikatakan edge ei incident dengan vertek vk dan vl.

2. Adjacent : Jika edge ei={vk,vl}maka dikatakan vertek vk dan vertek vl saling adjacent.

Jika ei=(vk,vl), maka vk adjacent ke vertek vl. Atau vertek vl adjacent dari vertek vk. Vertek vk sebagai source dan vertek vl disebut sebagai vertek terminal.

3. Isolated : Suatu vertek vk dikatakan sebagai vertek terisolasi (isolated vertek) jika vertek vk tidak adjacent dengan vertek lainnya.

4. Loop : Jika suatu edge e incident dari dan ke vertek yang sama, maka dikatakan edge tersebut sebagai loop. Graph yang tidak mempunyai loop dikatakan sebagai loop-free.

Sebagai ilustrasi perhatikan graph berikut :

- Edge e1 adalah incident dengan vertek a dan vertek b.

- vertek a dan vertek b saling adjacent

- vertek c adalah isolated vertek

- edge e2 adalah loop

tangerang

bandung

cianjur

bogor

cikampek

jakarta

a

c

d

b

e1

e1

e3 e1

e1

e2 e1


7-3

7.2 Pengertian Jalur

Walk atau jalur adalah suatu barisan bergantian antar vertek dengan edge yang dimulai dan diakhiri oleh vertek. Jika vertek awal dan vertek akhir sama, maka jalur tersebut disebut jalur tertutup. Sedangkan jika tidak sama maka disebut jalur terbuka. Panjang suatu jalur adalah banyaknya edge pada jalur tersebut. Sebagai ilustrasi perhatikan graph berikut :

1. Jalur : c, e4, f, e5, h, e5, f, e4, c, e2, d adalah jalur terbuka dengan panjang 5.

2. Jalur : c, e4, f, e5, h, e5, f, e4, c, e2, d, e8, a, e9, c adalah jalur tertutup dengan panjang 7.

Trail : Trail merupakan jalur dengan tidak ada edge yang diulang.

Circuit : Adalah trail yang tertutup

Path : Path adalah jalur dengan tidak ada vertek yang diulang.

Cycle : Adalah path yang tertutup.


1. Jalur : a, e9, c, e5, d, e8, f, e7, e, e6, c, e5, d, e10, b adalah bukan trail

2. Jalur : e, e11, g, e3, h, e14, i, e13, g, e2, a adalah trail

3. Jalur : e, e11, g, e3, h, e14, i, e13, g, e2, a, e9, c, e6, e adalah circuit

4. Jalur : e, e11, g, e3, h, e14, i, e13, g, e2, a adalah bukan path

5. Jalur : e, e7, f, e15, h, e14, i, e13, g, e2, a adalah path.

6. Jalur : e, e7, f, e15, h, e14, i, e13, g, e2, a, e9, c, e6, e adalah cycle.

g h

c

i

j

d

a b

f

e1

e1

e2

e1

e4

e1

e1

e3

e1

e7 e1

e1

e5

e1

e1

e6

e1

e1

e8

e1

e1

e9

e1

e1

e10 a

c d

e

g

b

f

h

i

e1

e8 e4 e6 e5

e7 e11

e9

e3

e14 e13

e2

e15

e10


7-4

Connected graph (graph terhubungkan) : Suatu graph dikatakan connected graph jika antar dua vertek sembarang di dalam graph tersebut dijamin ada path yang menghubungkannya. Jika tidak maka graph tersebut disebut disconnected (tidak terhubungkan). Banyaknya kelompok vertek yang tidak

terhubngkan disebut komponen graph, dan disimbolkan sebagai (G).

Multigraph : Suatu graph dikatakan multigraph jika ada setidaknya dua vertek di dalam graph tersebut sedemikian banyaknya edge yang incident lebih dari 1. Jika banyaknya edge maksimum yang incident ke pasangan dua vertek adalah n, maka dikatakan multiplicity dari graph tersebut adalah n. Dan graphnya disebut sebagai n-graph.

Sebagai ilustrasi perhatikan contoh berikut :

(i) Adalah connected graph dengan multiplicity 4, sehingga disebut 4-graph.

Setiap connected graph maka banyaknya komponen adalah 1, (G)=1.

(ii) Adalah contoh disconnected graph dengan multiplicitynya 2.

Banyaknya komponen graph ini adalah 4, (G)=4. Oleh karena itu termasuk dalam 4-graph

7.3 Subgraph Suatu Graph

Sebagai suatu himpunan suatu graph juga mempunyai subgraph.

Definisi :

Subgraph dari graph G=(V,E) adalah graph lain, yaitu G1=(V1,E1) yang memenuhi sifat :

a. V1 dan V1V serta

b. E1E


d

a

f

b

g

e

c

g h

c

i

j

d

a b

f


7-5

G=(V,E) adalah :

G1=(V1,E1) adalah G2=(V2,E2) adalah :

G3=(V3,E3) adalah G4=(V4,E4) adalah

Maka : G1 adalah subgraph dari G, ditulis G1G

G2 adalah bukan subgraph dari G, ditulis G2G

G3 adalah subgraph dari G, ditulis G3G

G4 adalah bukan subgraph dari G, dan ditulis G4G

Spanning Subgraph

spanning subgraph dari suatu graph G=(V,E) adalah G1=(V1,E1) dengan sifat :

a. G1 adalah subgraph dari G, serta

b. V1=V

Sebagai ilustrasi berikut disajikan beberapa spanning subgraph dari graph G=(V,E) di atas :

b

f

e

c d

a

b c d

a

b c d

a

b c

d

a

b

f

e

c

d

a

g


7-6

(i) (ii)

(iii) (iv)

Sedangkan contoh berikut adalah bukan spanning subgraph dari graph G tersebut :

subgraph dari G tetapi bukan spanning subgraph

(ii) bukan subgraph dan bukan spanning subgraph dari G

b

f

e

c d

a

b

f

e

c d

a

b

f

e

c d

a

b

f

e

c

a

b

f

e

c d

a

b

f

e

c d

a


7-7

7.4 Pengurangan Graph

Suatu graph dapat dikurangi dengan vertek atau dapat juga dikurangi dengan edge. Hasil operasi

tersebut didefinisikan sebagai berikut :

Pengurangan dengan vertek : Graph G=(V,E) dikurangi dengan himpunan beberapan vertek A,

ditulis G-A, adalah graph baru G1 yang merupakan graph G yang telah dihapuskan vertek-

vertek yang tercakup dalam A serta edge yang incident dengan vertek-vertek dalam A

tersebut. Sebagai ilustrasi perhatikan contoh berikut :

Pengurangan graph dengan edge : Graph G=(V,E) dikurangi dengan himpunan beberapan edge B,

ditulis G-B, adalah graph baru G1 yang merupakan graph G yang telah dihapuskan edge-

edge yang ada dalam B. Sebagai ilustrasi perhatikan contoh berikut :

b

f

e

c d

a

b

f

d

- {c,e,a} =

e1 e2

e3

e5 e6

e7

b

f

e

c d

a

e4 - {e2,e4,e7,e5} = b

f

e

c d

a


7-8

7.5 Complete Graph dan Komplemen Suatu Graph

Complete Graph : Jika V adalah himpunan vertek, maka yang dimaksud complete

graph (graph lengkap) dari vertek V adalah suatu graph

G=(V,E) dengan sifat :

“Dijamin ada tepat satu buah edge antar dua vertek

sembarang”

Jika |V|=n, maka complete graph terhadap himpunan vertek V ditulis sebagai Kn. Sebagai ilustrasi

perhatikan contoh-contoh berikut :

K1 adalah :

K2 adalah :

K3 adalah :

K4 adalah :

K1 adalah :

Komplemen suatu Graph : Komplemen suatu graph G=(V,E) dengan |V|=n adalah complete graph

Kn dengan sifat semua edge yang ada di G telah dihapus. Sebagai ilustrasi

perhatikan graph berikut :

a

b a

c

b a

c

b a

c

b

a

c

e d


7-9

G=(V,E) adalah :

Maka komplemennya adalah :

b

a

c

e d

b

b

a

c

e d

d


7-10

LATIHAN 7.1.

1. Perhatikan graph berikut :

a. Tentukan himpunan yang berisi seluruh vertek dalam

graph tersebut.

b. Tentukan himpunan yang berisi seluruh edge

c. Graph tersebut termasuk digraph atau undigraph ?

d. Adakah vertek yang terisolasi (isolated vertek) pada

graph tersebut?

e. Adakah loop dalam graph tersebut ?

Jika : {a,b}=e1, {a,c}=e2, {a,g}=e3, {b,d}=e4, {b,h}=e5, {c,d}=e6, {c,e}=e7,

{d,f}=e8, {e,g}=e9, {e,f}=e10, {f,h}=e11, {g,i}=e12, {g,h}=e13, dan

{h,i}=e14,

f. Tentukan panjang dari jalur : a, e1, b, e4, d, e8, f, e10, e, e9, g, e3, a

g. Apakah jalur pada soal (f) di atas adalah jalur tertutup atau jalur terbuka ?

h. Tuliskan 5 buah jalur dari a ke f

i. Apakah jalur : f, e11, h, e14, i, e12, g, e13, h, e15, b, e4, d adalah trail?

j. Apakah jalur : f, e11, h, e14, i, e12, g, e13, h, e15, b, e4, d, e8, f adalah circuit?

k. Apakah jalur : f, e11, h, e14, i, e12, g, e13, h, e15, b, e4, d adalah path?

l. Apakah jalur : f, e11, h, e14, i, e12, g, e13, h, e15, b, e4, d, e8, f adalah cycle?

m. Buatlah path terpanjang dari vertek a ke vertek I, dan berapa panjangnya !

n. Buatlah cycle terpanjang dari vertek a !

o. Apakah graph tersebut ‘connected’ atau ‘disconnected’ ?

p. Berapa banyaknya komponen dari graph tersebut ?

q. Berapa ‘multiplicity’ dari graph tersebut ?

r. Sebutkan semua cycle dari verteks a dengan panjang 6 !

s. Sebutkan semua cycle dari vertek a dengan panjang 9 !

t. Jarak antara dua vertek adalah panjang path minimum yang menghubungkan kedua vertek

tersebut. Tentukan jarak dari vertek a ke i !

a

c d

e

g

b

f

h

i


7-11

2. Perhatikan graph G=(V,E) berikut :

a. Mana saja dari yang berikut ini merupakan subgraph dari graph di atas :

(i) (ii) (iii)

b. Apakah graph berikut merupakan spanning subgraph dari graph di atas ?

c. Ada berapa komponen dari graph pada soal (b) di atas ?

d. Dari graph G di atas, tentukan : (i) G – {d, f, a} (ii) G – {e4, e8, e7}

e. Tentukan komplemen dari graph G di atas !

a

c

d

b a

c

d

b a

c

d

b

g h

c

i

j

d

a b

f

e1

e1

e2 e1

e4 e1

e1

e3 e1

e7 e1

e1

e5 e1

e1

e6 e1

e1

e8 e1

e1

e9 e1

e1

g h

c

i

j

d

a b

f


7-12

7.6 Derajad Suatu Vertek

Derajad vertek suatu undirected graph : derajad suatu vertek v dari suatu undirected graph adalah

banyaknya edge yang incident ke vertek tersebut, dan ditulis sebagai deg(v). Vertek

dengan derajad satu disebut pendant vertek.

Untuk setiap graph selalu berlaku :

Vv

Ev ||2)deg(


deg(a)=2

deg(b)=0

deg(c)=2

deg(d)=3

deg(e)=2

deg(f)=1

---------------------

Vv

v 10)deg(

Sedangkan |E| = 5. Oleh karena itu terlihat

bahwa :

Vv

Ev ||2)deg(

Dalam graph tersebut, f adalah pendant vertek.

Euler Circuit : Euler circuit adalah suatu circuit (tidak ada edge yang dilalui lebih dari seklai) yang

melalui seluruh edge. Jika jalur tersebut berupa jalur tertutup maka disebut euler trail.

Suatu undirected loop-free graph akan mempunyai euler circuit jika dan hanya jika derajad

setiap verteknya adalah genap. Oleh karena itu suatu undirected loop-free graph akan

mempunyai euler trail kalau tepat hanya ada vertek yang berderajad ganjil.


b c

a

f

e

d


7-13

Terlihat bahwa semua vertek berderajad genap, maka graph tersebut akan mempunyai euler

circuit. Salah satu euler circuitnya adalah :

a, e1, b, e3, f, e8, e, e7, d, e6, c, e5, b, e4, e9, f, e2, a

Contoh untuk euler trail perhatikan graph berikut :

Jalur : f, e2, a, e1, b, e5, c, e6, d, e7, e, e4, b, e3, f, e8, e adalah suatu trail.

Derajad vertek suatu directed graph : Ada dua jenis derajad suatu vertek dalam directed graph,

yaitu incoming degree, ditulis sebagai id(v) dan outgoing degree, ditulis sebagai od(v).

Incoming degree, id(v), adalah banyaknya edge yang incident ke vertek v. Sedangkan

outgoing degree, od(v), adalah banyaknya edge yang incident dari vertek v.

Suatu directed graph akan mempunyai euler circuit kalau dipenuhi :

Untuk setiap vertek berlaku : id(v)=od(v)

a

b

c

e

d

f

e6 e5

e7

e1 e4

e3

e2

e8

e9

a

b

c

e

d

f

e6 e5

e7

e1 e4

e3

e2

e8

e9


7-14


1. Graph G1=(V1,E1) :

Jalur : d, e4, a, e3, c, e7, b, e2, a, e1, a, e5, e, e6, d adalah suatu euler circuit.

2. Graph G2=(V2,E2) :

Graph ini tidak mempunyai euler circuit, sebab pada vertek c id(v)=2od(v)=0. Juga

pada vertek b, id(b)=0od(b)2.

7.7 Planar dan Graph Bipartite

Planar graph : Suatu graph dikatakan sebagai planar graph jika graph tersebut dapat digambarkan

dalam bidang dimensi dua dengan tidak ada edge-edge yang berpotongan kecuali

perpotongannya tepat di vertek.

Graph yang tidak memenuhi sifat di atas dikatakan sebagai non planar graph. Sebagai ilustrasi

perhatikan graph-graph berikut :

c

a

d e

b

e3 e4

e6

e5

e2

e7

e1

c

a

d e

b

e3 e4

e6

e5

e2

e7

e1


7-15

a. K5 adalah planar graph seperti dalam gambar berikut :

b. Kubus dapat digambarkan sebagai planar graph :

Graph Bipartite : Suatu graph G=(V,E) dikatakan bipartite jika V=V1V2 dengan V1V2= dan

setiap edge pada G akan berbentuk {a,b} dengan aV1 dan bV2.

Sebagai ilustrasi, marilah kita lihat apakah graph berikut merupakan bipartite :

1. G=(V,E) yang bipartite :

2. G=(V,E) yang bipartite :

a

c

d

e

b

a d

c b

h

g f

e

a

c

d

b

h e

f g

a

d

b

c

i

h

g

f

e

V1 V2

a

i

g

h b

c

k

j

l

f

d

e


7-16

3. G=(V,E) yang bukan bipartite :

7.8 Pewarnaan Graph

Pewarnaan Graph : merupakan pemberian warna pada vertek-vertek suatu graph sedemikian

sehingga vertek-vertek yang saling adjacent mempunyai warna yang berbeda.

Contoh :

Vertek a dan c harus mempunyai warna yang berlainan.

Vertek b dan c harus mempunyai warna yang berlainan.

Vertek d dan c harus mempunyai warna yang berlainan.

Vertek d dan e harus mempunyai warna yang berlainan.

Vertek a, b, dan d boleh mempunyai warna yang sama.

Chromatic Number dari graph G ((G)) : merupakan banyaknya warna paling sedikit yang

diperlukan agar supaya dapat dilakukan pewarnaan graph. Untuk graph di atas, maka nilai

chromatic number adalah 2. Sebab hanya perlu dua jenis warna yang berbeda supaya dapat

dilakukan pewarnaan. Misalkan : vertek a, b, dan d diberi warna hitam, sedangkan vertek c dan e

diberi warna putih.

a

d

b

c

i

h

g

f

e

V1 V2

b

b

a

c

e d

d


7-17

Chromatic Polinomial : merupakan banyaknya pewarnaan yang dapat dibuat jika kita mempunyai

sejumlah warna tertentu. Jika banyaknya warna disimbolkan dengan , chromatic polynomial dari

graph G ditulis sebagai P(G,). Sebagai contoh adalah untuk graph di atas :

P(G,) = (-1)(-1)(-1)(-1) = (-1)4

Jika kita mempunyai warna sebanyak 6 jenis, maka banyaknya pewarnaan yang dapat dibuat adalah

sebanyak : 6 x 5 x 5 x 5 x 5 = 3750.

LATIHAN 8.2.


a. Tentukan derajad masing-masing verteks !

b. Apakah ada pendant vertek dalam graph tersebut ?

c. Tunjukan apakah berlaku : deg(v) = 2 |E| di dalam graph tersebut ?

d. Apakah ada Euler circuit di dalam graph tersebut. Jika ada tuliskan salah satunya.

a

j

d e

b

i

h

c

f g

k

b

b

a

c

e d

d

(-1)

(-1)

(-1)

(-1)


7-18


a. Tentukan incoming degree, id(v), dan outgoing degree, od(v), dari masing-masing graph tersebut !

b. Dengan memperhatikan jawaban nomor (a) di atas, apakah ada kemungkinan graph tersebut

mempunyai euler circuit. Kenapa ?

c. Sebutkan salah satu euler circuit dalam graph tersebut (kalau ada).

3. Dari planar graph berikut :

a. Tentukan banyaknya ‘region’ dari graph tersebut !

b. Tentukan derajad dari masing-masing daerah tersebut !

c. Tentukan dual dari graph tersebut !

d. Jika loop yang ada dihapuskan, apakah graph tersebut adalah Bipartite ?

4. Mana dari graph berikut yang mempunyai hamilton cycle ?

a

d

b

h

g

c

f e

i j k

d

a

f

b

g

e

c

a

d

c b

g i

f e

h

k

j

c d e

f

b

a

g

i

h

a


7-19

5. Tentukan :

i. chromatic number

ii. chromatic polinomial

iii. Banyaknya pewarnaan jika kita mempunayi 5 warna yang berbeda

dari graph berikut.

a. b.

c. d.

a

g

f

h

e

c

d

b

b

a

c d e

f

a

b

c

e

d

f

a

b

f e g

d c

diskret vii graph

Education