Teori graf merupakan sebuah pokok bahasan yang muncul pertama kali pada tahun 1736, yakni ketika Leonhard Euler mencoba untuk mencari solusi dari permasalahan yang sangat terkenal yaitu Jembatan Königsberg. Di kota Königsberg (sebelah timur Prussia, Jerman sekarang), sekarang bernama kota Kaliningrad, terdapat sungai Pregal yang mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai.
Masalah jembatan Königsberg ini adalah, mungkinkah melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi ke tempat semula? Kemudian tahun 1736 seorang matematikawan Swiss, Leonhard Euler, adalah orang pertama yang berhasil menemukan jawaban masalah itu dengan memodelkan masalah ini ke dalam graf. Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakan sebagai titik (noktah) yang disebut simpul atau titik (vertex) dan jembatan dinyatakan sebagai garis-garis yang disebut sisi atau garis (edge).Euler memberi permisalan daratan sebagai sebuah titik, setiap titik diberi label A, B, C, dan D. Peta kota Königsberg kuno dan graf yang dibuat Euler dapat dilihat pada Gambar
Euler mengungkapkan bahwa tidak mungkin seseorang berjalan melewati tepat satu kali masing-masing jembatan dan kembali lagi ke tempat semula, karena pada graf model jembatan Königsberg itu tidak semua simpul berderajat genap (derajat sebuah simpul adalah jumlah sisi yang bersisian dengan simpul yang bersangkutan).
Teori graf merupakan salah satu pokok bahasan yang sudah sangat tua usianya tetapi memiliki banyak terapan praktis hingga saat ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan sisi atau garis.
Graf
Kata graf dalam matematika memiliki bermacam-macam arti. Graf dikenal dengan sebutan grafik yaitu suatu fungsi dan relasi. Disini kata graf digunakan dalam arti yang lain.
Definisi 1: Graf G didefinisikan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V,E), yang dalam hal ini V adalah himpunan tidak kosong dari titik-titik (vertices atau node) dan E adalah himpunan garis (edges atau arcs) yang menghubungkan sepasang titik (Munir, 2005:356).
Dalam definisi 1 dinyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Oleh karena itu, sebuah graf dimungkinkan tidak mempunyai garis satu pun, tetapi titik harus ada, minimal harus memiliki satu titik. Graf yang hanya memiliki satu titik tanpa garis pun, dinamakan graf trivial. Dalam graf yang berbeda setiap garis yang berhubungan dengan satu atau dua titik maka titik-titik tersebut dinamakan titik ujung. Graf disebut loop apabila graf tersebut memiliki garis yang hanya berhubungan dengan satu titik ujung. Dua garis berbeda yang menghubungkan dua titik yang sama disebut garis paralel.
Dua titik dikatakan berhubungan (adjacent) jika ada garis yang menghubungkan keduanya. Titik yang tidak mempunyai garis yang berhubungan dengannya disebut titik terasing (isolating point).
Kadang-kadang suatu graf dinyatakan dengan gambar. Gambar suatu graf G terdiri dari himpunan titik-titik V(G), himpunan garis-garis E(G) yang menghubungkan titik-titik tersebut, dan label pada garisnya (jika ada). Panjang garis, kelengkungan garis, dan letak titik tidak berpengaruh dalam suatu graf.
Titik pada graf dapat dinomori dengan huruf, seperti a, b, c, …, v, w,…, dengan bilangan asli 1, 2, 3, …, atau gabungan keduanya. Sedangkan sisi yang menghubungkan titik u dan v dinyatakan dengan pasangan (u, v) atau dinyatakan dengan lambang e1, e2, e3, …. Dengan kata lain, jika e adalah sisi yang menghubungkan titik u dengan titik v, maka e dapat ditulis sebagai e = (u, v).
Secara geometri graf digambarkan sebagai sekumpulan noktah (titik) di dalam bidang dwimatra (2 dimensi) yang dihubungkan dengan sekumpulan garis.
Jenis-jenis Graf
Dilihat dari sudut pandang pengelompokannya graf dapat dikelompokkan menjadi beberapa kategori (jenis). Pengelompokan graf dapat dipandang berdasarkan ada tidaknya garis ganda atau garis gelang, berdasarkan jumlah simpul, atau berdasarkan orientasi arah pada garis.
Berdasarkan ada tidaknya gelang atau garis ganda pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1) Graf sederhana (simple graph)
Graf yang tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana. Pada graf sederhana, garis adalah pasangan yang tak-terurut (unordered pairs). Jadi, menuliskan garis (u, v) sama dengan (v, u).
2) Graf tak-sederhana (unsimple graph)
Graf yang mengandung garis ganda atau gelang dinamakan graf tak-sederhana. Ada dua macam graf tak-sederhana, yaitu graf ganda (multigraph) yaitu graf yang mengandung garis ganda dan graf semu (pseudograph) yaitu graf yang mengandung gelang (loop).
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 garis, maka secara umum graf digolongkan menjadi dua jenis:
1) Graf tak-berarah (undirected graph)
Graf yang garisnya tidak mempunyai orientasi arah disebut graf tak-berarah. Seperti graf sederhana, urutan pasangan titik yang dihubungkan oleh garis tidak diperhatikan, (u, v) = (v, u) adalah garis yang sama.
2) Graf berarah (directed graph atau digraph)
Graf yang setiap garisnya diberikan orientasi arah disebut graf berarah. Berbeda dengan graf tak-berarah, pada graf berarah (u, v) dan (v, u) menyatakan dua garis yang berbeda, dengan kata lain (u, v) ≠ (v, u). Untuk garis (u, v), titik u dinamakan titik asal (initial vertex) dan titik v dinamakan titik terminal (terminal vertex). Pada graf berarah gelang diperbolehkan tetapi sisi ganda tidak.
REFRENSI:
Munir, Rinaldi. 2005. Matematika Diskrit Buku Teks Ilmu Komputer Edisi Ketiga. Bandung: Informatika.
Suryadi, H. S. 1994. Teori Graf Dasar Seri Diklat Kuliah. Jakarta: Gunadarma
Tidak ada komentar:
Posting Komentar