Teori Graph

http://dc169.4shared.com/img/YUuNRtn0/preview.html


Graf

·       Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

·       Gambar di bawah ini sebuah graf yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah.

·       Sejarah Graf: masalah jembatan Königsberg (tahun 1736)

Gambar 1. Masalah Jembatan Königsberg

·       Graf yang merepresentasikan jembatan Königsberg:

                                       Simpul (vertex) à menyatakan daratan

          Sisi (edge)           à menyatakan jembatan

·       Bisakah melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula?

Definisi Graf

Graf G = (V, E), yang dalam hal ini:

     V  = himpunan tidak-kosong dari simpul-simpul (vertices)

= { v₁ , v₂ , ... , v_n }

     E = himpunan sisi  (edges) yang menghubungkan sepasang

    simpul

= {e₁ , e₂ , ... , e_n }

Gambar 2.  (a) graf sederhana, (b) graf ganda, dan (c) graf semu

                                               

Contoh 1. Pada Gambar 2, G₁ adalah graf dengan

V = { 1, 2, 3, 4 }

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

G₂ adalah graf dengan

V = { 1, 2, 3, 4  }

E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) }       = { e₁, e₂, e₃, e₄, e₅, e₆, e₇}

G₃ adalah graf dengan

V = { 1, 2, 3, 4  }

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

= { e₁, e₂, e₃, e₄, e₅, e₆, e₇, e₈}                                                                 

 ·       Pada G₂, sisi  e₃ = (1, 3) dan sisi e₄ = (1, 3) dinamakan sisi-ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.

 ·       Pada G₃, sisi e₈ = (3, 3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.

Jenis-Jenis Graf

 ·       Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis

1. Graf sederhana (simple graph).

     Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G₁ pada Gambar 2 adalah contoh graf sederhana

 2. Graf tak-sederhana (unsimple-graph).

    Graf yang mengandung sisi ganda atau gelang dinamakan  graf tak-sederhana (unsimple graph). G₂ dan G₃ pada Gambar 2 adalah contoh graf tak-sederhana

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

    1. Graf berhingga (limited graph)

        Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.

    2. Graf tak-berhingga (unlimited graph)

Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.

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

      1.  Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada 

Gambar 1 adalah graf tak-berarah.

    2.  Graf berarah (directed graph atau digraph)

    Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Dua buah graf pada 

Gambar 2 adalah graf berarah.

Tabel 1 Jenis-jenis graf [ROS99]

Contoh Terapan Graf

1. Rangkaian listrik.

2.  Isomer senyawa kimia karbon

                         metana (CH₄)                  etana (C₂H₆)                propana (C₃H₈)

3.  Transaksi konkuren pada basis data terpusat

    Transaksi T₀ menunggu  transaksi T₁  dan T₂ 

    Transaksi T₂ menunggu transaksi T₁ 

    Transaksi T₁  menunggu transaksi T₃ 

    Transaksi T₃ menunggu transaksi T₂ 

 4.  Pengujian program

          read(x);

   while x <> 9999 do

    begin          

      if x < 0 then

         writeln(‘Masukan tidak boleh negatif’)

      else

        x:=x+10;

           read(x);

    end;

   writeln (x);

Keterangan:   1 : read(x)                              5 : x := x + 10

                      2 : x <> 9999                                                6 : read(x)

                      3 : x < 0                                                        7 : writeln(x)

                      4 : writeln(‘Masukan tidak boleh negatif’);

5.  Terapan graf pada teori otomata [LIU85].

Mesin jaja (vending machine)

Keterangan:

       a : 0 sen dimasukkan

       b : 5 sen dimasukkan

       c : 10 sen dimasukkan

       d : 15 sen atau lebih dimasukkan

Terminologi Graf

Gambar 4. Graf yang digunakan untuk menjelaskan terminologi pada graf

1. Ketetanggaan (Adjacent)

Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.

Tinjau graf G₁ : simpul 1 bertetangga dengan simpul 2 dan 3,

     simpul 1 tidak bertetangga dengan simpul 4.

2. Bersisian (Incidency)

Untuk sembarang sisi e = (v_j, v_k) dikatakan

          e bersisian dengan simpul v_j , atau

          e bersisian dengan simpul v_k

Tinjau graf G₁: sisi (2, 3) bersisian dengan simpul 2 dan simpul 3,

    sisi (2, 4) bersisian dengan simpul 2 dan simpul 4,

 tetapi sisi (1, 2) tidak bersisian dengan simpul 4.

3. Simpul Terpencil (Isolated Vertex)

Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya.

Tinjau graf G₁: simpul 5 adalah simpul terpencil.

4. Graf  Kosong (null graph atau empty graph)

Graf yang himpunan sisinya merupakan himpunan kosong (N_n).

5. Derajat (Degree)

Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.

Notasi: d(v)

Tinjau graf G₁:

          d(1) = d(4) = 2

                   d(2) = d(3) = 3

Tinjau graf G₃: d(5) = 0    à simpul terpencil

       d(4) = 1    à simpul anting-anting (pendant vertex)

Tinjau graf G₂: d(1) = 3     à bersisian dengan sisi ganda        

       d(2) = 4     à bersisian dengan sisi gelang (loop)      

Pada graf berarah,

          d_in(v) = derajat-masuk (in-degree)

         = jumlah busur yang masuk ke simpul v

          d_out(v) = derajat-keluar (out-degree)

= jumlah busur yang keluar dari simpul v

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

   G₄                                              

Tinjau graf G₄

_din(1) = 1; d_out(1) = 1

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

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

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

Lemma Jabat Tangan.  Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali  jumlah sisi pada graf tersebut. 

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

          

                                              

 Tinjau graf G₁:  d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10

= 2 ´ jumlah  sisi = 2 ´ 5

G1

Tinjau graf G₂:  d(1) + d(2) + d(3) = 3 + 3 + 4 = 10

= 2 ´ jumlah sisi = 2 ´ 5

G2

Tinjau graf G₃:  d(1) + d(2) + d(3) + d(4) + d(5)

= 2 + 2 + 3 + 1 + 0 = 8

= 2 ´ jumlah sisi = 2 ´ 4

Contoh 2. Diketahui graf dengan lima buah simpul. Dapatkah kita menggambar graf tersebut jika derajat masing-masing simpul adalah:

          (a) 2, 3, 1, 1, 2

          (b) 2, 3, 3, 4, 4

Penyelesaian:     

(a) tidak dapat, karena jumlah derajat semua simpulnya ganjil

 (2 + 3 + 1 + 1 + 2 = 9).

(b) dapat, karena          jumlah derajat semua simpulnya genap

       (2 + 3 + 3 + 4 + 4 = 16).

6. Lintasan (Path)

Lintasan yang panjangnya n dari simpul awal v₀ ke simpul tujuan v_n di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v₀, e₁, v₁, e₂, v₂,... , v_{n –1}, e_n, v_n sedemikian sehingga e₁ = (v₀, v₁), e₂ = (v₁, v₂), ... , e_n = (v_n-1, v_n) adalah sisi-sisi dari graf G.

Tinjau graf G₁: lintasan 1, 2, 4, 3 adalah lintasan dengan barisan sisi (1,2), (2,4), (4,3).

Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G₁ memiliki panjang 3.

7. Siklus (Cycle) atau Sirkuit (Circuit)

Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus.

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.

8. Terhubung (Connected)

Dua buah simpul v₁ dan simpul v₂ disebut terhubung jika terdapat lintasan dari v₁ ke v₂.

G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul v_i dan v_j dalam himpunan V terdapat lintasan dari v_i ke v_j.

Jika tidak, maka G disebut graf tak-terhubung (disconnected graph).

Contoh graf tak-terhubung:

Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari G diperoleh dengan menghilangkan arahnya).

