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

Video ini membahas tentang konsep simpul bertetangga, simpul terminal, derajat masuk, derajat keluar, dan terminologi graf dalam Matematika Diskrit. Konsep ber-tetangga atau adjacent digunakan untuk menggambarkan hubungan antar simpul dalam graf berarah. Derajat masuk dan derajat keluar digunakan untuk mengukur jumlah busur masuk dan keluar dari suatu simpul dalam graf berarah. Terdapat istilah-istilah seperti simple graph, multigraph, dan pseudograph yang digunakan untuk mengklasifikasikan jenis-jenis graf berdasarkan sifatnya. Graph digunakan untuk memodelkan situasi tertentu, seperti pertemanan antara individu, di mana derajat simpul dapat menggambarkan seberapa banyak individu tersebut dikenal dalam kelompok tertentu.

Kalau kita mengenal tetangga waktu di graf yang tak berarah,

di sini kita juga kenal tetangga, istilah ber-tetangga atau adjacent.

Tapi kalau kita punya busur berarah X, Y maka simpul X disebut ber-tetangga ke Y atau pada Y.

Jadi kita tidak cuma ngomong X dan Y ber-tetangga, tapi harus X-nya ber-tetangga ke mana.

Karena belum tentu ada busur berarah dari Y ke X, jadi di sini kalau ada busur dari X ke Y

berarti kita bilang X ber-tetangga pada Y dan Y-nya disebut ber-tetangga dari,

jadi ada arahnya dari atau ke-nya ke mana.

X-nya itu kita sebut sebagai simpul awal dari busur berarah X, Y

dan Y-nya kita sebut sebagai simpul terminal.

Jadi ada simpul awalnya, ada simpul terminal.

Kalau yang di graf tak berarah itu tidak dibedakan antara simpulnya itu awal atau terminal,

tapi kita cuma bilang itu simpul ujung atau titik ujung.

Karena si V ini misalnya dia punya dua busur keluar kemudian satu busur ke dalam,

maka kita tidak bisa mengatakan derajatnya tiga.

Tapi ini dipisahkan derajat ke dalam atau derajat masuk dan derajat keluar.

Di sini istilah Inggrisnya in-degree atau out-degree.

Jadi kita lihat di sini derajat masuknya itu dinotasikan dengan D-V,

pada contoh kita itu satu, kemudian derajat keluarnya itu D-V,

itu kita kasih nilai dua di sini karena memang ada busur yang keluar, jadi dari V.

Jadi bedanya itu kita membedakan antara in-degree sama out-degree.

Jadi kalau kita lihat contohnya di sini, ini ada graf berarah,

ada yang tadi simpul terisolasi itu sama in-degree sama out-degree,

atau derajat ke dalam dan derajat keluarnya itu sama dengan nol.

Jadi untuk F, D-F nya itu sama dengan D plus F, itu sama dengan nol.

Untuk simpul A kita lihat di sini ada loop, berarti kalau loop itu dihitung satu keluar, satu ke dalam.

Kemudian dari A ke E itu ada satu keluar, satu ke dalam,

berarti di sini kita sudah punya masing-masing dua,

tapi kita punya juga kaitan A dengan B itu yang keluar dan yang A ke C itu juga keluar,

sehingga degree keluarnya atau derajat keluarnya itu empat.

Jadi yang pertama adalah dari loopnya, yang kedua dari A ke E,

yang ketiga A ke B, dan yang keempat dari A ke C.

Derajat masuknya itu cuma dua, yang satu berasal dari loop, yang satu lagi berasal dari E.

Nanti kita bisa hitung untuk derajat keluarnya B itu satu, derajat masuknya B itu dua,

derajat keluarnya C itu dua, derajat masuknya dua, dan seterusnya.

Bisa dilihat ada berapa yang keluar, ada berapa yang masuk.

Jadi di sini ada istilah-istilah dalam graph.

Kalau graphnya sederhana, itu biasanya digunakan untuk graph yang tak berarah.

Dan apakah ada busur berganda? Tidak ada.

Multigraph itu kalau dia punya busur ganda, tapi tidak punya loop.

Dan busur gandanya tidak untuk setiap pasang simpul.

Jadi yang penting kalau misalnya graphnya itu ada sepasang simpul yang punya busur yang lebih dari satu

yang menghubungkan mereka, itu kita sebut sebagai busur ganda.

Kalau pseudograph itu tadi adalah kalau dia mempunyai loop dan boleh juga mempunyai busur ganda.

Kemudian kalau graphnya berarah, itu juga bisa disebut sederhana sama kalau dia tidak punya busur ganda dan tidak punya loopnya.

Kemudian mixed graph, mixed graph ini adalah graph yang ada busur yang tak berarah, ada busur yang berarah.

Jadi kalau tadi misalnya dari titik A ke titik B, dalam contoh sebelumnya,

itu kita boleh dari A ke B, boleh dari B ke A.

Biasanya ada beberapa yang menuliskan ini menjadi satu busur yang tidak ada arahnya.

Kalau di B ke C misalnya, itu hanya ada satu arah, jadi tidak ada dari titik C ke B.

Berarti kan di sini ada busur yang direpresentasikan sebagai busur tak berarah, ada yang berarah.

Makanya itu kita sebut sebagai mixed graph.

Tapi untuk selanjutnya kita tidak bahas untuk ini.

Nah sekarang graph itu seperti awal ditemukannya dapat digunakan untuk memodelkan situasi tertentu.

Misalnya graph pertemanan, misalnya di sini ada delapan orang.

Di sini ada Gina, Rina, Adi, Dika, Ina, Eki, Nada dan Tia.

Nah kalau pertemanan, kalau Gina itu kenal sama Rina, Rina itu pasti kenal sama Gina kan.

Jadi representasinya di sini yang digunakan adalah graph yang tak berarah.

Kalau sekelompok ini Gina itu kenal berapa orang, kita lihat derajatnya di sini.

Derajatnya Gina itu di sini lima, berarti dia kenal lima di antara delapan orang yang disebutkan namanya di sini.