Soal Latihan dan Pembahasan – Graf Isomorfik dan Subgraf (Upagraf)


Berikut ini adalah soal-soal beserta penyelesaiannya mengenai graf isomorfik dan subgraf. Tentunya, Anda diharapkan sudah menguasai materi graf dasar terlebih dahulu. Selain itu, Anda juga diharapkan mengenal istilah dalam grafBagi Anda yang ingin mempelajari kosa kata atau istilah graf, silakan klik sini

Soal Nomor 1
Jika G adalah graf yang diberikan seperti gambar di bawah ini, tentukan
a) Graf G – U, bila U = \{x_1, x_3, x_5, x_7\}
b) Graf G – F, bila F = \{e_2, e_4, e_6, e_8, e_{10}, e_{12}\}
c) G[U], dengan U = \{x_2, x_3, x_4, x_7\}
d) G[F], dengan F = \{e_1, e_2, e_8, e_{11}\}

Penyelesaian

(Jawaban a) 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) Hapus sisi F = \{e_2, e_4, e_6, e_8, e_{10}, e_{12}\} pada graf G sehingga diperoleh graf berikut.

 

(Jawaban c) Hapus semua titik pada graf G terkecuali U = \{x_2, x_3, x_4, x_7\}. Tambahkan dengan sisi pada graf G yang titik ujungnya adalah anggota himpunan titik U, sehingga diperoleh graf berikut.

(Jawaban d) Hapus semua sisi pada graf G terkecuali F = \{e_1, e_2, e_8, e_{11}\}. Tambahkan titik ujung sisi tersebut sehingga terbentuk graf berikut.

[collapse]

Soal Nomor 2
Benar atau salahkan pernyataan berikut? Jelaskan.
a) Jika graf G dan H isomorfik, maka keduanya mempunyai banyak titik yang sama dan banyak sisi yang sama pula.
b) Jika graf G dan H isomorfik, maka keduanya mempunyai barisan derajat yang sama.
c) Jika G dan H graf sederhana dan mempunyai barisan derajat yang sama, maka keduanya isomorfik.

Penyelesaian

(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]


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

Penyelesaian

Soal ini bersifat open-ended. Berikut ini disajikan graf beraturan-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. 

Penyelesaian

(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 A berkorespondesi secara bijektif terhadap D, maka kita tidak akan bisa menemukan pemetaan bijektif pada C, karena baik E dan F pada graf H masing-masing hanya berderajat 2. 

[collapse]

Soal Nomor 5
Perhatikan graf G yang direpresentasikan sebagai berikut.

Tentukan graf yang merupakan
a) graf bagian dari G
b) graf bagian rentang dari G

Penyelesaian


(Jawaban a) G_1 dan G_4 merupakan subgraf (graf bagian) dari G. G_2 bukan subgraf G karena semua titiknya berderajat 3, padahal titik/simpul di G tidak semuanya berderajat 3. Sedangkan, 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, G_4 adalah subgraf merentang dari G karena mengandung 5 titik, seperti graf G.

[collapse]


Soal Nomor 6
Perhatikan graf pada soal nomor 1.
a. Gambarkan graf G[U] \cup G[F]
b. Gambarkan graf G[U] \cap G[F]

Penyelesaian

Berikut ini adalah video penjelasan untuk soal nomor 6 di atas.

[collapse]

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

Penyelesaian

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)

[collapse]


Soal Nomor 8
Misal G_1 dan G_2 adalah graf. Didefinisikan produk kartesius G = G_1 \times G_2 sebagai berikut.
V(G) = V(G_1) \times V(G_2), dengan dua buah titik (u_1, u_2) dan (v_1, v_2) di G terhubung langsung (adjacent) jika dan hanya jika
u_1 = v_1 dan u_2v_2 \in E(G_2) atau
u_2 = v_2 dan u_1v_1 \in E(G_1)
Tentukan graf G.

Penyelesaian Belum Tersedia
[collapse]


Soal Nomor 9
Tunjukkan bahwa dua graf berikut tidak isomorfik.

Penyelesaian

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]

Ayo Beri Rating Postingan Ini

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *