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

Video ini membahas Teorema 2 dalam Teori Graf yang menyatakan setiap graf tak berarah memiliki jumlah simpul genap yang berderajat ganjil. Teorema ini dijelaskan dengan pembagian simpul-simpul ke dalam himpunan berderajat genap dan ganjil serta penerapan Handshaking Theorem untuk membuktikan bahwa jumlah derajat simpul harus genap. Selain itu, video juga menjelaskan jenis-jenis graf yang sering digunakan, seperti graf lintasan (Pn), graf lingkaran (Cn), graf teratur, graf lengkap (KN), dan graf roda (WN) dengan contoh penggambaran dan definisi masing-masing graf. Konsep isomorfisma juga disinggung dalam video untuk menjelaskan bahwa meskipun gambarannya berbeda, graf yang sama tetap dapat diidentifikasi.

Kalau kita lihat derajat dari suatu simpul, ada suatu sifat yang menarik yang dituliskan dalam teorema 2 disini,

yaitu setiap graf tak berarah itu mempunyai sejumlah genap simpul yang berderajat ganjil.

Jadi kalau kita punya ada beberapa simpul berderajat ganjil, maka banyaknya simpul itu pasti genap.

Misalkan kita bagi 2, V1 itu adalah himpunan-himpunan simpul di dalam graf tersebut yang berderajat genap.

Jadi derajatnya 2, 4, 8 dan seterusnya dan yang V2 itu yang derajatnya ganjil.

Kemudian dari handshaking teorem itu kita tahu bahwa 2M, 2 kali banyaknya busur itu akan sama dengan jumlahan semua derajat-derajat simpulnya.

Nah jumlahan derajat simpul itu kita pecah untuk yang himpunan simpul yang berderajat genap sama berderajat ganjil.

Jadi kita punya disini jumlahan untuk yang anggota V1, yang ini jumlahan untuk anggota V2.

Nah sekarang jumlahan ini selalu sama dengan 2M berarti kan harus genap.

Kalau kita lihat V1 karena di V1 degrinya itu atau derajatnya genap di jumlahkan berapapun pasti hasilnya genap.

Sehingga jumlahan yang untuk sigma dari degri V atau derajat V yang Vnya anggota V2 dimana V2 adalah himpunan simpul yang derajatnya ganjil itu harus bernilai genap.

Sehingga dengan demikian karena degri Vnya atau derajatnya ganjil jumlahannya harus bersifat genap untuk mendapatkan nilai ini adalah nilai yang genap.

Jadi disini kita bisa menyimpulkan bahwa simpul yang berderajat ganjil itu harus berjumlah genap,

Ini karena kita punya sigma dari derajat V, Vnya itu anggota V2 dimana setiap V ini derajatnya ganjil.

Jadi masing-masing ini berupa nilai ganjil.

Kalau ini jumlahannya mau bernilai genap maka banyaknya si Vnya itu harus genap.

Karena kita tahu bahwa graf tadi bisa merepresentasikan bentuk-bentuk tertentu atau modal-modal dari masalah tertentu,

kadang ada beberapa graf yang sering muncul atau sering digunakan sehingga ada jenis-jenis graf yang sering kita pakai.

Contoh yang pertama adalah graf lintasan.

Graf lintasan ini adalah graf yang mempunyai n simpul dan mempunyai n simpul ini dinotasikan sebagai V1, V2, V3, V4 sampai Vn

dan dia mempunyai busur V1, V2, V2, V3, V3, V4 dan seterusnya sampai Vn-1, Vn jadi berurut.

Jadi kita lihat di sini kalau nnya atau banyaknya simpul tiga jadi namanya P3.

Kita punya tiga simpul V1, V2, V3 busurnya adalah V1, V2, V2, V3 jadi gambarnya adalah lintasannya seperti ini.

Kalau P4 berarti dia punya empat simpul V1, V2, V3 sampai V4 dan busurnya adalah V1, V2, V2, V3 dan V3, V4.

Begitu juga kita lihat contoh yang P5 ini.

