graf : matematika diskrit

GRAF

Secara kasar, graf adalah suatu diagram yang memuat informasi tertentu jika diinterpretasikan secara tepat. Dalam kehidupan sehari-hari, graf digunakan untuk menggambarkan berbagai macam struktur yang ada. Tujuannya adalah sebagai visualisasi obyek-obyek agar lebih mudah dimengerti. Beberapa contoh graf yang sering dijumpai dalam kehidupan sehari-hari antara lain: struktur organisasi, bagan alir pengambilan mata kuliah, peta, rangkaian listrik, dan lain-lain. Graf struktur sebuah organisasi dan peta beberapa daerah tampak pada Gambar 1 dan Gambar 2.

                                                                                                                                                     

Tiap-tiap diagram memuat sekumpulan obyek (kotak, titik, dan lain-lain) beserta garis-garis yang menghubungkan obyek-obyek tersebut. Garis bisa berarah ataupun tidak berarah. Garis yang berarah biasanya digunakan untuk menyatakan hubungan yang mementingkan urutan antar objek-objek. Urut-urutan objek akan mempunyai arti yang lain jika arah garis diubah. Sebagai contoh adalah garis komando yang menghubungkan titik-titik struktur sebuah organisasi. Sebaliknya, garis yang tidak berarah digunakan untuk menyatakan hubungan antar objek-objek yang tidak mementingkan urutan. Sebagai contoh adalah garis untuk menyatakan jarak hubung 2 kota pada Gambar 2. Jarak dari kota A ke kota B sejauh 200 km akan sama dengan jarak dari kota B ke kota A. Apabila jarak 2 tempat tidak sama jika dibalik (misalnya karena harus melalui jalan memutar), maka garis yang digunakan haruslah garis yang berarah.

Dalam materi ini, graf akan dibahas secara teoretis, baik graf secara umum maupun Tree (pohon) yang merupakan kasus khusus graf yang banyak dipakai dalam ilmu komputer. Terminologi yang dipakai dalam teori graf tidak baku. Dalam buku yang berbeda, sebuah simbol mungkin menyatakan beberapa hal yang berbeda. Hal ini bisa dimaklumi mengingat luasnya aplikasi graf dalam berbagai bidang. Dalam materi ini, diusahakan agar definisi-definisi maupun simbol-simbol yang digunakan merupakan definisi-definisi dan simbol-simbol yang biasa dipakai.

Dasar-Dasar Graf

Definisi 1

Suatu graf G terdiri dari 2 himpunan yng berhingga, yaitu himpunan titik-titik tidak kosong (simbol V(G)) dan himpunan garis-garis (simbol E(G)).

Setiap garis berhubungan dengan satu atau dua titik. Titik-titik tersebut dinamakan Titik Ujung. Garis yang hanya berhubungan dengan satu titik ujung disebut Loop. Dua garis berbeda yang menghubungkan titik yang sama disebut Garis Paralel.

Dua titik dikatakan berhubungan (adjacent) jika ada garis yang menghubungkan keduanya. Titik yang tidak mempunyai garis yang berhubungan dengannya disebut Titik Terasing (Isolating Point)

Graf yang tidak mempunyai titik (sehingga tidak mempunyai garis) disebut Graf Kosong.

Jika semua garisnya berarah maka graf-nya disebut Graf Berarah (Directed Graph, atau sering disingkat Digraph). Jika semua garisnya tidak berarah, maka graf-nya disebut Graf Tak Berarah (Undirected Graph). Dalam materi ini, jika hanya disebutkan graf saja, maka yang dimaksud adalah graf tak berarah.

Kadang-kadang suatu graf dinyatakan dengan gambar. Gambar suatu graf G terdiri dari himpunan titik-tilik V(G), himpunan garis-garis E(G) yang menghubungkan titik-titik tersebut (beserta arah garis pada graf berarah), dan label pada garisnya (jika ada). Panjang garis, kelengkungan garis, dan letak titik tidak berpengaruh dalam suatu graf.

Contoh 1

Ada 7 kota (A,...,G) yang beberapa di antaranya 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.

                         

                                                                                                                                                  

Dalam graf tersebut e1 berhubungan dengan titik A dan B (keduanya disebut titik ujung e1). 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.

Dalam graf tak berarah, garis e dengan titik ujung (v,w) menyatakan suatu garis yang menghubungkan titik v dengan titik w. Dalam graf berarah, garis tersebut menyatakan garis dari titik v ke titik w.

Dengan diketahuinya graf, maka himpunan garis, titik serta titik-titik ujungnya adalah tunggal. Tetapi hal ini tidak berlaku sebaliknya. Dengan diketahuinya himpunan garis, titik dan titik-titik ujung garis, maka dapat dibentuk beberapa graf yang “berbeda”. Perbedaan graf-graf tersebut terletak pada panjang garis, kelengkungan garis, dan posisi titik yang berbeda antara satu graf dengan graf yang lainnya.

Tetapi karena visualisasi titik dan garis (panjang garis, kelengkungan posisi titik dan lain-lain) tidak berpengaruh, maka graf-graf tersebut merupakan graf yang sama meskipun secara visual tampak berbeda.

