Oops! It appears that you have disabled your Javascript. In order for you to see this page as it is meant to appear, we ask that you please re-enable your Javascript!

Belajar Teori Graph

Kali ini aku akan mengajak teman-teman untuk belajar Teori Graph. Aku sudah sangat lama sekali tidak bergelut dengan hal-hal yang berbau graph. Akan tetapi kali ini aku sangat kangen dengan Mata Kuliah ini. Dulu aku mengira kalau teori graph merupak teori yang membahas tentang grafik. Akan tetapi aku salah. Graph tidak membahas grafik sama sekali, jadi apa itu graph? Mari kita coba untuk belajar.

Pengertian Graph

Secara formal, sebuah graph adalah satu pasang himpunan (V, E), dimana V adalah himpunan titik dan E adalah himpunan sisi yang menghubungkan titik dalam V. Mari kita coba perjelas.

  1. Sebuah Graph adalah sepasang himpunan. Artinya, 1 buah graph terdiri dari 2 buah himpunan.
  2. Himpunan pertama adalah V. V adalah adalah himpunan titik.
  3. Himpunan kedua adalah E. E adalah himpunan sisi yang menghubungkan titik.

Contoh Graph.

  1. V = {a, b, c, d}; E = {(a,b), (a,d), (c,d), (a,e)}
  2. V = {1, 2, 3, 4}; E = {(1,2), (2,3), (3,4), (1,4)}

Pada contoh 1 kita menamai titik dengan alfabet, pada contoh 2 kita menamai titik dengan angka. Apapun penamaan titik, yang perlu diingat adalah himpunan E merpukan hubungan dari titik-titik tersebut. Misal pada contoh 1, himpunan E terdiri dari

  1. a terhubung dengan b
  2. a terhubung dengan d
  3. c terhubung dengan d
  4. a terhubung dengan e

Kita juga bisa menamai titik dengan menggunakan nama kota. Misal Graph Kota: V = {Malang, Surabaya, Semarang, Jakarta}; E = {(Malang,Surabaya), (Semarang,Jakarta), (Jakarta,Surabaya)}

Memvisualkan Graph

Kita juga memvisualkan graph dalam gambar berisi titik-titik dan garis yang menghubungkannya. Kita coba ambil contoh Graph Kota. Ingat bahwa Graph Kota terdiri dari

  • V = {Malang, Surabaya, Semarang, Jakarta};
  • E = {(Malang,Surabaya), (Semarang,Jakarta), (Jakarta,Surabaya)}

Pertama kita gambar dulu titik-titiknya.

Menggambar Titik - Belajar Teori Graph

Menggambar Titik

Kemudian kita gambar garis-garis yang menghubungkan

Malang-Surabaya

Menghubungkan Malang dengan Surabaya

Semarang - Jakarta

Menghubungkan Semarang dengan Jakarta

Jakarta - Surabaya - Belajar Teori Graph

Menghubungkan Jakarta dengan Surabaya

Merepresentasikan Graph dalam Matrik

Selain dapat divisualkan, kita juga merepresentasikan ke dalam bentuk matrik. Kita coba ambil contoh Graph Kota. Graph kota terdiri dari Malang, Surabaya, Semarang dan Jakarta. Kita buat matrik 4×4 dengan nama-nama kota tersebut. Jika terhubung nilainya 1, jika tidak terhubung nilainya 0.

Malang Surabaya Semarang Jakarta
Malang 0 1 0 0
Surabaya 1 0 0 1
Semarang 0 0 0 1
Jakarta 0 1 1 0

 

Implementasi dari Graph

Nah, kita sudah mengerti apa itu graph, bagaimana memvisualkan graph, dan bagaimana merepresentasikan graph ke dalam bentuk matrik. Kita pastinya sudah tahu, akan digunakan untuk apa graph ini. Salah satu kegunaan-nya adalah untuk mencari shortest path (jarak terpendek) antar kota. Untuk shortest path, banyak sekali algoritma-algoritma yang dapat digunakan misalnya: Dijkstra dan Bellman-Ford.

Nah, sekian dulu kita belajar teori graph. Lain kali aku lanjutkan tentap materi graph yang lain. Selamat belajar.