Dua simpul, u dan v, pada graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u.

Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, maka u dan v dikatakan terhubung lemah (weakly coonected).

Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarang u dan v di G, terhubung kuat. Kalau tidak, G disebut graf terhubung lemah.

graf  berarah terhubung lemah                              graf berarah terhubung kuat

8. Upagraf (Subgraph) dan Komplemen Upagraf

Misalkan G = (V, E) adalah sebuah graf. G₁ = (V₁, E₁) adalah upagraf (subgraph) dari G jika V₁  Í V dan E₁ Í E.

Komplemen dari upagraf 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.

                           (a) Graf G₁                    (b) Sebuah upagraf       (c) komplemen dari upagraf (b)

Komponen graf (connected component) adalah jumlah maksimum upagraf terhubung dalam graf G.

	Graf G di atas ini mempunyai 4 buah komponen.  Pada graf berarah, komponen terhubung kuat (strongly connected component) adalah jumlah maksimum upagraf yang terhubung kuat.

Graf di bawah ini mempunyai 2 buah komponen terhubung kuat:

9. Upagraf Rentang (Spanning Subgraph)

Upagraf G₁ = (V₁, E₁) dari G = (V, E) dikatakan upagraf rentang jika V₁ =V (yaitu G₁ mengandung semua simpul dari G).

                           (a) graf G,         (b) upagraf rentang dari G,   (c) bukan upagraf rentang dari G

10. Cut-Set

Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.

 Pada graf di bawah, {(1,2), (1,5), (3,5), (3,4)} adalah cut-set. Terdapat banyak cut-set pada sebuah graf terhubung.

Himpunan {(1,2), (2,5)} juga adalah cut-set, {(1,3), (1,5), (1,2)} adalah cut-set, {(2,6)} juga cut-set,

 tetapi {(1,2), (2,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,2), (2,5)} adalah cut-set. 

11. Graf Berbobot (Weighted Graph)

Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).

Beberapa Graf Sederhana Khusus

a. Graf Lengkap (Complete Graph)

Graf lengkap ialah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Graf lengkap dengan n buah simpul dilambangkan dengan K_n. Jumlah sisi pada graf lengkap yang terdiri dari n buah simpul adalah n(n – 1)/2.

b. Graf Lingkaran

Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan C_n.

c. Graf Teratur (Regular Graphs)

Graf yang setiap simpulnya mempunyai derajat yang sama disebut graf teratur. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r. Jumlah sisi pada graf teratur adalah nr/2. 

d. Graf Bipartite (Bipartite Graph)

Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V₁ dan V₂,  sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V₁ ke sebuah simpul di V₂ disebut graf bipartit dan dinyatakan sebagai G(V₁, V₂).

Graf G di bawah ini adalah graf bipartit, karena simpul-simpunya dapat dibagi menjadi V₁ = {a, b, d} dan V₂ = {c, e, f, g}

             graf persoalan utilitas,                 topologi bintang

Representasi Graf

1. Matriks Ketetanggaan (adjacency matrix)

A = [a_ij],

                                1, jika simpul i dan j bertetangga  

                     a_ij = {       

                                0, jika simpul i dan j tidak bertetangga   

                                     

Contoh:

Derajat tiap simpul i:

(a)  Untuk graf tak-berarah,

d(vi) =