Contoh 2

Gambarlah graf G dengan titik dan garis berikut ini

V(G) = {v1, v2, v3, v4}

E(G) = {e1, e2, e3, e4, e5}

Titik-titik ujung garis adalah :

Garis    Titik Ujung

e1    {v1,v3}

e2    {v2,v4}

e3    {v1}

e4    {v2,v4}

e5    {v3}

Penyelesaian :

Ada banyak graf yang dapat dibentuk. Semua graf tersebut sebenarnya menggambarkan objek yang sama, tetapi tampak berbeda karena letak titik, panjang garis dan kelengkungannya berbeda. Dua di antara graf-graf tersebut tampak pada Gambar 4 dan 5

                                                                                                                                                    

Graf juga banyak dipakai untuk membantu menyelesaikan masalah-masalah yang berhubungan dengan Kecerdasan Buatan (Artificial Intelligence), seperti dalam contoh 3, yang merupakan suatu teka-teki yang banyak dipakai sebagai ilustrasi. Dalam hal ini, graf digunakan untuk menyatakan hubungan-hubungan yang terjadi di antara objek-objek. Dengan cara itu, deduksi ke kesimpulan akan lebih mudah dibuat.

Contoh 3

Ada sebuah pulau yang penghuninya hanya terdiri dari 2 macam yaitu : pemakan orang (cannibal) dan pemakan sayuran (vegetarian). Pada mulanya, ada 2 orang pemakan orang dan 2 orang pemakan sayuran di sisi barat sungai. Di sisi barat itu pula terdapat sebuah perahu kecil yang hanya dapat menampung paling banyak 2 orang. Masalahnya adalah bagaimana cara mengangkut keempat orang tersebut ke sisi timur sungai. Syaratnya adalah : jumlah pemakan manusia pada suatu sisi sungai tidak boleh lebih banyak dari jumlah pemakan sayuran di sisi yang sama, karena hal itu akan menyebabkan pemakan manusia akan memakan pemakan sayuran.

Penyelesaian:

Suatu cara penyelesaian yang sistematis adalah dengan menggambarkan semua kemungkinan keadaan, dan kemudian menghilangkan bagian-bagian yang tidak mungkin terjadi karena tidak memenuhi kendala yang diisyaratkan.

Misalkan simbol s menyatakan pemakan sayuran, o menyatakan pemakan orang, P menyatakan perahu dan simbol "/" menyatakan sungai. Dengan menggunakan simbol tersebut maka ssoP/o berarti suatu keadaan di mana di sisi barat sungai (di sebelah kiri simbol /) ada 2 orang pemakan sayuran dan satu orang pemakan orang, sedangkan di sisi timur sungai ada seorang pemakan orang. Perahu ada di sisi barat sungai.

Semua kemungkinan keadaan di sungai tersebut dapat digambarkan pada Gambar 6 (sumbu mendatar menyatakan jumlah pemakan sayur di timur sungai dan sumbu tegak menyatakan jumlah pemakan orang di timur sungai). Pada suatu titik tertentu, ada 2 kemungkinan posisi perahu (P), yaitu di kiri sungai atau di kanan sungai.

Selanjutnya, dihilangkan keadaan-keadaan yang tidak mungkin terjadi:

a.    Karena jumlah pemakan orang (o) di suatu sisi sungai tidak boleh lebih banyak dari jumlah pemakan sayurnya (s), maka titik-titik : s/Psoo, sP/soo, soo/Ps, sooP/s harus dihilangkan

b.    Perahu harus berada pada sisi sungai yang ada orangnya. Jika tidak demikian, maka tidak ada orang yang dapat menyeberang. Oleh karena itu, harus dihilangkan titik-titik   ssoo/P dan P/ssoo

Dengan adanya beberapa titik yang dihilangkan tersebut, maka didapatkan keadaan yang dinyatakan pada Gambar 7

                                                                                                                                                     

Dari titik-titik yang tersisa, dibuat garis-garisnya. Suatu garis menghubungkan 2 buah titik yang dapat dicapai satu dari yang lainnya. Sebagai contoh, titik ssoP/o dapat dihubungkan dengan titik o/Psso karena dari titik ssoP/o, perahu dapat mengangkut 2 orang pemakan sayur (s) ke sisi kanan sungai, sehingga didapatkan titik o/Psso. Kondisi ini juga berlaku sebaliknya. Dari titik o/Psso, perahu dapat mengangkut 2 orang pemakan sayur ke kiri sungai sehingga didapatkan titik ssoP/o. Dengan penambahan semua garis yang mungkin dibuat, maka didapatkan graf yang dinyatakan pada Gambar 8.

Untuk menyelesaikan masalah tersebut, berarti harus dicari jalur (garis) yang menghubungkan titik ssooP/ (perahu dan semua orang yang terlibat berada di barat sungai) dengan titik /Pssoo (perahu dan semua orang yang terlibat berada di timur sungai)

Dari Gambar 8 didapatkan 2 kemungkinan jalur yaitu :

ssooP/ ® ss/Poo ® ssoP/o ® o/Psso ® ooP/ss ® /Pssoo

atau:

