Graf Terapan: Pengertian, Sejarah Graf, Penererapan dan Penjelasannya

Pengertian Graf

Graf adalah sekumpulan objek terstruktur di mana beberapa pasangan objek mempunyai hubungan ataupun keterkaitan tertentu, 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.

Graf terdiri dari 2 komponen yaitu :

1. Vertex/simpul/node/vertice

2. Edge/sisi/busur/arc

Sejarah Graf

Sejarah teori graph berawal pada tahun 1736  saat ahli matematika Swiss Leonhard Euler memecahkan masalah jembatan Königsberg . 

Masalah jembatan Königsberg adalah teka-teki lama mengenai kemungkinan menemukan jalan setapak di tujuh jembatan yang membentang di sepanjang sebuah sungai bercabang yang melewati sebuah pulau tapi dengan tanpa melewati jembatan dua kali.

Pada akhirnya Leonhard Euler merepresentasikan ilustrasi jembatan Königsberg dalam bentuk Graf. Titik yaitu {A, B, C, D} disebut sebagai Simpul (Vertex) untuk merepresentasikan sebagai daratan, dan  garis atau sisi (edge) yang menghubungkan titik-titik simpul tersebut untuk mempresentasikan sebagai jembatan.

Jawaban pertanyaan Euler adalah tidak mungkin. Agar bisa melalui setiap jembatan tepat

sekali dan kembali lagi ke tempat semula maka jumlah jembatan yang menghubungkan

setiap daratan harus genap.

Contoh penerapan graf dalam kehidupan.

1. Rute perjalanan dari rumah ke pasar, dimana banyak rute yang saling terhubung satu sama lainnya.

2, Perancangan navigasi web

Jenis-jenis Graf

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:

1. Graf sederhana (simple graph).

Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana.

2. Graf tak-sederhana (unsimple-graph).

Graf yang mengandung sisi ganda atau gelang

dinamakan graf tak-sederhana (unsimple graph).

Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:

1. Graf berhingga (limited graph)

Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.

2. Graf tak-berhingga (unlimited graph)

Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.

Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:

1. Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah.

2. Graf berarah (directed graph atau digraph)

Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.

Pengelompok graf sederhana khusus :

1. Graf lengkap

2. Graf lingkaran

3. Graf teratur

4. Graf bipartit

Share this post