Jadi memang bentuknya seperti lintasan makanya kita sebut sebagai graf lintasan.

Graf yang kedua adalah graf yang kita sebut sebagai graf lingkaran.

Graf lingkaran itu ada beberapa definisi, salah satu definisinya di sini adalah graf yang diperoleh dari lintasan Pn tadi.

Jadi punya n simpul kemudian ditambahkan satu busur antara simpul awal yang tadi kita sebut sebagai V1 dengan simpul akhir yang Vn.

Jadi kalau kita misalnya lihat P4 berarti P4 itu lintasan yang punya simpul 4.

Kemudian kita tambahkan simpul dari V1 ke V4 ini kita sebut sebagai graf lingkaran.

Karena dia bisa digambarkan seperti lingkaran.

Kita lihat di sini contoh dari lingkaran C3, C4, C5, C6 itu bisa digambarkan dalam bentuk lingkaran.

Tapi ini tidak harus digambar sebagai lingkaran.

Jadi saya boleh misalnya punya C4 gitu ya, gambarnya tidak dalam bentuk lingkaran tapi bentuknya seperti ini.

Itu tidak masalah, ini tetap kita sebut sebagai graf lingkaran.

Nanti kita akan mengenal apa yang disebut sebagai isomorfisma.

Dan kalau kita lihat derajatnya, semua simpul di sini derajatnya 2.

Mau di C6 juga sama, dia derajatnya 2 semua di sini.

Sehingga kita bisa bilang kalau derajatnya sama semua itu kita sebut sebagai graf teratur.

Jadi graf lingkaran merupakan graf teratur yang berajat 2.

Karena graf lengkap dengan notasi KN, dia punya N simpul adalah graf sederhana

yang mempunyai tepat satu busur antara pasangan simpul yang berbeda.

Jadi lengkap itu dalam arti kalau kita ambil sembarang pasangan simpul itu pasti ada busurnya.

Kalau kita lihat misalnya contohnya di sini K3, ada 3 simpul itu mereka saling terhubung satu dengan yang lain.

Jadi kalau di sini saya kasih nama V1, V2, V3 maka V1 terhubung dengan V2, V2 terhubung dengan V3

atau kita sebut sebagai V1 bertetangga dengan V2, V1 bertetangga dengan V3 dan V2 bertetangga dengan V3 juga.

Kalau misalnya K5, berarti kita punya V1, V2, V3, V4, V5 setiap pasang simpul di situ bertetangga.

Itu yang kita sebut sebagai graf lengkap, jadi lengkap semuanya itu terhubung.

Graf yang berikutnya lagi adalah graf roda.

Kalau di graf ini namanya bisa lucu-lucu ya, tergantung pada yang pertama kali menemukan atau memodelkan graf itu ingetnya itu apa.

Jadi kalau graf roda ini, kenapa disebut sebagai graf roda itu karena dia bisa digambarkan dalam bentuk dia lingkaran terus tengahnya ada simpul.

Kalau di sini misalnya ada 5 simpul yang lingkarannya, nanti dia akan dihubungkan ke simpul yang di tengah ini yang disebut pusat.

Nah ini kan seperti roda ya, jadi kita kasih nama graf roda tapi nanti digambarkannya tidak harus bentuk lingkaran seperti ini.

Tapi bisa kita lihat di sini graf roda dengan 3 simpul, 4 simpul, 5 simpul, 6 simpul itu boleh digambarkan dalam bentuk yang agak berbeda.

Kalau definisinya, notasinya WN ya, itu adalah graf roda itu diperoleh dengan cara menambahkan 1 simpul pada lingkaran CN

dan menghubungkan si simpul baru ini, ini simpul yang ditambahkan dengan semua dihubungkan dengan busur untuk ke semua simpul-simpul yang ada di lingkaran.

Jadi menambahkan busur baru, tadinya bentuknya kalau lingkarannya aslinya itu seperti ini, kemudian ditambahkan 1,

habis itu kita tambahkan busur-busur yang menghubungkan si simpul baru ini dengan simpul-simpul yang ada.