Graf

Pendahuluan

Teori graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek dinyatakan sebagai noktah, bulatan, atautitik, sedangkan hubungan antara objek dinyatakan dengan garis.

Sebagai contoh, Gambar 1 adalah sebuah peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah. Sesungguhnya peta tersebut adalah sebuah graf, yang dalam hal ini kota dinyatakan sebagai bulatan sedangkan jalan dinyatakan sebagai garis. Dengan diberikannya peta tersebut, kita dapat mengetahui apakah ada lintasan jalan antara dua buah kota. Selain itu, bila panjang jalan kereta api antara dua buah kota bertetangga diketahui, kita juga dapat menentukan rute perjalanan yang tersingkat dari kota A ke kota B. Masih banyak pertanyaan lain yang dapat kita munculkan berkenaan dengan graf.

Gambar 1: Peta Jaringan Jalan Raya

Aplikasi dari teori graf ini sangat luas dan dipakai dalam berbagai disiplin ilmu maupun dalam kehidupan sehari hari. Penggunaan graf di berbagai bidang tersebut digunakan untuk memodelkan persoalan. Teori ini juga sangat berguna untuk mengembangkan model-model yang terstruktur dalam berbagai situasi. Dalam implementasinya teori ini banyak digunakan di dalam bidang kelistrikan, kimia organik, ilmu komputer, dll. Bahkan dewasa ini teori graf digunakan secara besar-besaran dalam bidang ekologi, geografi, antropologi, genetika, fisika, elektronika, pemrosesan informasi, arsitektur, dan desain. Sealain itu juga, teori ini banyak dimanfaatkan secara praktis dalam bidang industri.

Sejarah Graf

Teori graf merupakan sebuah pokok bahasan yang muncul pertama kali pada tahun 1736, yakni ketika 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.

Gambar 2: Jembatan Königsberg

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, L.Euler, adalah orang pertama yang berhasil menemukan jawaban masalah itu dengan memodelkan masalah ini ke dalam graf. Daratan (titiktitik yang dihubungkan oleh jembatan) dinyatakan sebagai titik (noktah) yang disebut simpul (vertex) dan jembatan dinyatakan sebgai garis-garis yang disebut sisi (edge).

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).

Graf Dalam kehidupan Sehari – Hari

Sedemikian banyaknya pengaplikasian graf dalam dunia ini, bila perlu dikatakan tidak akan ada habis–habis nya jika kita membahas setiap aplikasi graf dalam dunia ini, karena setiap bidang ilmu dapat dikaitkan dengan graf. Terlepas dari bidang keilmuan yang ada, ada baiknya kita mengetahui tentang pengaplikasian graf dalam kehidupan sehari – hari.

Banyak orang yang tidak sadar akan adanya peran graf dalam kehidupan kita. Baik dalam saat kita sekolah, bermain, atau bekerja, persoalan graf selalu menghampiri kita. seperti yang sudah di sebutkan pada bab bab sebelumnya, contoh graf yang dapat kita temui dalam kehidupan kita adalah sebagai berikut : Penjadwalan, kita dapat membuat jadwal pelajaran, jadwal kegiatan, ataupun jadwal ujian dengan graf, sedemikian rupa sehingga satu sama lain tidak saling tumpang tindih.

Teorema yang dipakai disini adalah pewarnaan graf. Pewarnaan graf ini sangat berguna bagi seorang staff sekolah atau guru dalam membuat jadwal pelajaran 2 kelas sekaligus atau lebih agar tidak saling bertabrakan satu sama lainnya.

Penggunaan graf dalam tournament Round-Robin. Tentunya banyak dari kita telah mempunyai pengalaman dalam mengikuti suatu tournament, atau setidaknya menonton suatu tournament, seperti contohnya, pada tournament suatu liga. Bagan tournament tersebut juga dapat direpresentasikan dengan graf. Turnamen Round-Robin Turnamen yang setiap tim bertanding dengan tim lainnya hanya sekali disebut turnamen round-robin. Turnamen semacam itu dimodelkan dengan graf berarah, yang dalam hal ini simpul menyatakan tiap tim

yang bertanding, dan busur menyatakan pertandingan. Busur (a, b) berarti tim a berhasil memukul tim b. Gambar 3memperlihatkan turnamen round-robin untuk 6 buah tim. Tim 1 tidak terkalahkan, sedangkan tim 3 tidak pernah menang.

Gambar 3: Turnamen round-robin

Graf dalam mesin otomatis.

Persoalan graf juga dapat kita temukan pada saat kita membeli minuman ataupun makanan dari sebuah mesin otomatis. Penerapan graf dalam hal ini dapat kita lihat dalam penggambaran bagan kerja mesin tersebut.

Gambar 4: Model Perilaku Mesin Otomatis

Marilah kita simak masalah pemodelan perilaku sebuah mesin jaja (vending machine) yang menjual coklat seharga 15 sen sebuah. Untuk memudahkan, kita akan memisalkan bahwa mesin tersebut hanya menerima uang logam 5 sen dan 10 sen, dan mesin tidak akan memberi kembalian bila yang dimasukkan lebih dari 15 sen. Graf berbobot (setiap sisi diberi sebuah harga, akan diejlaskan kemudian) pada Gambar 4 menggambarkan perilaku mesin ini, dengan simpul menyatakan banyaknya uang logam yang dimasukkan, yaitu 0, 5, 10, dan 15 sen atau lebih. Setiap saat seorang pembeli dapat melakukan salah satu dari tiga hal berikut: memasukkan sebuah uang logam 5 sen, memasukkan sebuah uang logam 10 sen, dan menekan tombol coklat (P) pilihannya. Dengan demikian., di dalam graf pada Gambar 4 ada tiga buah sisi dari setiap simpul yang berbobot 5, 10, dan P. Sisi dengan bobot 5 menghitung kembali jumlah uang yang ada di dalam mesin ketika pembeli memasukkan sebuah uang logam 5 sen, dan sisi dengan bobot 10 menghitung kembali jumlah uang yang ada di dalam mesin ketika seorang pembeli memasukkan uang logam 10 sen. Kiranya jelas, ketika kita ada disimpul a, b, dan c, tidak akan terjadi apa-apa meskipun tombol kita tekan; mesin akan  mengeluarkan sepotong coklat hanya bila kita sampai pada simpul d.

Kesimpulan

Seperti yang sudah dibahas pada bab-bab diatas, graf sangat banyak applikasinya baik pada berbagai bidang ilmu, maupun dalam kehidupan sehari – hari. Paper ini hanyalah membahas sebagian kecil dari penerapan penerapan yang berhubungan dengan graf. Masih banyak lagi contoh lainnya yang berkaitan dengan graf.

Referensi

·         GRAF DALAM BERBAGAI BIDANG ILMU. Hugo Toni Seputro. Program Studi Teknik Informatika, Institut Teknologi Bandung