Matematika Diskrit

Graf

A.    DEFENISI GRAF

Graf  G didefenisikan sebagai pasangan himpunan (V,E) ditulis dengan notasi G=(V,E) yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul (vertices atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul.

Berdasarkan defenisi di atas, graf yang terdiri dari satu titik dan tidak memiliki sebuah sisipun disebut graf trivial.

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 }

Dibawah ini beberapa contoh graf :

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

Contoh 1.

 G₁ adalah graf dengan himpunan simpul V dan himpunan sisi E dimana :

V = { 1, 2, 3, 4 }

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

Contoh 2.

G₂ adalah graf dengan himpunan simpul V dan himpunan sisi E dimana :

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₇}

Contoh 3.

G₃ adalah graf dengan himpunan simpul V dan himpunan sisi E dimana :

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.

B.  SEJARAH GRAF

Graf pertama kali ditemukan oleh seorang matematikawan Swiss yang bernama Leonard Euler pada tahun 1763 untuk memecahkan teka-teki jembatan Konigsberg di kota Konigsberg Jerman Timur terdapat sungai Pregal yang dibelah dua oleh pulau Kneiphof. Daratan yang dipisahkan oleh sungai tersebut dihubungkan oleh tujuh buah jembatan. Teka-tekinya adalah apakah mungkin melalui tujuh jembatan tersebut dan kembali ketempat semula dengan masing-masing jembatan dilalui tepat satu kali ?

Gambar 2. Jembatan  Konigsberg

        Sebelum Euler memodelkan masalah ini kedalam graf dan menentukan solusinya, kebanyakan orang sepakat bahwa tidak mungkin kembali ketempat semula, namun mereka tidak mampu menjelaskan mengapa.
     Euler memodelkan daratan dengan titik yang disebut sebagai simpul dan jembatan yang menghubungkannya sebagai garis yang disebut dengan sisi.

Jawaban Euler adalah orang tidak mungkin melalui jembatan tersebut masing-masing satu kali dan kembali ketempat semula jika digree dari simpul-simpul tidak semua genap atau dengan kata lain, jika masing-masing satu kali dapat kembali ketempat semula.

Gambar 3. Graf pemodelan jembatan Konigsberg

C.     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₁ 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₃ 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 di bawah ini 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 di bawah ini adalah graf berarah.

                                          (a) G₄                               (b) G₅

Gambar 4. (a) graf berarah, (b) graf-ganda berarah

Tabel 1. Jenis-jenis graf [ROS99]

Jenis	Sisi	Sisi ganda dibolehkan?	Sisi gelang dibolehkan?
Graf sederhana Graf ganda Graf semu Graf berarah Graf-ganda berarah	Tak-berarah Tak-berarah Tak-berarah Bearah Bearah	Tidak Ya Ya Tidak Ya	Tidak Tidak Ya Ya Ya