Materi, Soal, dan Pembahasan – Representasi Graf dan Isomorfisme Graf

Representasi graf dan isomorfisme graf

Graf dapat direpresentasikan dalam berbagai macam bentuk selain dimodelkan dalam gambar. Kita dapat merepresentasikannya dalam bentuk matriks ketetanggaan, senarai ketetanggaan, dan matriks kebersisian.

Artikel tentang Graf

Matriks Ketetanggaan

Matriks ketetanggaan (adjacency matrix) merupakan salah satu representasi graf yang sering dijumpai. Misalkan G=(V,E) merupakan graf tanpa sisi rangkap dengan n1 simpul. Matriks ketetanggaan A dari G merupakan matriks persegi berukuran n×n dengan aturan entri sebagai berikut. Misalkan A=[aij]. Dengan demikian, entri aij=1 jika simpul i dan j bertetangga. Sebaliknya, aij=0 jika simpul i dan j tidak bertetangga. Dengan kata lain,
aij={1,jika {i,j}E(G)0,jika {i,j}E(G)Dapat dilihat bahwa matriks ketetanggaan dari graf sederhana (tidak memuat sisi rangkap maupun gelang) merupakan matriks simetris, yaitu matriks yang transposnya sama dengan dirinya sendiri, serta matriks tersebut memiliki diagonal utama yang semua entrinya bernilai 0. Dengan kata lain, aij=aji dan aij=0 ketika i=j. Jika suatu simpul i pada graf memuat gelang, simpul itu dianggap bertetangga dengan dirinya sendiri sehingga aij=1.

Sebagai contoh, misalkan graf G dan graf komplemennya, G, diberikan sebagai berikut.
Perhatikan bahwa setiap simpul pada masing-masing graf telah dilabeli dengan nomor (yang urutannya tidak mesti seperti itu). Dengan demikian, matriks ketetanggaan dari graf G dan G berturut-turut adalah sebagai berikut.

Karena entri dari matriks ketetanggaan hanya memiliki dua nilai, yaitu 0 dan 1, matriks tersebut juga kadang dinamakan matriks nol-satu (zero-one matrix). Beberapa literatur juga menggunakan simbol T (true) dan F (false) sebagai pengganti angka 1 dan 0 pada matriks tersebut. Lebih lanjut, matriks ketetanggaan disusun berdasarkan pelabelan pada simpul pada graf. Ini berarti setiap simpul pada graf harus dilabeli (diberi nama) terlebih dahulu sebelum direpresentasikan dalam bentuk matriks ketetanggaan. Karena ada n simpul, ada n! cara untuk mengurutkan nomor simpul, artinya ada n! matriks ketetanggaan berbeda untuk graf yang sama dengan n simpul.


Senarai Ketetanggaan

Jika suatu graf memiliki sisi yang relatif sedikit, matriks ketetanggaannya akan mengandung banyak entri yang bernilai 0. Matriks yang banyak memuat entri nol kadang dinamakan matriks jarang (sparse matrix). Ketika diimplementasikan dengan menggunakan komputer, ruang memori yang dibutuhkan untuk matriks jarang termasuk boros karena komputer menyimpan entri nol yang sebenarnya tidak bermanfaat. Oleh karena itu, ada representasi graf lain yang dapat menutupi kelemahan dari matriks ketetanggaan, yaitu senarai ketetanggaan (adjacency list).

Pada senarai ketetanggaan, kita mendaftarkan setiap simpul yang telah dilabeli dari suatu graf, kemudian mengidentifikasi tetangga dari masing-masing simpul tersebut.  Jika simpul yang dimaksud berderajat 0 (tidak memiliki tetangga), kita dapat memberikan tanda strip (-) sebagai gantinya.  Untuk menyajikan senarai ketetanggaan, kita biasanya menggunakan tabel dua kolom: kolom pertama berisi simpul awal, sedangkan kolom kedua berisi simpul akhir. Pada multigraf, jika dua simpul dihubungkan oleh lebih dari satu sisi, kita harus tuliskan simpul akhir sebanyak sisinya pada baris yang sama.

Contoh 1:
Berikut merupakan model graf takberarah G beserta senarai ketetanggaannya.
Contoh 2:

Berikut merupakan model graf takberarah H beserta senarai ketetanggaannya.
Contoh 3:

Berikut merupakan model graf berarah P beserta senarai ketetanggaannya.


Matriks Kebersisian

Matriks kebersisian (incidency matrix), kadang juga disebut sebagai matriks keterkaitan, menyatakan kebersisian simpul dengan sisi pada suatu graf, berbeda dengan matriks ketetanggaan yang menyatakan ketetanggaan dari simpul-simpul pada suatu graf. Misalkan G=(V,E) adalah graf dengan n simpul dan m sisi. Matriks kebersisian dari G berordo n×m. Baris matriks kebersisian menunjukkan bagian simpul, sedangkan kolom matriks kebersisian menunjukkan bagian sisi. Misalkan matriks kebersisian tersebut adalah A=[aij]. Nilai aij=1 jika simpul i bersisian dengan simpul j. Sebaliknya, nilai aij=0jika simpul i tidak bersisian dengan simpul j.

Matriks kebersisian dapat digunakan untuk merepresentasikan graf taksederhana, artinya graf tersebut memuat sisi rangkap atau gelang. Dengan menggunakan matriks kebersisian, derajat dari setiap simpul i dapat dihitung dengan menjumlahkan entri-entri pada baris untuk simpul i, kecuali untuk graf yang memuat gelang.

Berikut merupakan model graf G beserta matriks kebersisiannya.


Ketika dua orang diminta untuk menggambar graf dengan banyak simpul, sisi, dan ketetanggaan tertentu, sangat mungkin mereka berdua menggambar graf yang secara tampilan tidaklah sama. Namun, dua graf yang digambar mereka sebenarnya “sama”, atau lebih tepatnya sama secara struktur.
Fenomena inilah yang menjadi latar belakang diciptakannya definisi tentang kesamaan graf secara struktur yang selanjutnya memunculkan terminologi baru dalam graf, yaitu isomorfisme.

Definisi: Isomorfisme Graf

Graf sederhana G1=(V1,E1) dan G2=(V2,E2) dikatakan isomorfis (isomorphic) jika terdapat fungsi satu-satu dan pada, katakanlah fungsi f, dari V1 ke V2 dengan sifat bahwa simpul a dan b bertetangga di G1 jika dan hanya jika f(a) dan f(b) bertetangga di G2, untuk setiap a,bV1. Fungsi f yang seperti itu dinamakan isomorfisme (isomorphism). Dua graf sederhana yang tidak isomorfis disebut takisomorfis (nonisomorphic). Secara matematis, jika G1 dan G2 isomorfis, kita notasikan G1G2 (baca: G1 isomorfis dengan G2).

Dengan kata lain, ketika dua graf sederhana isomorfis, terdapat korespondensi satu-satu antara simpul-simpul pada dua graf tersebut yang mengawetkan hubungan ketetanggaan. Isomorfisme dari graf sederhana merupakan relasi ekuivalensi karena bersifat refleksif, simetris, dan transitif.

Beberapa fakta penting yang berkenaan dengan isomorfisme graf diberikan sebagai berikut.

  1. Jika dua graf isomorfis, maka dua graf tersebut pasti memiliki banyak simpul dan banyak sisi yang sama, tetapi tidak sebaliknya.
  2. Jika dua graf isomorfis, maka dua graf tersebut pasti memiliki barisan derajat simpul yang sama, tetapi tidak sebaliknya.
  3. Dua graf isomorfis jika dan hanya jika graf komplemennya juga isomorfis.

Perhatikan dua model graf berikut.
Graf G1 dan G2 tidak isomorfis. Hal ini mudah dilihat karena banyak sisi pada kedua graf tersebut tidaklah sama. Graf G1 hanya memiliki 3 sisi, sedangkan graf G2 memiliki 4 sisi. Akibatnya, tidak mungkin ada korespondensi satu-satu antara simpul pada G1 dan G2.

Sampai saat ini, belum ada algoritma yang efektif dan efisien untuk memeriksa apakah dua graf isomorfis atau tidak. Sejauh ini, algoritma terbaik yang ada mempunyai kompleksitas waktu eksponensial pada kasus terburuk. Semakin banyak simpul dalam suatu graf, kebutuhan waktu algoritma tersebut akan meningkat sangat drastis. Namun, mungkin saja di masa depan, algoritma baru ditemukan, dan tidak menutup kemungkinan kalau Anda yang membaca tulisan ini sekarang merupakan penemunya.

Definisi: Graf Swakomplemen

Suatu graf sederhana G dikatakan graf swakomplemen (self-complementary graph) jika G isomorfis dengan komplemennya, G. 

Berikut ini merupakan dua contoh graf swakomplemen. 


Di bawah ini telah disediakan sejumlah soal dan pembahasan tentang representasi graf dan isomorfisme graf. Sebagian soal dibuat oleh penulis sendiri dan sebagian lainnya diadaptasi dari literatur.

Jika Anda ingin mencari soal latihan yang lebih banyak, Anda dapat mengakses ke folder soal mathcyber1997.com dengan mendaftar di bit.ly/Akses_SoalFolder soal tersebut berisi soal UTBK-SNBT, soal persiapan CPNS-PPPK, soal psikotes, soal TPA, soal ujian masuk perguruan tinggi (termasuk STAN), soal kompetensi matematika (termasuk OSN dan ON MIPA), dan masih banyak lagi.

Baca: Istilah Lengkap dalam Teori Graf


Artikel ini ditulis berdasarkan beberapa sumber. Salah satu sumber berbahasa Indonesia yang digunakan adalah buku “Matematika Diskrit” karya Rinaldi Munir. Untuk sumber berbahasa Inggris, salah satu yang digunakan adalah buku “Discrete Mathematics and Its Applications” yang ditulis oleh Kenneth H. Rosen. Oleh karena itu, untuk meminimalisasi kesalahan penafsiran, padanan untuk beberapa kata/istilah diberikan dalam tabel berikut.

No.Bahasa IndonesiaBahasa Inggris1.Matriks KetetanggaanAdjacency Matrix2.Matriks KebersisianIncidency Matrix3.Senarai KetetanggaanAdjacency List4.IsomorfismeIsomorfism5.IsomorfisIsomorphic5.Matriks JarangSparse Matrix7.Matriks SimetrisSymmetry Matrix8.Graf SwakomplemenSelf-complementary Graph


Quote by J.S. Khairen

Pergilah ke depan kaca dan maafkanlah sosok yang ada di sana. Kita semua boleh menyesal, tetapi jangan memilih menderita.

Bagian Pilihan Ganda

Soal Nomor 1

Pernyataan berikut yang tepat mengenai baris dan kolom matriks ketetanggaan yang berkorespondensi dengan simpul terpencil dari suatu graf sederhana adalah

  1. Semua entri pada baris dan kolom tersebut bernilai 0
  2. Semua entri pada baris dan kolom tersebut bernilai 1
  3. Semua entri pada baris tersebut bernilai 0, sedangkan entri kolomnya tidak selalu bernilai 0
  4. Sebagian entri pada baris dan kolom tersebut bernilai 0
  5. Jika i dan j berturut-turut menyatakan urutan baris dan kolom matriks ketetanggaannya, maka aij=1 jika i=j dan aij=0 jika ij.
Pembahasan

Soal Nomor 2

Suatu graf G memiliki 12 simpul dan 9 sisi. Pernyataan berikut yang benar mengenai matriks ketetanggaan atau matriks kebersisian dari G adalah

  1. Matriks kebersisian dari G memiliki ordo 9×12
  2. Matriks kebersisian dari G memiliki ordo 9×9
  3. Matriks ketertanggaan dari G memiliki ordo 12×9
  4. Matriks ketertanggaan dari G memiliki ordo 12×12
  5. Ada 81 entri pada matriks ketertanggaan dari G

Pembahasan

Soal Nomor 3

Perhatikan model graf berikut.
Matriks ketetanggaan dari graf di atas adalah sebagai berikut.
Nilai dari a+b+c+d+e=
A. 2                         C. 4                      E. 6
B. 3                         D. 5

Pembahasan

Soal Nomor 4

Nilai n sehingga graf siklus Cn merupakan graf swakomplemen adalah
A. 5                         C. 8                       E. 15
B. 6                         D. 10

Pembahasan

Bagian Uraian

Soal Nomor 1

Gambarkan contoh dua graf sederhana, beraturan, memiliki 8 simpul, dan 8 sisi, tetapi tidak isomorfis.

Pembahasan

Soal Nomor 2

Periksa apakah dua graf berikut isomorfis atau tidak.

Pembahasan

Soal Nomor 3

Periksa apakah dua graf berikut isomorfis atau tidak.

Pembahasan

Soal Nomor 4

Periksa apakah dua graf berikut isomorfis atau tidak.

Pembahasan

Soal Nomor 5

Apakah pasangan graf sederhana dengan matriks ketertanggaan berikut isomorfis? Jelaskan.

  1. (001001110),(011100100)
  2. (0101100100011110),(0111100110011110)
  3. (0110100110010110),(0101100000011010)

Pembahasan

Soal Nomor 6

Buktikan bahwa jika G dan H merupakan graf isomorfis, maka derajat simpul-simpul di G sama dengan derajat simpul-simpul di H. Dengan kata lain, barisan derajat G sama dengan barisan derajat H.

Pembahasan

Soal Nomor 7

Misalkan G dan H merupakan graf sederhana. Buktikan bahwa G dan H isomorfis jika dan hanya jika komplemennya, G dan H, juga isomorfis.

Pembahasan

Soal Nomor 8

Buktikan bahwa isomorfisme graf merupakan relasi ekuivalensi.

Pembahasan

Soal Nomor 9

Buktikan bahwa graf swakomplemen mempunyai simpul sebanyak 4k atau 4k+1 untuk suatu bilangan bulat positif k.

Pembahasan