Definisi Graf dan Penerapanya di Dunia nyata

Otakcerdas.com - Halo kawan ocer ketemu lagi dengan saya, kali ini saya akan berbagi tentang Teori graf dan penerapanya. sebelum membahas lebih jauh tentang Graf. kita terlebih dahulu berkenalan dan paham dengan yang namanya Graf.

kalo kita tanya ke om Wikipedia kata dia seperti ini. "Dalam matematika dan ilmu komputer, sebuah graf adalah objek dasar pelajaran dalam teori graf. Dalam bahasa sehari-hari, sebuah graf adalah himpunan dari objek-objek yang dinamakan titik, simpul, atau sudut dihubungkan oleh penghubung yang dinamakan garis atau sisi.

Dalam graf yang memenuhi syarat, di mana biasanya tidak berarah, sebuah garis dari titik A ke titik B dianggap sama dengan garis dari titik B ke titik A. Dalam graf berarah, garis tersebut memiliki arah. Pada dasarnya, sebuah graf digambarkan dengan bentuk diagram sebagai himpunan dari titik-titik (sudut atau simpul) yang digabungkan dengan kurva (garis atau sisi)."

Penerapan graf di dunia nyata biasanya untuk perutean, atau di biasa di sebut Routing, seperti pencarian jalur tercepat menuju suatu kota. atau jika belum mudeng juga gini saja. kalian pasti tahu kan google maps, nah di situ akan ada tuh fitur untuk perjalanan namanya google Street.

Google navigation - http://www.androidcentral.com/

nah ketika kita menjalankan google street dan menetapkan kota tujuan kita, google akan mencari dan menghitung jalur mana saja yang bisa di lewati untuk menuju kota yang anda inginkan, nah setelah itu google akan memunculkan masukan kepada anda tentang jalur yang bisa di lewati lengkap dengan jarak dan waktu tempuh nya. nah itu lah penerapan Graf sekarang ini.

Gimana sudah paham atau belum ? kalau belum bersyukurlah artinya kamu masih berfikir, oke kita lanjut dengan pemahaman tentang Graf. Graf di definisikan sebagai pasangan Himpunan dari (V, E). biasanya di tulis dengan notasi G = (V, E). yang dalam hal ini arti dari simbol itu adalah.

• V = himpunan tidak kosong dari simpul-simpul (vertices) = { v1, v2, ...., vn }.
• E = himpunan sisi (edges) yang menghubungkan sepasang simpul = { e1, e2,.., en }

Initnya kita bisa menyebut simpul dengan Vertecs dan sisi dengan sebutan Edge. dan dari hasil pengertian di atas kesimpulanya adalah V atau simpul tidak boleh kosong sedangkan E boleh kosong. artinya adalah Sebuah Graf di mungkinkan tidak mempunyai sisi satu buah pun, tapi simpulnya harus ada minimal satu. kalau tidak ada simpul satu buah pun itu tidak bisa kita sebuh sebagai Graf.

Nah selanjutnya adalah cara penomoran pada sebuh Graf, yang dalam hal ini adalah penomoran pada Simpul dan Sisi. 

jika anda ingin menomori pada simpul anda bisa menggunakan kode seperti menggunakan huruf, bilangan atau campuran huruf dan bilangan.

• Huruf (a, b, c, ...,z) atau
• Bilangan (1, 2, 3, ...) atau
• Huruf dan Bilangan (a1, a2, a3, ....)

Selanjutnya kita ke cara menghubungkan dua buah simpul, yang menghubungkan dua buah simpul di sebut dengan sisi, misalkan, sisi yang menghubungkan simpul u dan simpul v di nyatakan dengan pasangan (u,v) atau di nyatakan dengan e1, e2.. sehingga dapat di tulis : e = (u, v). ingat kita bisa menggunakan huruf, bilangan maupun campuran huruf dan bilangan.

"Yang ingin belajar lewat Modul, Silahkan di unduh di Download"

Sisi yang berawal dan berakhir pada simpul yang sama di sebut dengan gelang atau kalang dan bahasa kerenya adalah loop. untuk lebih jelasnya lihat gambar di bawah ini.

Loop pada Graf

Sedangkan jika ada dua buah simpul yang di hubungkan oleh dua atau lebih sisi di sebut dengan sisi granda/sisi paralel (multiple edges/paralel edges). lihat gambar di bawah ini, dan perhatikan yang di lingkari merah. itulah yang kita sebut sebagai sisi ganda, artinya ada 2 buah garis yang menghubungkan dua buah titik atau simpul.

Sisi ganda / Multiple Egde

Itulah sedikit definisi dari Graf dan beberapa penjelasan tentang atribut graf. semoga bisa bermanfaat, apabila ada sesuatu hal yang masih bingung dengan materi ini anda bisa tinggalkan pertanyaan di kolom komentar di bawah ini. okeh, selamat belajar !