Masalah Graph

Masalah GRAPH

DASAR-DASAR TEORI GRAPH

Graph adalah kumpulan dari titik ( node ) dan garis dimana pasangan-pasangan titik ( node ) tersebut dihubungkan oleh segmen garis. Node ini biasa disebut simpul (verteks) dan segmen garis disebut ruas (edge).

Simpul dan ruas dalam graph dapat diperluas dengan penambahan informasi. Sebagai contoh, simpul bisa diberi nomor atau label dan ruas dapat diberi nilai juga. Perluasan dengan pemberian informasi ini sangat berguna dalam penggunaan graph untuk banyak aplikasi komputer. Contoh, graph dengan simpul yang merepresentasikan kota dan ruas merepresentasikan jarak yang ditempuh diantara kota-kota tsb. (atau harga tiket pesawat antara kota-kota tsb.) , dapat digunakan sebagai “transportation network” untuk mempelajari total jarak (atau harga) dari suatu perjalanan dengan banyak kota pemberhentian. Satu kemungkinan pertanyaan yang bisa muncul adalah “Jalur mana yang terpendek dengan satu atau lebih tempat pemberhentian, yang menghubungkan kota tertentu menuju kota tertentu lainnya dalam transportation network tersebut ?”.

Dalam kehidupan sehari-hari maupun dalam bidang akademis banyak persoalan yang dimodelkan dengan graph. Graph dipakai untuk membantu pemecahan masalah. Dari model graph yang dibuat, suatu masalah dapat dipahami menjadi lebih mudah. Untuk kemudian diturunkan metode pemecahannya.

1.1. Kelahiran Teori Graph

Jembatan Konigsberg

Menurut catatan sejarah, masalah jembatan Konigsberg adalah masalah yang pertama kali menggunakan graph (th. 1736). Masalah Jembatan Konigsberg adalah : “ apakah mungkin melalui tujuh buah jembatan masing-masing tepat satu kali. Dan kembali lagi ke tempat semula ?” . Tak seorangpun yang dapat memecahkan masalah ini. Barulah Euler yang pertama kali menemukan jawabannya. Ia memodelkan masalah dengan memodelkannya ke dalam graph. Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakannya sebagai simpul (vertex) dan jembatan sebagai sisi. Graph dibuat oleh Euler diperlihatkan pada gambar dibawah atas.

Jawabannya adalah : Orang tidak mungkin berjalan melalui ketujuh jembatan masing-masing satu kali dan kembali ke tempat asal keberangkatan. Singkatnya, tidak terdapat siklus Euler pada Graph tersebut.

Graph yang memenuhi kondisi diatas tersebut kemudian dikenal dengan nama Graph Euler dan perjalanannya disebut perjalanan euler.
Perjalanan Euler adalah :
Perjalanan dari suatu simpul kembali ke simpul tersebut dengan melalui setiap ruas tepat satu kali.
Perjalanan Euler akan terjadi, jika :

– Graf terhubung.
– Banyaknya ruas yang datang pada setiap simpul adalah genap

1.2. Graph secara Formal
Definisi Graf Graf G (V, E), adalah koleksi atau pasangan dua himpunan
(1) Himpunan V yang elemennya disebut simpul atau titik, atau vertex, atau point, atau node.
(2) Himpunan E yang merupakan pasangan tak terurut dari simpul, disebut ruas atau rusuk, atau sisi, atau edge, atau line.
Banyaknya simpul (anggota V) disebut order Graph G, sedangkan banyaknya ruas (anggota E) disebut ukuran (size) Graph G
_e4
_e31       _e1 2            _e2 3         _e5 4                                 9
_{e10          e11
e12
e13}
_{e6
e7
e8
e9}8
_e14
5                                                6                7                  _e16
_e1510

Graph G

Pada Gbr 2, G (V,E) adalah graph dengan

V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

E = {e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12, e13, e14, e15, e16 }

Ruas

e1 = (1,2)

e2 = (2,3)

e3 = (1,1)

e4 = (2,4)

e5 = (3,4)

e6 = (1,5)

e7 = (1,6)

e8 = (2,6)

e9 = (2,7)

e10 = (3,8)

e11 = (4,8)

e12 = (4,7)

e13 = (4,7)

e14 = (7,8)

e15 = (5,6)

e16 = (7,10)

