GRAPH

1. Pendahuluan

Graf biasanya dapat kita pakai untuk mempresentasikan sekumpulan objek-objek diskrit yang berada didalamnya dan hubungan antara objek-objek diskrit tersebut. Gambar berikut ini merupakan gambar sebuah graf yang menunjukkan peta jaringan jalan raya dan menghubungkan sejumlah kota di Provinsi Jawa Tengah.

 

2. Definisi Graf

Graf  G  dapat kita definisikan  sebagai pasangan dari himpunan (V,E), dan dapat kita tulis dengan notasi G = (V, E), yang dalam hal ini:

·         V  = himpunan yang tidak kosong dari simpul-simpul (vertices)  = { v₁ , v₂ , ... , v_n }

·         E = himpunan busur/sisi  (edges) yang menghubungkan   sepasang  simpul  = {e₁ , e₂ , ... , e_n }

Contoh

G₁ adalah graf dengan

V = { 1, 2, 3, 4 }         

Lalu E =  { (1, 2), (1, 3), (2,3), (2, 4), (3, 4) }

 

3. Jenis-Jenis Graf Dasar

Berdasarkan ada atau tidaknya sisi ganda ataupun gelang didalam suatu graf, maka graf tersebut dapat kita golongkan menjadi dua jenis:

·         Graf sederhana (simple graph)

Graf yang tidak mengandung  gelang maupun sisi-ganda

·         Graf tak-sederhana (unsimple-graph).

Graf yang mengandung gelang ataupun sisi ganda disebut graf tidak sederhana (unsimple graph)

contoh:

                     

4. Jenis-Jenis Graf berdasarkan orientasi arah

Berdasarkan orientasi arah pada sisi, maka secara umum sebuah graf  dapat kita bedakan berdasarkan 2 jenis:

·         Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah maka disebut graf tidak berarah.

·         Graf berarah (directed graph atau digraph)

Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah dan tidak mempunyai sisi ganda.

5 Terminologi Graf

A. Ketetanggaan (Adjacent)

Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.

Contoh 4

Tinjau graf G₁ :

·         simpul 1 bertetangga dengan simpul 2 dan 3

·         simpul 1 tidak bertetangga dengan  simpul 4.

 

B. Bersisian (Incidency)

Untuk sembarang sisi e = (v_j, v_k) dikatakan e bersisian dengan simpul v_j , atau e bersisian dengan simpul v_k

Contoh

Tinjau graf G₁:

·         sisi (2, 3) merupakan saling bersisian simpul 2  dengan simpul 3

·         sisi (1, 2) merupakan tidak saling bersisian dengan simpul 4.

C. Simpul Terpencil (Isolated Vertex)

Simpul terpencil adalah simpul yang tidak memiliki sisi yang bersisian dengan simpul itu sendiri.

Contoh

Tinjau graf G₃: simpul 5 adalah simpul terpencil karena tidak ada yang bersisian dengannya.

D. Graf  Kosong (empty graph)

Graf yang himpunan busurnya adalah himpunan kosong (N_n).

 

E. Derajat (Degree)

Derajat suatu simpul adalah jumlah sisi yang bersisian dengannya. Notasi yang digunakan : d(v)

Contoh

 Tinjau graf G₁:     

·         d(1) = d(4) = 2

·         d(2) = d(3) = 3

 

F. Derajat Graf Berarah

Pada sebuah graf berarah maka

·         d_in(v)       = derajat masuk yang merupakan jumlah busur yang mengarah masuk ke simpul v

·         d_out(v)      = derajat keluar yang merupakan jumlah busur yang mengarah keluar dari simpul v

·         d(v)         = d_in(v) + d_out(v)                                                                                    

Contoh

Tinjau graf G₄:

d_in(1) = 2;               d_out(1) = 1

d_in(2) = 2;               d_out(2) = 3

d_in(3) = 2;               d_out(3) = 1

d_in(4) = 1;               d_out(3) = 2

G. Lemma Jabat Tangan

Jumlah derajat dari semua simpu-simpul dalam suatu graf adalah genap, yaitu besarnya dua kalinya  jumlah busur dalam graf tersebut. 

Dengan kata lain, jika G = (V, E), maka:

 

Contoh

Tinjau graf G₁: 

d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10

Lintasan

Lintasan yang panjang n nya berasal dari simpul awal (v₀₎  lalu ke simpul tujuan (v_n) di dalam graf G adalah barisan yang diselang-selingi simpul-simpul dan sisi-sisi yang berbentuk v₀, e₁, v₁, e₂, v₂,... , v_{n –1}, e_n, v_n sedemikian sehingga merupakan sisi graf yaitu e₁ = (v₀, v₁), e₂ = (v₁, v₂), ... , e_n = (v_n-1, v_n)

Contoh

 

Tinjau graf G₁: lintasan 1, 2, 4, 3 merupakan lintasan dengan berisikan barisan sisi (1,2), (2,4), (4,3). Panjang lintasan adalah jumlah sisi-sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G₁ memiliki panjang 3.

Pada prinsipnya simpul dan sisi yang dilalui di dalam lintasan boleh berulang. Sebuah lintasan dapat kita nyatakan Lintasan Sederhana (simple path) apabila dari semua masing -masing simpulnya berbeda (setiap sisi dilalui hanya satu kali). Lintasan yang berawal dan berakhir pada simpul yang sama disebut lintasan Tertutup (close path). Lintasan yang tidak berawal dan berakhir pada simpul yang sama disebut lintasan terbuka (open path). Coba perhatikan pada G₁ lintasan:

·         1,2,4,3            : lintasan terbuka dan  lintasan sederhana

·         1,2,4,3,1        : lintasan tertutup dan lintasan sederhana

·         1,2,4,3,2        : lintasan terbuka tetapi bukan lintasan sedernana

H. Sirkuit

Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus. Coba kita tinjau graf G₁: 1, 2, 3, 1 adalah sebuah sirkuit.

Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G₁ memiliki panjang 3

SubGraf dan Komplemen

Misalkan G = (V, E) adalah sebuah graf. G₁ = (V₁, E₁) adalah SubGraf dari G jika V₁  Í V dan E₁ Í E. Komplemen dari SubGraf G₁ terhadap graf G adalah graf G₂ = (V₂, E₂) sedemikian sehingga E₂ = E - E₁ dan V₂ adalah himpunan simpul yang anggota-anggota E₂ bersisian dengannya.

Contoh

Perhatikan Graf G₁

 

  Graf G1          SubGraf G1      bukan Subgraf G1

I. SubGraf Rentang

SubGraf G₁ = (V₁, E₁) dari G = (V, E) dinyatakan SubGraf rentang jika V₁ =V (yaitu G₁ menmemiliki semua  simpul didalamnya dari G).

Graf              Subgraf Rentang    Bukan subgraf rentang

J. Cut-Set

Cut-set dari graf terhubung G yang merupakan himpunan sisi dan apabila himpunan sisi tersebut kita buang dari G maka  dapat menyebabkan G tidak terhubung dari graf tersebut. Jadi, cut-set selalu menghasilkan dua buah komponen. Terdapat banyak cut-set pada sebuah graf terhubung.

Contoh 15

Pada graf di bawah ini, {(1,2), (1,5), (3,5), (3,4)} merupakan cut-set. Himpunan {(1,2), (2,5)} juga adalah cut-set, {(1,3), (1,5), (1,2)} adalah cut-set, {(2,6)} juga cut-set, {(1,2), (2,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,2), (2,5)} adalah cut-set.

 

K. Graf Berbobot

Graf berbobot adalah graf yang setiap masing-masing sisinya diberi sebuah bobot

Contoh