ssooP/ ® so/Pso ® ssoP/o ® o/Psso ® ooP/ss ® /Pssoo

Graf Tak Berarah

Berdasarkan jenis garis-garisnya, graf dibedakan dalam 2 kategori yaitu Graf Tak Berarah (Undirected Graph) dan Graf Berarah (Directed Graph = Digraph).

    Graf Bipartite

Definisi 2

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

Contoh 4

Gambarlah semua graf sederhana yang dapat dibentuk dari 4 titik {a, b, c, d} dan 2 garis

Penyelesaian :

Sebuah garis dalam graf sederhana selalu berhubungan dengan 2 buah titik. Karena ada 4 titik, maka ada   garis yang mungkin dibuat, yaitu garis-garis yang titik-titik ujungnya adalah {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, dan {c,d}.

Dari keenam garis yang mungkin tersebut, selanjutnya dipilih  2 di antaranya. Jadi ada ( 6  2 ) = 6! / 2! 4! = 15 buah graf yang mungkin dibentuk. Graf-graf tersebut dapat dilihat pada Gambar 9.

Definisi 3

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

Teorema 1

Banyaknya garis dalam suatu graf lengkap dengan n titik adalah n(n-1) / 2  buah

Bukti

Misalkan G adalah suatu graf lengkap dengan n titik v1, v2,..., vn.

Ambil sembarang titik (sebutlah v1). Karena G merupakan graf lengkap, maka v1 dihubungkan dengan (n-1) titik lainnya (v2, v3, ... , vn). Jadi ada (n-1) buah garis.

Selanjutnya, ambil sembarang titik kedua (sebutlah v2). Karena G adalah graf lengkap, maka v2 juga dihubungkan dengan semua titik sisanya (v1, v3, ..., vn), sehingga ada (n-1) buah garis yang berhubungan dengan v2. Salah satu garis tersebut menghubungkan v2 dengan v1. Garis ini sudah diperhitungkan pada waktu menghitung banyaknya garis yang berhubungan dengan v1. Jadi, ada (n-2) garis yang belum diperhitungkan.

Proses dilanjutkan dengan menghitung banyaknya garis yang berhubungan dengan v3, v4, ..., vn-1 dan yang belum diperhitungkan sebelumnya. Banyak garis yang didapat berturut-turut adalah : (n-3), (n-4), ...,3,2,1.

Jadi secara keseluruhan terdapat (n-1) + (n-2) + (n-3) + ... + 2 + 1 =  n(n-1) / 2 buah garis.

Contoh 5

Gambarlah K2, K3, K4, K5, dan K6 !

Penyelesaian :

                                                                                                                                                

Kadang-kadang, titik-titik dalam suatu graf dapat dipecah menjadi 2 bagian, di mana titik-titik dalam satu bagian dihubungkan dengan titik-titik di bagian yang lain. Dengan demikian, graf terlihat seolah-olah "terpisah" menjadi 2 bagian.

Definisi 4

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

Apabila dalam Graf Bipartite, setiap titik dalam V1 berhubungan dengan setiap titik dalam V2, maka graf-nya disebut Graf Bipartite Lengkap.

Jika V1 terdiri dari m titik dan V2 terdiri dari n titik, maka Graf Bipartite Lengkapnya sering diberi simbol Km,n.

Contoh 6

Tentukan mana di antara graf-graf berikut ini yang merupakan graf Bipartite dan Bipartite lengkap.

Penyelesaian :

a.    Jelas bahwa titik-titik graf-nya terbagi menjadi 2 bagian yaitu V1 = {v1, v2, v3} dan V2 = {v4, v5}. Setiap titik dalam V1 dihubungkan dengan setiap titik dalam  V2. Maka graf-nya merupakan K3,2.

    b.    Hanya merupakan graf bipartite saja karena titik-titik dalam graf terbagi menjadi 2 bagian, yaitu V1 = {v1, v3} dan V2 = {v2, v4}. Akan tetapi, tidak semua titik dalam V1 dihubungkan dengan semua titik dalam V2 (v1 tidak dihubungkan dengan v4).

    c.    Dengan pengaturan letak titik-titiknya, maka graf Gambar 11 (c) dapat digambarkan sebagai graf pada Gambar 12.

Tampak bahwa titik-titiknya terbagi menjadi 2 bagian yaitu V1 = {v1, v3, v5}   dan   V2 = {v2, v4, v6}. Setiap garis menghubungkan sebuah titik dalam V1 dengan sebuah titik dalam V2, sehingga graf-nya merupakan graf bipartite

d.    Perhatikan bahwa meskipun tampak berbeda, sebenarnya graf pda Gambar 11 (d) sama dengan graf Gambar 11 (a), sehingga graf Gambar 11 (d) adalah K3,2.

Posisi titik-titik dalam penggambaran graf kadang-kadang mempengaruhi pandangan, seperti halnya pada contoh (c) dan (d). Dalam kedua graf tersebut, semua titik tampaknya terhubung dan tidak dapat dipisahkan walaupun kenyataannya tidaklah demikian. Oleh karena itu, harus jeli dalam menentukan apakah suatu graf merupakan Graf Bipartite