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 merupakan graf tanpa sisi rangkap dengan simpul. Matriks ketetanggaan dari merupakan matriks persegi berukuran dengan aturan entri sebagai berikut. Misalkan Dengan demikian, entri jika simpul dan bertetangga. Sebaliknya, jika simpul dan tidak bertetangga. Dengan kata lain,
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 Dengan kata lain, dan ketika Jika suatu simpul pada graf memuat gelang, simpul itu dianggap bertetangga dengan dirinya sendiri sehingga
Sebagai contoh, misalkan graf dan graf komplemennya, 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 dan berturut-turut adalah sebagai berikut.

Karena entri dari matriks ketetanggaan hanya memiliki dua nilai, yaitu dan matriks tersebut juga kadang dinamakan matriks nol-satu (zero-one matrix). Beberapa literatur juga menggunakan simbol (true) dan (false) sebagai pengganti angka dan 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 simpul, ada cara untuk mengurutkan nomor simpul, artinya ada matriks ketetanggaan berbeda untuk graf yang sama dengan simpul.
Senarai Ketetanggaan
Jika suatu graf memiliki sisi yang relatif sedikit, matriks ketetanggaannya akan mengandung banyak entri yang bernilai 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 (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 beserta senarai ketetanggaannya.
Contoh 2:
Berikut merupakan model graf takberarah beserta senarai ketetanggaannya.
Contoh 3:
Berikut merupakan model graf berarah 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 adalah graf dengan simpul dan sisi. Matriks kebersisian dari berordo Baris matriks kebersisian menunjukkan bagian simpul, sedangkan kolom matriks kebersisian menunjukkan bagian sisi. Misalkan matriks kebersisian tersebut adalah Nilai jika simpul bersisian dengan simpul Sebaliknya, nilai jika simpul tidak bersisian dengan simpul
Matriks kebersisian dapat digunakan untuk merepresentasikan graf taksederhana, artinya graf tersebut memuat sisi rangkap atau gelang. Dengan menggunakan matriks kebersisian, derajat dari setiap simpul dapat dihitung dengan menjumlahkan entri-entri pada baris untuk simpul kecuali untuk graf yang memuat gelang.
Berikut merupakan model graf 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 dan dikatakan isomorfis (isomorphic) jika terdapat fungsi satu-satu dan pada, katakanlah fungsi dari ke dengan sifat bahwa simpul dan bertetangga di jika dan hanya jika dan bertetangga di untuk setiap Fungsi yang seperti itu dinamakan isomorfisme (isomorphism). Dua graf sederhana yang tidak isomorfis disebut takisomorfis (nonisomorphic). Secara matematis, jika dan isomorfis, kita notasikan baca: isomorfis dengan
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.
- Jika dua graf isomorfis, maka dua graf tersebut pasti memiliki banyak simpul dan banyak sisi yang sama, tetapi tidak sebaliknya.
- Jika dua graf isomorfis, maka dua graf tersebut pasti memiliki barisan derajat simpul yang sama, tetapi tidak sebaliknya.
- Dua graf isomorfis jika dan hanya jika graf komplemennya juga isomorfis.
Perhatikan dua model graf berikut.
Graf dan tidak isomorfis. Hal ini mudah dilihat karena banyak sisi pada kedua graf tersebut tidaklah sama. Graf hanya memiliki sisi, sedangkan graf memiliki sisi. Akibatnya, tidak mungkin ada korespondensi satu-satu antara simpul pada dan
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 dikatakan graf swakomplemen (self-complementary graph) jika isomorfis dengan komplemennya,
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_Soal. Folder 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.
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
- Semua entri pada baris dan kolom tersebut bernilai
- Semua entri pada baris dan kolom tersebut bernilai
- Semua entri pada baris tersebut bernilai sedangkan entri kolomnya tidak selalu bernilai
- Sebagian entri pada baris dan kolom tersebut bernilai
- Jika dan berturut-turut menyatakan urutan baris dan kolom matriks ketetanggaannya, maka jika dan jika
Pembahasan
Simpul terpencil merupakan simpul yang berderajat artinya simpul tersebut tidak bertetangga dengan simpul yang lain dari suatu graf. Karena entri matriks ketetanggaan bernilai ketika dua simpul yang berkorespondensi tidak bertetangga, disimpulkan bahwa semua entri pada baris dan kolom matriks ketetanggaan yang berkorespondensi dengan simpul terpencil bernilai
(Jawaban A)
[collapse]
Soal Nomor 2
Suatu graf memiliki simpul dan sisi. Pernyataan berikut yang benar mengenai matriks ketetanggaan atau matriks kebersisian dari adalah
- Matriks kebersisian dari memiliki ordo
- Matriks kebersisian dari memiliki ordo
- Matriks ketertanggaan dari memiliki ordo
- Matriks ketertanggaan dari memiliki ordo
- Ada entri pada matriks ketertanggaan dari
Pembahasan
Pada matriks ketertanggaan, setiap baris dan kolom berkorespondensi dengan simpul-simpul yang dimiliki oleh suatu graf. Dengan kata lain, banyak sisi tidak memengaruhi ordo dari matriks ketertanggaan. Karena graf memiliki simpul, matriks ketertanggaannya akan berordo dengan banyak entri
Pada matriks kebersisian, setiap baris berkorespondensi dengan simpul, sedangkan setiap kolom berkorespondensi dengan sisi. Karena graf memiliki simpul dan sisi, ordo matriks kebersisiannya adalah dengan banyak entri
Jadi, pernyataan yang tepat diberikan oleh opsi C.
(Jawaban C)
[collapse]
Soal Nomor 3
Perhatikan model graf berikut.
Matriks ketetanggaan dari graf di atas adalah sebagai berikut.
Nilai dari
A. C. E.
B. D.
Pembahasan
Misalkan merupakan matriks ketetanggaan dari graf tersebut.
- karena simpul dan bertetangga.
- karena simpul dan bertetangga.
- karena simpul dan bertetangga.
- karena simpul dan tidak bertetangga.
- karena simpul bertetangga dengan dirinya sendiri (memuat gelang).
Jadi, nilai dari (Jawaban C)
[collapse]
Soal Nomor 4
Nilai sehingga graf siklus merupakan graf swakomplemen adalah
A. C. E.
B. D.
Pembahasan
Misalkan merupakan graf siklus dengan simpul. Agar termasuk graf swakomplemen, harus ditunjukkan bahwa dengan merupakan graf komplemen dari
Salah satu cara untuk menunjukkan dua graf itu isomorfis adalah dengan menghitung banyak sisinya yang harus sama, yaitu
Gabungan dari dan merupakan graf lengkap Karena memiliki simpul, sedangkan memiliki diperoleh
Nilai yang memenuhi persamaan terakhir adalah atau Karena menyatakan banyak simpul, nilainya tidak mungkin nol. Jadi, diperoleh Dengan kata lain, dan merupakan satu-satunya pasangan graf yang komplemen satu sama lain dan memuat banyak sisi yang sama. Kemudian, dapat ditunjukkan bahwa dan isomorfis seperti yang terlihat pada gambar berikut.
(Jawaban A)
[collapse]
Bagian Uraian
Soal Nomor 1
Gambarkan contoh dua graf sederhana, beraturan, memiliki simpul, dan sisi, tetapi tidak isomorfis.
Pembahasan
Berikut diberikan contoh dua graf beraturan, memiliki simpul, dan sisi, tetapi tidak isomorfis.
Dua graf tersebut tidak memuat sisi rangkap maupun gelang sehingga tergolong graf sederhana, masing-masing memiliki simpul dan sisi. Setiap simpul dari masing-masing graf berderajat sehingga termasuk graf beraturan, yaitu graf yang setiap simpulnya berderajat sama. Namun, dua graf tersebut tidak isomorfis karena graf pertama (kiri) membuat siklus dengan panjang sedangkan graf kedua (kanan) tidak memuat siklus seperti itu.
Dari sini, disimpulkan bahwa dua graf tersebut isomorfis.
[collapse]
Soal Nomor 2
Periksa apakah dua graf berikut isomorfis atau tidak.

Pembahasan
Setelah observasi dilakukan, klaim bahwa dua graf tersebut isomorfis karena terdapat fungsi satu-satu dan pada antara simpul pada graf pertama (kiri) dengan simpul pada graf kedua (kanan). Pertama, kita beri label pada setiap simpul yang ada seperti berikut.
Misalkan merupakan fungsi yang mengaitkan simpul pada graf pertama dan kedua. Korespondensi satu-satu yang dimaksud adalah sebagai berikut.
Karena mengawetkan ketetanggaan, merupakan isomorfisme dari dua graf itu. Catat bahwa mungkin ada fungsi lain yang juga merupakan isomorfisme dari dua graf tersebut (kita cukup pilih satu fungsi).
Dari sini, disimpulkan bahwa dua graf tersebut isomorfis.
[collapse]
Soal Nomor 3
Periksa apakah dua graf berikut isomorfis atau tidak.

Pembahasan
Setelah observasi dilakukan, klaim bahwa dua graf tersebut takisomorfis karena tidak terdapat fungsi satu-satu dan pada antara simpul pada graf pertama (kiri) dengan simpul pada graf kedua (kanan). Ada bukti yang memperkuat pernyataan bahwa tidak terdapat fungsi seperti itu. Perhatikan gambar berikut.
Simpul yang diberi warna merah pada graf pertama berderajat dan bertetangga dengan tiga simpul berwarna biru yang masing-masing berderajat dan Namun, tidak ada simpul berderajat di graf kedua yang bertetangga dengan tiga simpul berderajat dan Dengan kata lain, korespondensi satu-satu tidak akan dapat dibentuk.
Dari sini, disimpulkan bahwa dua graf tersebut takisomorfis.
[collapse]
Soal Nomor 4
Periksa apakah dua graf berikut isomorfis atau tidak.

Pembahasan
Setelah observasi dilakukan, klaim bahwa dua graf tersebut takisomorfis karena tidak terdapat fungsi satu-satu dan pada antara simpul pada graf pertama (kiri) dengan simpul pada graf kedua (kanan). Ada bukti yang memperkuat pernyataan bahwa tidak terdapat fungsi seperti itu. Perhatikan gambar berikut.
Simpul yang diberi warna merah pada graf pertama berderajat dan bertetangga dengan dua simpul berwarna biru yang masing-masing berderajat dan Namun, tidak ada simpul berderajat di graf kedua yang bertetangga dengan dua simpul berderajat dan Dengan kata lain, korespondensi satu-satu tidak akan dapat dibentuk.
Dari sini, disimpulkan bahwa dua graf tersebut takisomorfis.
[collapse]
Soal Nomor 5
Apakah pasangan graf sederhana dengan matriks ketertanggaan berikut isomorfis? Jelaskan.
Pembahasan
Jawaban a)
Dua graf dengan matriks ketertanggaan dan dapat digambarkan sebagai dua sisi segitiga. Masing-masing graf memuat tiga simpul dan dua sisi. Satu simpul berderajat sedangkan dua simpul lainnya berderajat Jadi, dua graf tersebut isomorfis.
Jawaban b)
Dua graf dengan matriks ketertanggaan dan tidak isomorfis karena banyak sisinya berbeda. Untuk melihatnya, jumlahkan semua entri di atas atau di bawah diagonal utama matriks ketetanggannya. Graf pertama memiliki sisi, sedangkan graf kedua memiliki sisi.
Jawaban c)
Dua graf dengan matriks ketertanggaan dan tidak isomorfis karena banyak sisinya berbeda. Untuk melihatnya, jumlahkan semua entri di atas atau di bawah diagonal utama matriks ketetanggannya. Graf pertama memiliki sisi, sedangkan graf kedua memiliki sisi.
[collapse]
Soal Nomor 6
Buktikan bahwa jika dan merupakan graf isomorfis, maka derajat simpul-simpul di sama dengan derajat simpul-simpul di Dengan kata lain, barisan derajat sama dengan barisan derajat
Pembahasan
Misalkan merupakan isomorfisme. Ambil sembarang simpul dan misalkan Misalkan juga bertetangga dengan dan tidak bertetangga dengan Dapat dilihat bahwa dan
Berdasarkan definisi isomorfisme, bertetangga dengan dan tidak bertetangga dengan Akibatnya,
Karena merupakan sembarang simpul di yang dipetakan oleh isomorfisme ke simpul disimpulkan bahwa derajat simpul-simpul di sama dengan derajat simpul-simpul di
Jadi, proposisi terbukti benar.
[collapse]
Soal Nomor 7
Misalkan dan merupakan graf sederhana. Buktikan bahwa dan isomorfis jika dan hanya jika komplemennya, dan juga isomorfis.
Pembahasan
Misalkan dan merupakan graf sederhana.
Pertama, akan ditunjukkan bahwa jika dan isomorfis, maka dan juga isomorfis.
Misalkan dan isomorfis. Menurut definisi, terdapat isomorfisme Ambil sembarang simpul Tanpa mengurangi keumuman, misalkan Menurut definisi komplemen, Karena merupakan isomorfisme dari ke diperoleh Menurut definisi komplemen,
Karena merupakan isomorfisme dari ke terbukti bahwa dan juga isomorfis.
Dengan cara yang serupa, akan ditunjukkan bahwa jika dan juga isomorfis, maka dan isomorfis.
Misalkan dan isomorfis. Menurut definisi, terdapat isomorfisme Ambil sembarang simpul Tanpa mengurangi keumuman, misalkan Menurut definisi komplemen, Karena merupakan isomorfisme dari ke diperoleh Menurut definisi komplemen,
Karena merupakan isomorfisme dari ke terbukti bahwa dan juga isomorfis.
Jadi, dapat disimpulkan bahwa proposisi terbukti benar secara keseluruhan.
[collapse]
Soal Nomor 8
Buktikan bahwa isomorfisme graf merupakan relasi ekuivalensi.
Pembahasan
Untuk membuktikan bahwa isomorfisme graf merupakan relasi ekuivalensi, kita harus membuktikan bahwa isomorfisme graf merupakan relasi refleksif, simetris, dan transitif.
Misalkan merupakan graf sederhana.
Relasi releksif:
Pemetaan identitas pada merupakan bijeksi yang memetakan setiap simpul pada dirinya sendiri. Akibatnya, ketertanggaan diawetkan. Jadi, isomorfisme graf merupakan relasi refleksif.
Relasi simetris:
Misalkan isomorfis dengan Akibatnya, ada suatu isomorfisme Misalkan inversnya, didefinisikan oleh
untuk setiap dan
Karena invers dari bijeksi merupakan bijeksi, merupakan bijeksi.
Misalkan sehingga dan untuk suatu
Akibatnya,
Jadi, dan bertetangga jika dan hanya jika dan bertetangga.
Karena isomorfis dengan dan bertetangga jika dan hanya jika dan bertetangga.
Ini berarti dan bertetangga jika dan hanya jika dan bertetangga.
Jadi, isomorfis dengan sehingga isomorfisme graf merupakan relasi simetris.
Relasi transitif:
Misalkan isomorfis dengan dan isomorfis dengan Akibatnya, ada suatu isomorfisme
Tinjau pemetaan komposisi
Karena komposisi dari bijeksi juga bijeksi, merupakan bijeksi dari ke
Misalkan dan serta
Karena dan merupakan isomorfisme, didapat bahwa
dan bertetangga jika dan hanya jika dan bertetangga; dan
dan bertetangga jika dan hanya jika dan bertetangga.
Akibatnya,
dan bertetangga jika dan hanya jika dan bertetangga.
Jadi, merupakan isomorfisme dari ke sehingga isomorfis dengan Disimpulkan bahwa isomorfisme graf merupakan relasi transitif.
Karena isomorfisme graf merupakan relasi refleksif, simetris, dan transitif, disimpulkan bahwa isomorfisme graf merupakan relasi ekuivalensi.
[collapse]
Soal Nomor 9
Buktikan bahwa graf swakomplemen mempunyai simpul sebanyak atau untuk suatu bilangan bulat positif
Pembahasan
Misalkan merupakan graf swakomplemen dengan sisi. Berdasarkan definisi isomorfisme, juga memiliki sisi. Gabungan dari dan adalah graf lengkap, yaitu graf yang setiap simpulnya saling bertetangga satu sama lain. Lebih lanjut, graf lengkap dengan simpul memiliki sisi sebanyak Dengan kata lain, sehingga didapat Agar bulat, haruslah atau Dengan demikian, terdapat suatu bilangan bulat sehingga atau Jadi, terbukti bahwa graf swakomplemen mempunyai simpul sebanyak atau untuk suatu bilangan bulat positif
[collapse]