GRAF

Matematika Diskrit

Teori graf ditulis pertamakali pada tahun 1736 oleh seorang matematikawan Swiss yang bernama Leonard Euler. Yang digunakan untuk menyelesaikan masalah jembatan Königsberg (sekarang, bernama Kaliningrad). Berikut adalah ilustrasi masalah tersebut :

—        Definisi Graf

—        Graf merupakan struktur diskrit yang terdiri

—        simpul (vertices, vertex) dan

—        himpunan sisi (edges)

—        Notasi sebuah graf adalah G = (V, E), dimana :

—        V merupakan himpunan tak kosong dari simpul-simpul (vertices), misalkan V = { v₁ , v₂ , ... , v_n }

—        E merupakan himpunan sisi – sisi (edges) yang menghubungkan sepasang simpul, misalkan E = {e₁ , e₂ , ... , e_n }

—        Jika graf tersebut mempunyai himpunan sisi yang merupakan himpunan kosong, dinamakan null graph atau empty graph.

CONTOH  Jembatan Königsberg

Misalkan graf tersebut adalah G(V, E) dengan V = { A, B, C, D }

E = { (A, C), (A, C), (A, B), (A, B), (B, D), (A, D), (C, D)}

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

   Lintasan dan Sirkuit Euler

Lintasan Euler dalam suatu graf merupakan lintasan yang melalui masing-masing sisi didalam graf tersebut tepat satu kali. Jika lintasan tersebut kembali kesimpul awal, sehingga membentuk lintasan tertutup (sirkuit) maka lintasan ini dinamakan sirkuit Euler. Dengan demikian, sirkuit Euler merupakan sirkuit yang melewati masing-masing sisi tepat satu kali. Graf yang memuat sirkuit Euler dinamakan graf Euler (Eulerian graph), sedangkan graf yang memuat lintasan Euler dinamakan graf semi Euler (semi- Eulerian graph).

Contoh:

Graf G1 merupakan graf Euler. karena memiliki lintasan yang membentuk lintasan tertutup (sirkuit), yaitu : pr – rt – ts – sq – qt – tp.

—        Beberapa sifat tentang lintasan dan sirkuit Euler :

—        Suatu graf G merupakan graf Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpul pada graf tersebut berderajat genap.

—        Graf terhubung G merupakan graf semi Euler (memiliki lintasan Euler) jika dan hanya jika di dalam graf tersebut terdapat tepat dua simpul berderajat ganjil.

—        Suatu graf terhubung berarah G merupakan graf Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpul pada graf tersebut memiliki derajat masuk dan derajat keluar yang sama.

—        Suatu graf terhubung berarah G merupakan graf semi Euler (memiliki lintasan Eulr) jika dan hanya jika G terhubung setiap simpul pada graf tersebut memiliki derajat masuk dan derajat keluar yang sama, kecuali dua

simpul yaitu simpul petama (simpul awal lintasan) memiliki derajat keluar satu lebih besar dari pada derajat masuk dan simpul yang kedua (simpul akhir lintasan) memiliki derajat masuk satu lebih besar dari pada derajat keluar.

—        Lintasan Hamilton suatu graf merupakan lintasan yang melalui setiap simpul dalam graf tersebut tepat satu kali. Jika lintasan tersebut kembali kesimpul awal, sehingga membentuk lintasan tertutup (sirkuit) maka lintasan ini dinamakan sirkuit Hamilton.

—        Dengan demikian, sirkuit Hamilton merupakan sirkuit yang melewati masing- masing sisi tepat satu kali. Graf yang memuat sirkuit Hamilton dinamakan graf Hamilton (Hamiltonian graph), sedangkan graf yang memuat lintasan Hamilton dinamakan graf semi Hamilton (semi- Hamiltonian graph).

Bertetangga (Adjacent)

Dua buah simpul dikatakan bertetangga jika kedua simpul tersebut terhubung langsung oleh

suatu sisi.

Pada graf diatas : simpul P bertetangga dengan simpul Q dan S, tetapi simpul P tidak bertetangga dengan simpul R.

Bersisian (Incidency)

Suatu sisi e dikatakan bersisian dengan simpul v1 dan simpul v2 jika e menghubungkan kedua simpul tersebut, dengan kata lain e = (v1, v2).

Contoh : Perhatikan graf dari masalah jembatan Königsberg berikut ini :

maka e1 bersisian dengan simpul A dan simpul C , tetapi sisi tersebut tidak berisian dengan simpul B.

Graf sederhana (simple graph ) = Graf sederhana merupakan graf tak berarah yang tidak mengandung gelang maupun sisi-ganda.

Graf Ganda (multigraph) = Graf ganda merupakan graf tak berarah yang tidak mengandung gelang (loop).

Graf semu (Pseudo graph) = Graf semu merupakan graf yang mengandung gelang (loop).

Matriks Adjasensi X dari graf berarah :

—        Suatu kolom yang seluruh elemennya bernilai 0 menyatakan suatu sumber.

—        Suatu baris yang seluruh elemennya bernilai 0 menyatakan suatu muara.

            —        Jika seluruh elemen diagonal utamanya bernilai 0, maka menyatakan tidak terdapat                       loop dalam graf tersebut.Sebaliknya, suatu elemen yang tidak  bernilai 0 pada                               diagonal menyatakan suatu loop.

Matriks Adjasensi X dari graf tak berarah :

—        Jika pada graf ditambahkan suatu simpul yang tidak terhubung, maka pada matriks X akan ditambahkan pula baris dan kolom yang seluruh elemennya bernilai 0.

            —        Matriks X simetris. 

            —        Elemen yang tidak bernilai 0 pada diagonal utama menyatakan suatu loop

Dari representasi matriks Insidensi Z pada contoh di atas dapat dilihat bahwa :

Pada graf tak berarah :

—        Jumlah elemen tidak nol pada suatu baris menunjukkan derajat dari simpul.

—        Setiap kolom mempunyai tepat dua elemen yang tidak nol.

—        Suatu kolom yang hanya mempunyai satu elemen tidak nol menunjukkan suatu gelung.

Pada graf berarah :

•       Pada suatu baris yang semua elemen- elemen tidak nolnya adalah 1 menunjukkan bahwa barisan (simpul) merupakan suatu sumber.

        •       Suatu baris yang semua elemen-elemen tidak nolnya adalah -1 menunjukkan bahwa baris       (simpul) merupakan muara.

•       Jumlah elemen 1 pada suatu baris menunjukkan derajat keluar dari baris

(simpul). Jumlah elemen -1 pada suatu baris menunjukkan derajat masuk dari simpul.

•       Setiap kolom mempunyai satu elemen -1 dan satu elemen 1. Hal ini sebagai akibat bahwa setiap busur selalu mempunyai satu simpul awal dan satu simpul akhir.