Graf

Sejarah Graf

Menurut catatan sejarah, masalah jembatan Königsberg adalah masalah yang pertama kali menggunakan graf (tahun 1736). Di kota Königsberg (sebelah timur Prussia, Jerman sekarang), sekarang bernama kota Kaliningrad, terdapat sungai Pregal yang mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai.

(a)

Gambar (a) Jembatan Königsberg [ROS99]

Ada tujuh buah jembatan yang menghubungkan daratan yang dibelah oleh sungai tersebut (Gambar 8.2(a)). Masalah jembatan Königsberg adalah: apakah mungkin melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi ke tempat semula? Sebagian penduduk kota sepakat bahwa memang tidak mungkin melalui setiap jembatan itu hanya sekali dan kembali lagi ke tempat asal mula keberangkatan, tetapi mereka tidak dapat menjelaskan mengapa demikian jawabannya, kecuali dengan cara coba-coba.

Tahun 1736, seorang matematikawan Swiss, L.Euler, adalah orang pertama yang berhasil menemukan jawaban masalah itu dengan pembuktian yang sederhana. Ia memodelkan masalah ini ke dalam graf. Daratan (titiktitik yang dihubungkan oleh jembatan) dinyatakannya sebagai titik (noktah) –yang disebut simpul (vertex)- dan jembatan dinyatakan sebagai garis –yang disebut sisi (edge). Setiap titik diberi label huruf A, B, C, dan D. Graf yang dibuat oleh Euler. Jawaban yang dikemukakan oleh Euler adalah: orang tidak mungkin melalui ketujuh jembatan itu masingmasing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnyagenap. Yang dimaksud dengan derajat adalah banyaknya garis  yang bersisian dengan noktah. Sebagai contoh, simpul C memiliki derajat 3 karena ada tiga buah garis yang bersisian dengannya, simpul B dan D juga berderajat dua, sedangkan simpul A berderajat 5. Karena tidak semua simpul berderajat genap, maka tidak mungkin dilakukan perjalananan berupa sirkuit (yang dinamakan dengan sirkuit Euler) pada graf tersebut.

Jenis-jenis Graph

1.    Graph sederhana

Graph yang tidak mempunyai sisi rangkap dan tidak memiliki gelung disebut graph sederhana.

2.    Graph tidak sederhana

a. Graph rangkap

Sebuah graph yang memiliki sisi rangkap tetapi tidak memiliki gelung disebut graph rangkap (multi-graph).

b. Graph semu

Sebuah graph yang memilki sisi rangkap dan memiliki gelung disebut graph

semu (pseudograph).

3.    Graph komplit

Sebuah graph komplit (graph lengkap) dengan n titik, dilambangkan dengan Kn , adalah graph sederhana dengan n titik dan setiap dua titik berbeda dihubungkan dengan sebuah sisi. Sebuah graph lengkap sering juga disebut sebagai graph universal. Kerena tiap titik dalam grap lengkap selalu dihubungkan dengan titik lain melalui satu sisi, maka derajat tiap titik dalam sebuah graph lengkap G dengan n titik adalah n-1. Dengan demikian, banyaknya sisi dalam graph lengkap G adalah .

4.    Graph bagian (subgraph)

Sebuah graph H disebut graph bagian (subgraph) dari graph G

5.    Graph teratur

Sebuah graph disebut graph teratur jika semua titiknya berderajat sama. Misal graph teratur berderajat tiga.

6.    Graph lingkaran

Graph sederhana yang setiap titiknya berderajat dua disebut graph lingkaran. Graph lingkaran dengan n titik dilambangkan dengan Cn. Graph lingkaran ini disebut juga graph teratur berderajat dua.

7.    Graph kosong atau graph nol

Graph yang tidak memiliki sisi disebut graph kosong atau graph nol. Graph nol dengan n titik dilambangkan dengan Nn. Graph yang hanya mempunyai satu buah titik tanpa sebuah sisi dinamakan graph trivial. Misal graph kosong dengan tiga titik (N3).

8.    Graph bipartisi

Sebuah graph G disebut graph bipartisi jika V(G) (himpunan titik graph G) dapat dipartisi menjadi dua himpunan bagian X dan Y sedemikian sehingga setiap sisi dari G menghubungkan sebuah titik di X dan sebuah titik di Y.

Kita notasikan (X,Y) bipartisi dari G. Apabila G sederhana dan bipartisi dengan partisi (X,Y) sedemikian sehingga setiap titik di X berhubungan langsung dengan setiap titik di Y, maka G disebut graf bipartisi lengkap, dinotasikan dengan Km,n dengan m dan n adalah banyaknya titik dikedua partisi tersebut.

9.    Graph berbobot

Sebuah graph G disebut graph berbobot jika setiap sisinya diberi sebuah harga.

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

1.    Graf tak-berarah (undirected graf)

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

2.    Graf berarah (directed graf atau digraf)

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

Operasi-operasi pada graf :

1. Gabungan G₁ È G₂ adalah graf dengan himpunan V nya = V₁ È V₂ dan himpunan E nya = E₁ È E₂

2.  Irisan G₁ Ç G₂ adalah graf dengan himpunan V nya = V₁ Ç V₂ dan himpunan E nya = E₁ Ç E₂

3.  Selisih G₁ - G₂ adalah graf dengan himpunan V nya = V₁ dan himpunan E nya = E₁ - E₂

Sedangkan Selisih G₂ – G₁ adalah graf dengan himpunan V nya = V₂ dan himpunan E nya = E₂ – E₁

4.  Penjumlahan Ring G₁ Å G₂ adalah graf yang dihasilkan dari  

(G₁ È G₂) – (G₁ Ç G₂) atau (G₁ - G₂) È (G₂ - G₁)