Soal dan Pembahasan – Graf Isomorfik dan Subgraf (Graf Bagian)

Berikut ini adalah soal-soal beserta penyelesaiannya mengenai graf isomorfik dan subgraf (graf bagian). Semoga bermanfaat!

Today Quote

Bergebulah dan berapi-apilah di masa mudamu. Kobarkan semangat membara bak sang pahlawan. Masa muda adalah masa yang tidak boleh dilewatkan dengan malas-malasan.

Baca: Soal dan Pembahasan- Teori Dasar Graf

Baca: Istilah Lengkap dalam Teori Graf

Soal Nomor 1
Jika $G$ adalah graf yang diberikan seperti gambar di bawah ini, tentukan:

  1. Graf $G- U$ bila $U = \{x_1, x_3, x_5, x_7\}$;
  2. Graf $G- F$ bila $F = \{e_2, e_4, e_8, e_9, e_{10}, e_{12}\}$;
  3. $G[U]$, dengan $U = \{x_2, x_3, x_4, x_7\}$;
  4. $G[F]$, dengan $F = \{e_1, e_2, e_8, e_9, e_{11}\}$.

Pembahasan

Jawaban a)
Akan ditentukan gambar graf $G-U$ bila bila $U = \{x_1, x_3, x_5, x_7\}$.
Hapus titik $U = \{x_1, x_3, x_5, x_7\}$ pada graf $G$ beserta sisi yang bersisian dengannya sehingga diperoleh graf berikut.





Jawaban b)
Akan ditentukan gambar graf $G- F$ bila $F = \{e_2, e_4, e_8, e_9, e_{10}, e_{12}\}$. Hapus sisi $F = \{e_2, e_4, e_8, e_9, e_{10}, e_{12}\}$ pada graf $G$ sehingga diperoleh graf berikut.




Jawaban c)
Akan ditentukan gambar dari graf $G[U]$, dengan $U = \{x_2, x_3, x_4, x_7\}$.
Hapus semua titik pada graf $G$ kecuali $U = \{x_2, x_3, x_4, x_7\}$. Tambahkan dengan sisi pada graf $G$ yang titik ujungnya adalah anggota himpunan $U$ tersebut sehingga diperoleh graf berikut.


Jawaban d)
Akan ditentukan gambar dari graf $G[F]$, dengan $F = \{e_1, e_2, e_8, e_9, e_{11}\}$Hapus semua sisi pada graf $G$ terkecuali $F = \{e_1, e_2, e_8, e_9, e_{11}\}$. Tambahkan titik ujung sisi-sisi tersebut sehingga terbentuk graf berikut.


 

[collapse]

Soal Nomor 2
Benar atau salahkan pernyataan berikut? Jelaskan.

  1. Jika graf $G$ dan $H$ isomorfik, maka keduanya mempunyai banyak titik yang sama dan banyak sisi yang sama pula.
  2. Jika graf $G$ dan $H$ isomorfik, maka keduanya mempunyai barisan derajat yang sama.
  3. Jika $G$ dan $H$ graf sederhana dan mempunyai barisan derajat yang sama, maka keduanya isomorfik.

Pembahasan

Jawaban a)
Benar. Jika tidak demikian, maka fungsi yang terbentuk bukan bijektif (korespondensi satu-satu), padahal itu adalah syarat keisomorfikan graf. (ingat kembali bahwa syarat suatu fungsi dikatakan bijektif adalah banyaknya anggota domain sama dengan banyaknya anggota kodomain).
Jawaban b)
Benar. Ini merupakan syarat “melestarikan keterhubungan langsung” pada definisi graf isomorfik. Perlu ditekankan juga bahwa jika dua buah graf memiliki titik yang berderajat sama (graf beraturan), belum tentu kedua graf itu isomorfik, terkecuali graf itu adalah graf sederhana (simple graph).
Jawaban c) Salah.

Kedua graf ini sederhana dan memiliki barisan derajat yang sama, tetapi tidak isomorfik. Mengapa? Silakan baca penyelesaian soal nomor 4b.

[collapse]

Baca: Soal dan Pembahasan- Keterhubungan Graf

Soal Nomor 3
Gambarlah semua graf dengan empat titik berbeda terhadap isomorfiknya.

Pembahasan

Soal ini bersifat open-ended. Berikut ini disajikan graf beraturan-$2$, artinya graf yang setiap titiknya berderajat $2$, dengan empat titik berbeda beserta isomorfiknya yang mungkin.



