GRAFF

PENGERTIAN GRAFF

Graf  (graph) adalah himpunan benda-benda yang disebut simpul(vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Graf trival (satu titik tampa sisi satu pun). 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.

Dasar-Dasar Graf

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.

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. G1 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). G2 dan G3 pada Gambar 2 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 disebutgraf 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 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.

Graph Isomorfik

Dalam geometri, dua gambar disebut kongruen jika keduanya mempunyai sifat-sifat geometri yang sama. Maka dengan cara yang sama, dua graf disebut isomorfis jika keduanya menunjukkan "bentuk" yang sama, kedua graph tersebut hanya berbeda dalam hal pemberian label titik dan garisnya saja.

Syarat dua buah graph dikatakan isomorfik, yaitu :

1.      Memiliki jumlah simpul yang sama

2.      Memiliki jumlah garis yang sama

3.      Memiliki derajat yang sama dari simpul-simpulnya

Catatan : apabila dua graph yang berbeda tidak memiliki salah satu dari syarat diatas sudah pasti kedua graphtersebut tidak isomorfis, tetapi walaupun kedua graph tersebut memiliki seluruh syarat diatas belum tentu juga keduanya isomorfis.

CONTOH :

Periksa apakah kedua graf tersebut isomorfik? Jika ya, tentukan simpul-simpul yang saling berkorespondensi antara G₁ dan G₂

Jawab :

Ya,  kedua graf tersebut adalah isomorfik. Terlihat graf tersebut memuat simpul dimana setiap simpulnya masing-masing berderajat tiga. Simpul yang saling berkorespondensi dari kedua graf tersebut adalah :

simpul u1 dengan simpul v1

simpul u2 dengan simpul v3

simpul u3 dengan simpul v5

simpul u4 dengan simpul v6 

simpul u5 dengan simpul v4

simpul u6 dengan simpul v2

Pada dua graf yang isomorfik, kedua graf tersebut memiliki matriks ketetanggaan yang sama, tentunya setelah matriks yang berkorespondensi diurutakan dalam urutan yang sama.

Perhatikan matriks ketetanggaan dari kedua graf  tersebut. Dibawah ini adalah matriks ketetanggaan dari graf G₁ dan G₂:

Terlihat bahwa kedua graf  tersebut  memiliki  matriks  ketetanggaan  yang  sama,   yaitu  M_G1 =  M_G2.