Materi Lengkap menguji 2 buah graf Isomorifik

Materi Lengkap menguji 2 buah graf Isomorifik

Materi Lengkap menguji 2 buah graf Isomorifik – Menguji 2 buah graf isomorfik merupakan materi penting yang harus dikuasai oleh sobat beautymatika. Seperti yang pernah mimin tuliskan sebelumnya bahwa materi graf ini sebenarnya didapatkan pada saat kuliah, materi metode diskrit. 

Untuk sobat beautymatika yang masih di bangku SMA, janganlah mengganggap materi ini sulit. Sebenarnya materi ini cukup mudah untuk dipelajari, bahkan oleh anak SMA sekalipun. Bagi sobat beautymatika yang ketinggalan materi tentang graf dapat mempelajarinya disini.

Tanpa berlama-lama lagi mimin mengajak sobat beautymatika untuk mempelajari materi Lengkap menguji 2 buah graf Isomorifik :

Daftar isi

1. Pengertian graf isormofik
2. Teknik 1: Pembuktian graf ismorfik secara sederhana
3. Teknik 2: Pembuktian graf isomorfik menggunakan matriks
4. Teknik 1 atau Teknik 2 ?
5. Penutup

Pengertian graf isormofik

Graf isomorfik secara sederhana didefinisikan sebagai kondisi 2 buah graf sama namun secara geometri berbeda. Ini berarti bahwa 2 buah graf yang sama belum dapat dikatakan sama apabila belum dibuktikan kesamaannya melalui geometri. Intinya adalah sobat beautymatika perlu membuktikan secara geometri sebelum mengatakan 2 buah graf adalah isomorfik.

Teknik 1: Pembuktian graf ismorfik secara sederhana

Seperti yang mimin katakana sebelumnya bahwa diperlukan pembuktian secara geometri pada 2 buah graf isomorfik. 2 buah graf dapat dikatakan isomorfik jika memenuhi 3 syarat berikut :

1.     Kedua graf harus memiliki jumlah simpul yang sama

2.     Kedua graf harus memiliki jumlah garis hubung yang sama

3.     Kedua graf harus memiliki derajat dari simpul-simpulnya yang sama

Untuk lebih memahami sobat beautymatika dapat melihat contoh pembuktian 2 buah graf isomorfik yang menggunakan pembuktian graf isimorfik sederhana berikut :

Graf 1

Graf 2

Terlihat bahwa kedua graf diatas adalah isomorfik karena :

1.     Kedua graf memiliki jumlah simpul yang sama, yaitu sebanyak 5

2.     Kedua graf memiliki jumlah garis hubung yang sama, yaitu sebanyak 6

3.     Kedua graf memiliki derajat simpul yang sama, yaitu 3 dan 1. 3 disini berarti terdapat 4 (A, B, C, dan D) simpul pada kedua graf yang berderajat 3 dan 1 (E) simpul dari kedua graf yang berderajat 1.

Secara sederhana sobat beautymatika dapat membuktikan 2 buah graf isomorifik dengan cara seperti ini. Namun perlu sobat beautymatika ketahui bahwa cara sederhana (teknik 1) ini tidak dapat membuktikan secara tegas 2 buah graf isomorfik atau tidak. Oleh karena itu untuk membuktikan secara tegas 2 buah graf isomorfik atau tidak, dapat menggunakan cara yang lebih baik yaitu membuat nilai matriks dari kedua graf.

Teknik 2: Pembuktian graf isomorfik menggunakan matriks

Cara ini merupakan cara kedua dan yang paling aman dan tegas dalam membuktikan 2 buah graf isomorfik atau tidak. Pembuktian hanya perlu dilakukan dengan cara membuat nilai matriks dari kedua graf yang ada. Setelah nilai matriks masing-masing graf ditemukan, sobat beautymatika hanya perlu melihat apakah urutan susunan pola nilai matriks pada kedua graf sama atau tidak. Jika sama maka kedua graf tersebut adalah isomorfik. Jika tidak sama atau ada perbedaan pola, maka kedua graf tersebut tidaklah isomorfik.

Untuk lebih memahami pembuktian graf isomorfik menggunakan matriks, sobat beautymatika dapat melihat contoh berikut :

Graf 1

Nilai matriks graf 1 adalah :

Nilai matriks graf 1

Nilai matriks graf 2 adalah :

Graf 2

Nilai matriks graf 2

Sobat beautymatika dapat melihat bahwa pola nilai matrik graf 1 dan 2 adalah sama. Oleh karena itu graf 1 dan 2 adalah isomorfik.

Jadi, menguji 2 buah graf isomorfik menggunakan teknik 1 atau 2 ?

Mimin sendiri lebih menyarankan kepada sobat beautymatika untuk mengecek 2 buah graf isomorfik atau tidak dengan menggunakan teknik yang kedua, yaitu membuat nilai matriks dari masing-masing graf. Namun ini bukan berarti sobat beautymatika melupakan teknik 1 pembuktian graf ismorfik sederhana 

Untuk lebih tepat dalam menguji  2 buah graf isomorfik atau tidak, sobat beautymatika dapat mengikuti langkah-langkah berikut :

1.     Menguji sifat isomorfik 2 buah graf dengan teknik 1

Ini dilakukan untuk mengetahui secara kasar apakah 2 buah graf isomorfik atau tidak. Jika hasil pengerjaan 2 buah graf dengan teknik ini dinyatakan isomorfik, maka sobat beautymatika dapat lanjut ke teknik 2. Namun jika hasil pengerjaan 2 buah graf dengan teknik ini dinyatakan tidak isomorfik, maka 2 buah graf tersebut sudah dapat dipastikan tidak isomorfik.

2.     Menguji sifat isomorfik 2 buah graf dengan teknik 2

Ini hanya dapat dilakukan untuk menunjukan akan ketegasan 2 buah graf isomorfik. Ini hanya dilakukan jika 2 buah graf dinyatakan isomorfik melalui teknik 1. Teknik 2 ini diperlukan karena terkadang ada 2 buah graf dinyatakan isomorfik dengan teknik 1 namun tidak isomofik dengan teknik 2. Jika keadaanya seperti ini, maka kesimpulan tetap ada di teknik 2, yaitu menggunakan nilai matriks masing-masing graf.

Penutup

Demikian materi singkat mengenai materi lengkap menguji 2 buah graf isomorfik, Mimin yakin sobat beautymatika mampu menguasai materi ini dengan baik. Tetap semangat belajar dan sampai jumpa di materi lainnya.

 

 

Bagikan Artikel ini