Tampak bahwa graf $G$ isomorfik terhadap graf $H, I$, dan $J$ karena setiap titiknya berkorespondensi secara bijektif dan melestarikan keterhubungan langsung dengan titik pada graf yang dimaksud. Secara notasi ditulis: $G \cong H \cong I \cong J$.

[collapse]

Soal Nomor 4
Perhatikan graf berikut. Apakah dua graf tersebut isomorfik?
A.
B. 

Pembahasan

Jawaban a)
Isomorfik, karena masing-masing titik pada $G$ (dengan semua titik yang berderajat $3$) berkorespondensi satu-satu dan melestarikan keterhubungan langsung terhadap masing-masing titik pada $H$ (semua titiknya juga berderajat $3$).

Jawaban b)
Tidak isomorfik.


Perhatikanlah bahwa ketika kita menganggap bahwa titik $A$ berkorespondesi secara bijektif terhadaptitik  $D$, maka kita tidak akan bisa menemukan pemetaan bijektif pada $C$, karena baik $E$ maupun $F$ pada graf $H$ masing-masing hanya berderajat $2$, padahal $C$ berderajat $3$. 

[collapse]

Soal Nomor 5
Perhatikan graf $G$ yang direpresentasikan sebagai berikut.

Dari empat graf di bawah, tentukan graf yang merupakan:
a. graf bagian dari $G$;
b. graf bagian rentang dari $G$.

Pembahasan

Jawaban a)
$G_1$ dan $G_4$ merupakan subgraf (graf bagian) dari $G$, sedangkan $G_2$ bukan subgraf $G$ karena semua titiknya berderajat $3$, padahal titik/simpul di $G$ tidak semuanya berderajat $3$. $G_3$ bukan subgraf $G$ karena ada titik/simpul yang berderajat $4$, padahal graf $G$ tidak mengandung titik berderajat $4$.

Jawaban b)
Graf bagian merentang (subgraf merentang/spanning subgraph) dari $G$ adalah subgraf yang mengandung semua titik di $G$. Jelas bahwa $G_4$ adalah subgraf merentang dari $G$ karena mengandung $5$ titik seperti graf $G$.

[collapse]

Soal Nomor 6
Gambarkanlah dua graf yang tidak isomorfik, beraturan, serta memiliki $8$ sisi dan $8$ titik.

Pembahasan

Misalkan dua graf yang dimaksud diberi nama $G_1$ dan $G_2$. Kedua graf tersebut digambarkan sebagai berikut. 


Jelas bahwa kedua graf tersebut tidak isomorfik karena tidak ada satupun titik/simpul pada $G_1$ yang berkorespondensi secara bijektif pada titik/simpul di $G_2$ yang mengandung gelang (loop). Kedua graf di atas memiliki $8$ titik dan $8$ sisi, serta setiap titiknya berderajat $2$.
Catatan: Titik yang memiliki sisi loop dianggap memiliki derajat $2$, tetapi sisi loop itu hanya dihitung $1$.

[collapse]

Baca: Soal dan Pembahasan- Struktur Pohon dalam Teori Graf

Soal Nomor 7
Tunjukkan bahwa dua graf berikut tidak isomorfik.

Pembahasan

Beri label pada kedua graf tersebut seperti berikut.

Ketika kita memisalkan titik $A$ berkorespondensi dengan titik $b$, maka kita tak akan menemukan pasangan korespondensi titik $e$, sebab jelas titik $a$ dan titik $c$ (yang merupakan titik yang terhubung langsung/adjacent dengan $b$) pada graf $H$ tidak mengandung gelang. Ini berarti, syarat keisomorfikan sudah tidak terpenuhi. Dengan kata lain, kedua graf tersebut tidak isomorfik. Agar $H$ isomorfik dengan $G$, dua titik yang mengandung loop harus terhubung langsung (adjacent)

[collapse]

CategoriesTeori Graf, Matematika DiskritTags, , , , , , ,

Leave a Reply

Silakan beri tanggapan dan saran, tidak perlu sungkan. Mohon juga diinformasikan melalui kolom komentar ini bila ada kesalahan pengetikan sekecil apapun (typo atau bahasa latex yang error) atau kesalahan konsep dan pembahasan soal. Terima kasih. Ganbatte!

Your email address will not be published. Required fields are marked *