Pada Graph G , Order = 10 dan Ukuran = 16

Pada Graph G , ruas e12 = (4,7) dan ruas e13 = (4,7) dinamakan ruas berganda atau ruas sejajar (multiple edges atau paralel edges), karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 4 dan simpul 7.

Pada Graph G , ruas e3 = (1,1) dinamakan gelung atau self-loop karena ia berawal dan berakhir pada simpul yang sama.

Derajat (Degree) suatu simpul d(v) adalah banyaknya ruas yang menghubungi simpul tersebut.

Sedangkan Derajat Graph G adalah jumlah derajat semua simpul pada Graph G.

Pada, derajat simpul

d(1) = 5

d(2) = 5

d(3) = 3

d(4) = 5

d(5) = 2

d(6) = 3

d(7) = 5

d(8) = 3

d(9) = 0

d(10) = 1 +

= 30

Maka derajat Graph G adalah 32 dan jumlah derajat semua simpul Graph (derajat Graph) = dua kali banyaknya ruas Graph (size/ukuran Graph).

Simpul 9 dikatakan simpul terpencil / simpul terisolasi, karena d(9) = 0 dan simpul 10 dikatakan simpul bergantung / simpul akhir karena d(10) = 1

1.3. Jenis Graph

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graph, maka graph digolongkan menjadi dua jenis:

1. Graph sederhana (simple graph).

Graph yang tidak mengandung gelung maupun sisi-ganda dinamakan graph sederhana.

2. Graph tak-sederhana (unsimple-graph/multigraph).

Graph yang mengandung ruas ganda atau gelung dinamakan graph tak-sederhana (unsimple graph atau multigrapf).

Berdasarkan jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis:

1. Graph berhingga (limited graph)

Graph berhingga adalah graph yang jumlah simpulnya, n, berhingga.

2. Graph tak-berhingga (unlimited graph)

Graph yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graph tak-berhingga.

Berdasarkan orientasi arah pada sisi, maka secara umum graph dibedakan atas 2 jenis:

1. Graph tak-berarah (undirected graph)

Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak-berarah.

2. Graph berarah (directed graph atau digraph)

Graph yang setiap sisinya diberikan orientasi arah disebut sebagai graph berarah.

_e4

_e31 _e1 2 _e2 3 _e5 4

_{e10
e11}

_{e6
e7
e8
e9}

5 6

_e15

Graph Berarah

1.4. Subgraph

Misalkan G = (V, E) adalah sebuah graph. G₁ = (V₁, E₁), jika V₁⊆ V dan E₁⊆ E. maka G₁adalah subgraph (subgraph) dari G .

G = (V, E)

Dengan V = { A, B, C, D }

E = { e1, e2, e3, e4, e5 }

Dan

G₁ = (V₁, E₁)

Dengan V₁ = { A, B, D } ⊆ V

E₁ = { e1, e5 } ⊆ E

e25

G₁

e25

G₂

Komplemen dari subgraph G₁terhadap graph G adalah graph G₂= (V₂, E₂) sedemikian sehingga E₂= E – E₁dan V₂adalah himpunan simpul yang anggota-anggota E₂bersisian dengannya.

G = (V, E)

Dengan V = { A, B, C, D }

E = { e1, e2, e3, e4, e5 }

G₁ = (V₁, E₁) subgraph dari G

Dengan V₁ = { A, B, D } ⊆ V

E₁ = { e1, e5 } ⊆ E

G₂ = (V₁, E₁) subgraph dari G

Dengan V₂ = { B, C, D } ⊆ V

E₂ = { e2, e3, e4 } ⊆ E

Dan terlihat E₂= E – E₁

Subgraph yang Direntang (Spanning Subgraph) Apabila E‘ mengandung semua ruas di E yang kedua ujungnya di V‘ , maka G‘ adalah Spanning Subgraph dari G yang dibentuk oleh V‘ .

G₂ = (V₁, E₁) Spanning subgraph dari G

Dengan V₂ = { B, C, D } ⊆ V

E₂ = { e2, e3, e4 } ⊆ E

Anggota E₂ adalah semua ruas dari G yang menghubungkan simpul di V₂.

1.5. Keterhubungan Graph

e25

Dua buah simpul dikatakan bertetangga (Adjacent) bila keduanya terhubung langsung oleh sebuah ruas.

Pada graph G disamping,

simpul A bertetangga dengan simpul B dan D,

simpul A tidak bertetangga dengan simpul C

Bersisian (Incidency)

Untuk sembarang ruas e = (v_j, v_k) dikatakan :

e bersisian dengan simpul v_j, atau e bersisian dengan simpul v_k

Pada graph G

ruas e5 bersisian dengan simpul A dan simpul D, tetapi

ruas e5 tidak bersisian dengan simpul B

Simpul terpencil (Isolated Vertex) ialah simpul yang tidak mempunyai sisi yang bersisian dengannya atau simpul bererajat 0 (nol).

Graf Kosong (null graf atau empty graf) adalah graf yang himpunan sisinya merupakan himpunan kosong (N_n).

Graph N₄

1.6. Operasi Graph

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

1. Gabungan G1 ∪ G2 adalah graf dgn himpunan ruasnya E1 ∪ E2.

2. Irisan G1 ∩ G2 adalah graf dgn himpunan ruasnya E1 ∩ E2.

3. Selisih G1 – G2 adalah graf dgn himpunan ruasnya E1 – E2.

4. Selisih G2 – G1 adalah graf dgn himpunan ruasnya E2 – E1.

5. Penjumlahan ring G1 ⊕ G2 adalah graf dgn himpunan ruasnya (E1 ∪ E2) – (E1 ∩ E2) atau (E1 – E2) ∪ (E2 – E1).

e25

G₁

G₂ – G₁

G₂

G₁ G₂

e25

G₁ – G₂

e25

G₁ G₂

e25

G₂

G₁

Graph K dan L merupakan dekomposisi Suatu graf G, bila K ∪ L = G dan K ∩ L = ∅

Contoh :

Penghapusan ( deletion ) dapat dilakukan pada simpul ataupun ruas.

1) Penghapusan Simpul .

Notasinya : G – {V}

Contoh :

2) Penghapusan Ruas .

Notasinya : G – {e}

Pemendekan/Shorting adalah menghapus simpul yang dihubungkan oleh 2 ruas (simpul berderajat 2), lalu menghubungkan titik-titik ujung yang lain dari kedua ruas tersebut.

Contoh :

1.7. Keterhubungan

Perjalanan atau walk pada suatu Graf G adalah barisan simpul dan ruas berganti-ganti

v₁, e_1,v₂, e_{2, …,}e_n-1,

dengan v_nsimpul

e_iruas menghubungkan v_idan v_i+1

dapat hanya ditulis barisan ruas atau barisan simpul saja.

e₁, e_{2, …,}e_n-1atau v₁, v₂, _…,v_n-1, v_n

Dalam hal ini, v₁disebut simpul awal, dan v_ndisebut simpul akhir.

Perjalanan disebut perjalanan tertutup bila v₁= v_n, sedangkan Perjalanan disebut perjalanan tebuka yang menghubungkan v₁dan v_n.Panjang Perjalanan adalah banyaknya ruas dalam barisan tersebut

Lintasan (Trail) Lintasan adalah Walk dengan semua ruas dalam barisan adalah berbeda.

Jalur adalah Walk yang semua simpul dalam barisan adalah berbeda.

Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus. Panjang sirkuit adalah jumlah ruas dalam sirkuit tersebut.

Graf yang tidak mengandung sirkuit disebut acyclic.

Contoh Pohon :

Suatu graf G disebut terhubung jika untuk setiap simpul dari graf terdapat jalur yang menghubungkan kedua simpul tersebut.

Subgraf terhubung suatu graf disebut komponen dari G bila subgraf tersebut tidak terkandung dalam subgraf terhubung lain yang lebih besar.

Contoh :

Rank (G) = n – K

Nullity (G) = e – (n – k)

Dimana : n : Order graf G

e : Size graf G

K : banyaknya komponen graf G

Jarak antara 2 simpul dalam graf G adalah panjang jalur terpendek antara ke 2 simpul tersebut.

Diameter suatu graf terhubung G adalah maksimum jarak antara simpul G.

Jarak maksimum dalam graf G adalah 3 (yaitu antara A – G atau B – G ataupun C – G), jadi diameter = 3

Referensi :

1. https://proxymous.wordpress.com/2010/08/03/graph-dan-analisis-algoritma/

Referensi :

Share this