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
Berikut ini merupakan beberapa artikel yang tersedia, berkaitan dengan materi graf.
Materi, Soal, dan Pembahasan – Dasar-Dasar Graf dan Terminologinya
Materi, Soal, dan Pembahasan – Operasi pada Graf dan Konsep Subgraf
Matriks Ketetanggaan
Matriks ketetanggaan (adjacency matrix) merupakan salah satu representasi graf yang sering dijumpai. Misalkan $G = (V, E)$ merupakan graf tanpa sisi rangkap dengan $n \ge 1$ simpul. Matriks ketetanggaan $A$ dari $G$ merupakan matriks persegi berukuran $n \times n$ dengan aturan entri sebagai berikut. Misalkan $A = [a_{ij}].$ Dengan demikian, entri $a_{ij} = 1$ jika simpul $i$ dan $j$ bertetangga. Sebaliknya, $a_{ij} = 0$ jika simpul $i$ dan $j$ tidak bertetangga. Dengan kata lain,
$$a_{ij} = \begin{cases} 1, &\text{jika}~\{i, j\} \in E(G) \\ 0, &\text{jika}~\{i, j\} \notin E(G) \end{cases}$$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, $a_{ij} = a_{ji}$ dan $a_{ij} = 0$ ketika $i = j.$ Jika suatu simpul $i$ pada graf memuat gelang, simpul itu dianggap bertetangga dengan dirinya sendiri sehingga $a_{ij} = 1.$
Sebagai contoh, misalkan graf $G$ dan graf komplemennya, $\overline{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 $\overline{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 \times m.$ Baris matriks kebersisian menunjukkan bagian simpul, sedangkan kolom matriks kebersisian menunjukkan bagian sisi. Misalkan matriks kebersisian tersebut adalah $A = [a_{ij}].$ Nilai $a_{ij} = 1$ jika simpul $i$ bersisian dengan simpul $j.$ Sebaliknya, nilai $a_{ij} = 0$jika 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
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 $G_1$ dan $G_2$ tidak isomorfis. Hal ini mudah dilihat karena banyak sisi pada kedua graf tersebut tidaklah sama. Graf $G_1$ hanya memiliki $3$ sisi, sedangkan graf $G_2$ memiliki $4$ sisi. Akibatnya, tidak mungkin ada korespondensi satu-satu antara simpul pada $G_1$ dan $G_2.$
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
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.
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.
$$\begin{array}{ccc} \hline \text{No.} & \text{Bahasa Indonesia} & \text{Bahasa Inggris} \\ \hline 1. & \text{Matriks Ketetanggaan} & \text{Adjacency Matrix} \\ 2. & \text{Matriks Kebersisian} & \text{Incidency Matrix} \\ 3. & \text{Senarai Ketetanggaan} & \text{Adjacency List} \\ 4. & \text{Isomorfisme} & \text{Isomorfism} \\ 5. & \text{Isomorfis} & \text{Isomorphic} \\ 5. & \text{Matriks Jarang} & \text{Sparse Matrix} \\ 7. & \text{Matriks Simetris} & \text{Symmetry Matrix} \\ 8. & \text{Graf Swakomplemen} & \text{Self-complementary Graph} \\ \hline \end{array}$$
Quote by J.S. Khairen
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 $\cdots \cdot$
- Semua entri pada baris dan kolom tersebut bernilai $0$
- Semua entri pada baris dan kolom tersebut bernilai $1$
- Semua entri pada baris tersebut bernilai $0,$ sedangkan entri kolomnya tidak selalu bernilai $0$
- Sebagian entri pada baris dan kolom tersebut bernilai $0$
- Jika $i$ dan $j$ berturut-turut menyatakan urutan baris dan kolom matriks ketetanggaannya, maka $a_{ij} = 1$ jika $i = j$ dan $a_{ij} = 0$ jika $i \neq j.$
Simpul terpencil merupakan simpul yang berderajat $0,$ artinya simpul tersebut tidak bertetangga dengan simpul yang lain dari suatu graf. Karena entri matriks ketetanggaan bernilai $0$ ketika dua simpul yang berkorespondensi tidak bertetangga, disimpulkan bahwa semua entri pada baris dan kolom matriks ketetanggaan yang berkorespondensi dengan simpul terpencil bernilai $0.$
(Jawaban A)
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 $\cdots \cdot$
- Matriks kebersisian dari $G$ memiliki ordo $9 \times 12$
- Matriks kebersisian dari $G$ memiliki ordo $9 \times 9$
- Matriks ketertanggaan dari $G$ memiliki ordo $12 \times 9$
- Matriks ketertanggaan dari $G$ memiliki ordo $12 \times 12$
- Ada $81$ entri pada matriks ketertanggaan dari $G$
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 $G$ memiliki $12$ simpul, matriks ketertanggaannya akan berordo $12 \times 12$ dengan banyak entri $144.$
Pada matriks kebersisian, setiap baris berkorespondensi dengan simpul, sedangkan setiap kolom berkorespondensi dengan sisi. Karena graf $G$ memiliki $12$ simpul dan $9$ sisi, ordo matriks kebersisiannya adalah $12 \times 9$ dengan banyak entri $108.$
Jadi, pernyataan yang tepat diberikan oleh opsi C.
(Jawaban C)
Soal Nomor 3
Perhatikan model graf berikut.
Matriks ketetanggaan dari graf di atas adalah sebagai berikut.
Nilai dari $a+b+c+d+e=\cdots \cdot$
A. $2$ C. $4$ E. $6$
B. $3$ D. $5$
Misalkan $A = [a_{ij}]$ merupakan matriks ketetanggaan dari graf tersebut.
- $a = a_{12} = a_{21} = 1$ karena simpul $1$ dan $2$ bertetangga.
- $b = a_{13} = a_{31} = 1$ karena simpul $1$ dan $3$ bertetangga.
- $c = a_{23} = a_{32} = 1$ karena simpul $2$ dan $3$ bertetangga.
- $d = a_{34} = a_{43} = 0$ karena simpul $3$ dan $4$ tidak bertetangga.
- $e = a_{77} = 1$ karena simpul $e$ bertetangga dengan dirinya sendiri (memuat gelang).
Jadi, nilai dari $$\boxed{a+b+c+d+e=1+1+1+0+1=4}$$(Jawaban C)
Soal Nomor 4
Nilai $n$ sehingga graf siklus $C_n$ merupakan graf swakomplemen adalah $\cdots \cdot$
A. $5$ C. $8$ E. $15$
B. $6$ D. $10$
Misalkan $C_n$ merupakan graf siklus dengan $n$ simpul. Agar termasuk graf swakomplemen, harus ditunjukkan bahwa $C_n \cong \overline{C_n}$ dengan $\overline{C_n}$ merupakan graf komplemen dari $C_n.$
Salah satu cara untuk menunjukkan dua graf itu isomorfis adalah dengan menghitung banyak sisinya yang harus sama, yaitu $E(C_n) = E(\overline{C_n}).$
Gabungan dari $C_n$ dan $\overline{C_n}$ merupakan graf lengkap $K_n.$ Karena $C_n$ memiliki $n$ simpul, sedangkan $K_n$ memiliki $\displaystyle \binom{n}{2} = \dfrac12n(n-1),$ diperoleh
$$\begin{aligned} |E(C_n)| + |E(\overline{C_n})| & = |E(K_n)| \\ |E(C_n)| + |E(C_n)| & = |E(K_n)| \\ n + n & = \dfrac12n(n-1) \\ 4n & = n^2-n \\ n^2-5n & = 0 \\ n(n-5) & = 0.\end{aligned}$$Nilai $n$ yang memenuhi persamaan terakhir adalah $n = 0$ atau $n = 5.$ Karena $n$ menyatakan banyak simpul, nilainya tidak mungkin nol. Jadi, diperoleh $n = 5.$ Dengan kata lain, $C_5$ dan $\overline{C_5}$ merupakan satu-satunya pasangan graf yang komplemen satu sama lain dan memuat banyak sisi yang sama. Kemudian, dapat ditunjukkan bahwa $C_5$ dan $\overline{C_5}$ isomorfis seperti yang terlihat pada gambar berikut.
(Jawaban A)
Bagian Uraian
Soal Nomor 1
Gambarkan contoh dua graf sederhana, beraturan, memiliki $8$ simpul, dan $8$ sisi, tetapi tidak isomorfis.
Berikut diberikan contoh dua graf beraturan, memiliki $8$ simpul, dan $8$ sisi, tetapi tidak isomorfis.
Dua graf tersebut tidak memuat sisi rangkap maupun gelang sehingga tergolong graf sederhana, masing-masing memiliki $8$ simpul dan $8$ sisi. Setiap simpul dari masing-masing graf berderajat $2$ 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 $8,$ sedangkan graf kedua (kanan) tidak memuat siklus seperti itu.
Dari sini, disimpulkan bahwa dua graf tersebut isomorfis.
Soal Nomor 2
Periksa apakah dua graf berikut isomorfis atau tidak.
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 $\mathbb{F}$ merupakan fungsi yang mengaitkan simpul pada graf pertama dan kedua. Korespondensi satu-satu yang dimaksud adalah sebagai berikut.
$$\begin{array}{c} \hline \mathbb{F}(a) = 1 \\ \mathbb{F}(b) = 2 \\ \mathbb{F}(c) = 3 \\ \mathbb{F}(d) = 4 \\ \mathbb{F}(e) = 5 \\ \mathbb{F}(f) = 6 \\ \mathbb{F}(g) = 7 \\ \mathbb{F}(h) = 8 \\ \hline \end{array}$$Karena mengawetkan ketetanggaan, $\mathbb{F}$ 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.
Soal Nomor 3
Periksa apakah dua graf berikut isomorfis atau tidak.
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 $3$ dan bertetangga dengan tiga simpul berwarna biru yang masing-masing berderajat $3, 3,$ dan $2.$ Namun, tidak ada simpul berderajat $3$ di graf kedua yang bertetangga dengan tiga simpul berderajat $3, 3,$ dan $2.$ Dengan kata lain, korespondensi satu-satu tidak akan dapat dibentuk.
Dari sini, disimpulkan bahwa dua graf tersebut takisomorfis.
Soal Nomor 4
Periksa apakah dua graf berikut isomorfis atau tidak.
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 $3$ dan bertetangga dengan dua simpul berwarna biru yang masing-masing berderajat $3$ dan $2.$ Namun, tidak ada simpul berderajat $3$ di graf kedua yang bertetangga dengan dua simpul berderajat $3$ dan $2.$ Dengan kata lain, korespondensi satu-satu tidak akan dapat dibentuk.
Dari sini, disimpulkan bahwa dua graf tersebut takisomorfis.
Soal Nomor 5
Apakah pasangan graf sederhana dengan matriks ketertanggaan berikut isomorfis? Jelaskan.
- $\begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}$
- $\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0\end{pmatrix}, \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0\end{pmatrix}$
- $\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0\end{pmatrix}, \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}$
Jawaban a)
Dua graf dengan matriks ketertanggaan $\begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$ dan $\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}$ dapat digambarkan sebagai dua sisi segitiga. Masing-masing graf memuat tiga simpul dan dua sisi. Satu simpul berderajat $2,$ sedangkan dua simpul lainnya berderajat $1.$ Jadi, dua graf tersebut isomorfis.
Jawaban b)
Dua graf dengan matriks ketertanggaan $\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0\end{pmatrix}$ dan $\begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0\end{pmatrix}$ tidak isomorfis karena banyak sisinya berbeda. Untuk melihatnya, jumlahkan semua entri di atas atau di bawah diagonal utama matriks ketetanggannya. Graf pertama memiliki $4$ sisi, sedangkan graf kedua memiliki $5$ sisi.
Jawaban c)
Dua graf dengan matriks ketertanggaan $\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0\end{pmatrix}$ dan $ \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}$ tidak isomorfis karena banyak sisinya berbeda. Untuk melihatnya, jumlahkan semua entri di atas atau di bawah diagonal utama matriks ketetanggannya. Graf pertama memiliki $4$ sisi, sedangkan graf kedua memiliki $3$ sisi.
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.$
Misalkan $\phi: V(G) \to V(H)$ merupakan isomorfisme. Ambil sembarang simpul $v \in V(G)$ dan misalkan $\phi(v) = u \in V(H).$ Misalkan juga $v$ bertetangga dengan $w_1, w_2, \cdots, w_k$ dan tidak bertetangga dengan $x_1, x_2, \cdots, x_\ell.$ Dapat dilihat bahwa $|G| = k + \ell$ dan $\text{deg}_G(v) = k.$
Berdasarkan definisi isomorfisme, $u$ bertetangga dengan $\phi(w_1), \phi(w_2), \cdots, \phi(w_k)$ dan tidak bertetangga dengan $\phi(x_1), \phi(x_2), \cdots, \phi(x_\ell).$ Akibatnya, $\text{deg}_H(u) = k.$
Karena $v$ merupakan sembarang simpul di $G$ yang dipetakan oleh isomorfisme $\phi$ ke simpul $\phi(v) = u,$ disimpulkan bahwa derajat simpul-simpul di $G$ sama dengan derajat simpul-simpul di $H.$
Jadi, proposisi terbukti benar. $\blacksquare$
Soal Nomor 7
Misalkan $G$ dan $H$ merupakan graf sederhana. Buktikan bahwa $G$ dan $H$ isomorfis jika dan hanya jika komplemennya, $\overline{G}$ dan $\overline{H},$ juga isomorfis.
Misalkan $G$ dan $H$ merupakan graf sederhana.
Pertama, akan ditunjukkan bahwa jika $G$ dan $H$ isomorfis, maka $\overline{G}$ dan $\overline{H}$ juga isomorfis.
Misalkan $G = (V(G), E(G))$ dan $H = (V(H), E(H))$ isomorfis. Menurut definisi, terdapat isomorfisme $f: V(G) \to V(H).$ Ambil sembarang simpul $u, v \in V(G).$ Tanpa mengurangi keumuman, misalkan $\{u, v\} \notin E(G).$ Menurut definisi komplemen, $\{u, v\} \in E(\overline{G}).$ Karena $f$ merupakan isomorfisme dari $V(G)$ ke $V(H),$ diperoleh $\{f(u), f(v)\} \notin E(H).$ Menurut definisi komplemen, $\{f(u), f(v)\} \in E(\overline{H}).$
Karena $f$ merupakan isomorfisme dari $V(\overline{G})$ ke $V(\overline{H}),$ terbukti bahwa $\overline{G}$ dan $\overline{H}$ juga isomorfis.
Dengan cara yang serupa, akan ditunjukkan bahwa jika $\overline{G}$ dan $\overline{H}$ juga isomorfis, maka $G$ dan $H$ isomorfis.
Misalkan $\overline{G} = (V(\overline{G}), E(\overline{G}))$ dan $\overline{H} = (V(\overline{H}), E(\overline{H}))$ isomorfis. Menurut definisi, terdapat isomorfisme $f: V(\overline{G}) \to V(\overline{H}).$ Ambil sembarang simpul $u, v \in V(\overline{G}).$ Tanpa mengurangi keumuman, misalkan $\{u, v\} \notin E(\overline{G}).$ Menurut definisi komplemen, $\{u, v\} \in E(G).$ Karena $f$ merupakan isomorfisme dari $V(\overline{G})$ ke $V(\overline{H}),$ diperoleh $\{f(u), f(v)\} \notin E(\overline{H}).$ Menurut definisi komplemen, $\{f(u), f(v)\} \in E(H).$
Karena $f$ merupakan isomorfisme dari $V(G)$ ke $V(H),$ terbukti bahwa $G$ dan $H$ juga isomorfis.
Jadi, dapat disimpulkan bahwa proposisi terbukti benar secara keseluruhan. $\blacksquare$
Soal Nomor 8
Buktikan bahwa isomorfisme graf merupakan relasi ekuivalensi.
Untuk membuktikan bahwa isomorfisme graf merupakan relasi ekuivalensi, kita harus membuktikan bahwa isomorfisme graf merupakan relasi refleksif, simetris, dan transitif.
Misalkan $$\begin{aligned} G_1 & = (V(G_1), E(G_1)) \\ G_2 & = (V(G_2), E(G_2)) \\ G_3 & = (V(G_3), E(G_3)) \end{aligned}$$merupakan graf sederhana.
Relasi releksif:
Pemetaan identitas pada $V(G_1)$ merupakan bijeksi yang memetakan setiap simpul $G_1$ pada dirinya sendiri. Akibatnya, ketertanggaan diawetkan. Jadi, isomorfisme graf merupakan relasi refleksif.
Relasi simetris:
Misalkan $G_1$ isomorfis dengan $G_2.$ Akibatnya, ada suatu isomorfisme $\phi: V(G_1) \to V(G_2).$ Misalkan inversnya, $\phi^{-1}: V(G_2) \to V(G_1),$ didefinisikan oleh
$$\phi^{-1}(v_2) = v_1 \Leftrightarrow \phi(v_1) = v_2$$untuk setiap $v_1 \in V(G_1)$ dan $v_2 \in V(G_2).$
Karena invers dari bijeksi merupakan bijeksi, $\phi^{-1}$ merupakan bijeksi.
Misalkan $u_2, v_2 \in V(G_2)$ sehingga $\phi^{-1}(u_2) = u_1$ dan $\phi^{-1}(v_2) = v_1$ untuk suatu $u_1, u_2 \in V(G_1).$
Akibatnya,
$$\begin{aligned} \phi(u_1) & = u_2 \\ \phi(v_1) & = v_2. \end{aligned}$$Jadi, $u_2$ dan $v_2$ bertetangga jika dan hanya jika $\phi(u_1)$ dan $\phi(v_1)$ bertetangga.
Karena $G_1$ isomorfis dengan $G_2,$ $\phi(u_1)$ dan $\phi(u_2)$ bertetangga jika dan hanya jika $u_1 = \phi^{-1}(u_2)$ dan $v_1 = \phi^{-1}(v_2)$ bertetangga.
Ini berarti $u_2$ dan $v_2$ bertetangga jika dan hanya jika $u_1 = \phi^{-1}(u_2)$ dan $v_1 = \phi^{-1}(v_2)$ bertetangga.
Jadi, $G_2$ isomorfis dengan $G_1$ sehingga isomorfisme graf merupakan relasi simetris.
Relasi transitif:
Misalkan $G_1$ isomorfis dengan $G_2$ dan $G_2$ isomorfis dengan $G_3.$ Akibatnya, ada suatu isomorfisme
$$\begin{aligned} \alpha &: V(G_1) \to V(G_2) \\ \beta &: V(G_2) \to V(G_3). \end{aligned}$$Tinjau pemetaan komposisi $\beta \circ \alpha.$
Karena komposisi dari bijeksi juga bijeksi, $\beta \circ \alpha$ merupakan bijeksi dari $V(G_1)$ ke $V(G_3).$
Misalkan $u_1, v_1 \in V(G_1),$ $u_2, v_2 \in V(G_2),$ dan $u_3, v_3 \in V(G_3)$ serta
$$\begin{aligned} \alpha(u_1) = u_2~&\text{dan}~\alpha(v_1) = v_2 \\ \beta(u_2) = u_3~&\text{dan}~\beta(v_2) = v_3. \end{aligned}$$Karena $\alpha$ dan $\beta$ merupakan isomorfisme, didapat bahwa
$u_1$ dan $v_1$ bertetangga jika dan hanya jika $\alpha(u_1) = u_2$ dan $\alpha(v_1) = v_2$ bertetangga; dan
$u_2$ dan $v_2$ bertetangga jika dan hanya jika $\beta(u_2) = u_3$ dan $\beta(v_2) = v_3$ bertetangga.
Akibatnya,
$u_1$ dan $v_1$ bertetangga jika dan hanya jika $(\beta \circ \alpha)(u_1) = \beta(\alpha(u_1)) = u_3$ dan $(\beta \circ \alpha)(v_1) = \beta(\alpha(v_1)) = v_3$ bertetangga.
Jadi, $\beta \circ \alpha$ merupakan isomorfisme dari $V(G_1)$ ke $V(G_3)$ sehingga $G_1$ isomorfis dengan $G_3.$ Disimpulkan bahwa isomorfisme graf merupakan relasi transitif.
Karena isomorfisme graf merupakan relasi refleksif, simetris, dan transitif, disimpulkan bahwa isomorfisme graf merupakan relasi ekuivalensi. $\blacksquare$
Soal Nomor 9
Buktikan bahwa graf swakomplemen mempunyai simpul sebanyak $4k$ atau $4k+1$ untuk suatu bilangan bulat positif $k.$
Misalkan $G$ merupakan graf swakomplemen dengan $p$ sisi. Berdasarkan definisi isomorfisme, $\overline{G}$ juga memiliki $p$ sisi. Gabungan dari $G$ dan $\overline{G}$ adalah graf lengkap, yaitu graf yang setiap simpulnya saling bertetangga satu sama lain. Lebih lanjut, graf lengkap dengan $n$ simpul memiliki sisi sebanyak $\displaystyle \binom{n}{2} = \dfrac{n(n-1)}{2}.$ Dengan kata lain, $p + p = \dfrac{n(n-1)}{2}$ sehingga didapat $p = \dfrac{n(n-1)}{4}.$ Agar $p$ bulat, haruslah $4 \mid n$ atau $4 \mid (n-1).$ Dengan demikian, terdapat suatu bilangan bulat $k$ sehingga $n = 4k$ atau $n = 4k+1.$ Jadi, terbukti bahwa graf swakomplemen mempunyai simpul sebanyak $4k$ atau $4k+1$ untuk suatu bilangan bulat positif $k.$