Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas operasi graf hasil kali kartesian dan produk corona. Hasil kali kartesian dari dua graf, G dan H, menghasilkan graf dengan simpul-simpul berpasangan UV, dimana U adalah anggota dari VG dan V adalah anggota dari VH. Sedangkan produk corona melibatkan penggandaan graf G2 sebanyak elemen di G1, menghasilkan graf dengan lingkaran dan simpul. Contoh penerapan kedua operasi ini dijelaskan dengan detail dalam video, termasuk pembentukan graf tangga dan graf corona. Operasi-operasi lainnya seperti graf roda, bintang, prisma, dan lainnya juga dapat dilakukan namun tidak dibahas secara mendalam dalam video ini.

Operasi yang berikutnya kita sebut sebagai hasil kali kartesian.

Hasil kali kartesian dari dua graf misalnya di sini grafnya G dan H itu kita tuliskan dalam bentuk G x H atau G x H.

Dia adalah suatu graf yang himpunan simpulnya merupakan kartesian produk atau hasil kali kartesian dari himpunan simpul G dengan himpunan simpul H.

Sehingga nanti simpulnya diberi notasi sebagai pasangan terurut UV dimana U nya anggota VG dan V nya anggota VH.

Dua simpul UV dan U aksen V aksen itu akan bertetangga jika dan hanya jika aturannya adalah

kalau U nya sama dengan U aksen kemudian V nya itu bertetangga dengan V aksen di graf H.

Sedangkan kalau V nya sama dengan V aksen maka U nya itu harus bertetangga dengan U aksen di graf G.

Kita lihat contohnya ya di sini misalnya saya ambil P2 x P3 jadi kita melakukan operasi dari graf P2 dengan graf P3.

Kita punya graf P2 seperti ini misalnya saya kasih nama U1 U2 simpulnya kemudian kita punya P3.

Ini V1 V2 V3 gitu ya terus kita akan buat himpunan simpulnya dulu

berarti kita melakukan hasil kali kartesian antara himpunan V dari P2 dengan V P3.

Nanti kita akan punya pasangan terurut U1 dengan V1 U1 dengan V2 U1 dengan V3.

Berikutnya lagi U2 nya nanti kita punya U2 dengan V1 U2 dengan V2 U2 dengan V3.

Nah ini adalah apa namanya elemen-elemen atau simpul-simpul pada G.

Kalau ini simpul kita kasih notasi dengan titik kemudian kita mau ngecek apakah ada busur di antara simpul-simpul ini.

Caranya adalah kita lihat untuk yang pertama yang di baris atas saya tulis ini semua elemen pertamanya adalah U1.

Jadi sama semua ya kita tinggal melihat elemen keduanya mereka saling bertetangga enggak di P3.

Jadi kita lihat di sini antara V1 dengan V2 itu bertetangga enggak di graf yang kedua yaitu P3.

Nah ini karena di sini bertetangga maka kita punya busur antar mereka.

Begitu juga V2 dengan V3 itu bertetangga berarti di sini ada busur.

V1 dengan V3 tidak bertetangga berarti antara U1 V1 dengan U1 V3 juga tidak ada busurnya.

Hal yang sama kita bisa lihat di bagian yang saya tulis di bawahnya.

Ini U2 nya sama semua jadi kasusnya sama yang di atas.

Sekarang kita lihat yang berikutnya adalah yang elemen keduanya sama.

Di sini V1 yang ini sama-sama V2 ini sama-sama V3.

Maka untuk menentukan ada busur atau tidak di antara mereka kita melihat elemen pertamanya.

Jadi misalnya di sini elemen pertamanya U1 U2 itu ada enggak di graf aslinya.

Di sini U1 U2 itu bertetangga berarti di sini nanti kita juga akan punya busur yang menghubungkan kedua simbol tersebut.

Ini adalah hasil dari P2 cross P3 kita sebut graf yang seperti ini adalah graf tangga.

Operasi yang terakhir yang kita bahas sebetulnya banyak sekali operasi yang bisa kita lakukan pada dua graf.

Tapi operasi yang ini adalah operasi yang kita sebut sebagai produk corona.

Kita kasih notasinya G1 G2 terus di dalamnya ada lingkaran ada titiknya.

Ada notasi yang berbeda untuk beberapa sumber yang berbeda juga.

Caranya adalah kita meletakkan satu kopi graf G1 kemudian graf G2 digandakan sebanyak elemen di G1.

Di sini banyaknya elemen atau order dari G1 itu P1.

Jadi kalau saya mau bikin C3 kemudian di corona dengan P2.

Yang saya lakukan adalah saya gambar dulu C3 satu kopi dari C3.

Kemudian saya bikin kopi P2 sebanyak tiga kali karena di C3 ini ada tiga.

Jadi di sini yang pertama ini yang kedua P2 ini yang ketiga.

Langkah berikutnya kita menghubungkan simpul-simpul yang di graf pertama di C3 ke simpul yang tadi di kopinya.

Jadi kalau kita lihat di sini kan ini P2 kopi yang pertama jadi kita bikin mereka bertetangga.

Untuk yang kedua juga dia bertetangga ini juga bertetangga.

Kalau misalnya saya bikin C3 corona dengan K1 komplement artinya ini simpul yang terisolasi.

Terus kita kopi si K1 penamanya simpul terisolasi sebanyak tiga kali.

Kalau kita punya K2 di sini artinya dua simpul ya.

Kalau gambar lingkarannya itu kita buat sebagai lingkaran nanti kita akan dapat bentuk seperti ini.

Misalnya di lingkaran C4 kita punya ada Kr kita punya misalnya kalau Rnya tiga ini nanti bentuk coronanya adalah seperti ini.

Masih ingat waktu TK ya gambar matahari ini kenapa namanya itu adalah corona.

Nah ini adalah contoh beberapa graf yang bisa dituliskan dalam atau sebagai hasil operasi pada graf.

Ini grafnya kita sebut sebagai graf roda kalau masih ingat.

Ini graf bintang, ini graf prisma, ini corona antara lingkaran 4 dengan satu simpul dan seterusnya.

Ini ada beberapa operasinya yang tidak kita bahas pada diskusi kali ini.