TEORI 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.

• 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 titik-titik (vertices)

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

E = himpunan sisi (edges) yang menghubungkan sepasang simpul

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

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

G3 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₈}

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

• Pada G₂, sisi e₃ = (1, 3) dan sisi e₄ = (1, 3) dinamakan sisiganda (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 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 2 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 3 adalah graf berarah.

Contoh

Ada 7 kota (A,...,G) yang beberapa diantaranya dapat dihubungkan secara langsung dengan jalan darat. Hubungan-hubungan langsung yang dapat dilakukan adalah sebagai berikut:

A dengan B dan D

B dengan D

C dengan B E dengan F

Buatlah graf yang menunjukkan keadaan transportasi di 7 kota tersebut.

Penyelesaian :

Misalkan kota-kota dianggap sebagai titik-titik. Dua titik/kota dihubungkan dengan garis bila dan hanya bila ada jalan yang menghubungkan langsung kedua kota tersebut. Dengan demikian, keadaan transportasi di 7 kota dapat dinyatakan dalam gambar 3.

Gambar 3

Dalam graf tersebut e₁ berhubungan dengan titik A dan B (keduanya disebut titik ujung e₁). Titik A dan B dikatakan berhubungan, sedangkan titik A dan C tidak berhubungan karena tidak ada garis yang menghubungkannya secara langsung.

Titik G adalah titik terasing karena tidak ada garis yang berhubungan dengan G. dalam interpretasinya, kota G merupakan kota yang terasing karena tidak dapat dikunjungi dari kota-kota lain dengan jalan darat.

Contoh

Dalam graf G pada gambar 4, tentukan :

a. Himpunan titik-titik, himpunan garis-garis, titik-titik ujung masing-masing garis, dan garis paralel.

b. Loop dan titik terasing.

Penyelesaian :

Titik-titik ujung masing-masing garis adalah sebagai berikut :

Garis	Titik Ujung
e₁	{v₁,v₂}
e₂	{v₁,v₂}
e₃	{v₁,v₃}
e₄	{v₂,v₃}
e₅	{v₄,v₅}
e₆	{v₅}
e₇	{v₃}

B. Garis paralel adalah e1 dan e2 yang keduanya menghubungkan titik v1 dan v2. Loop adalah e6 dan e7, sedangkan titik terasing adalah titik v6.

Graf Bipartitie

Definisi 2

Graf Sederhana (Simple Graph) adalah graf yang tidak mempunyai loop ataupun garis paralel.

Definisi 3

Graf Lengkap (Complete Graph) dengan n titik (simbol K_n) adalah graf sederhana de n titik, di mana setiap 2 titik berbeda dihubungkan dengan suatu garis.

Definisi 4

Suatu graf G disebut Graf Bipartite apabila V(G) merupakan gabungan dari 2 himpunan tak kosong V₁ dan V₂, dan setiap garis dalam G menghubungkan suatu titik dalam V₁ dengan titik dalam V₂.

Apabila dalam Graf Bipartite, setiap titik dalam V₁ berhubungan dengan setiap titik dalam V₂, maka graf-nya disebut Graf Bipartite Lengkap.

Jika V₁ terdiri dari m titik dan V₂ terdiri dari n titik, maka Graf Bipartite Lengkapnya sering diberi simbol K_m,n.