DEFINISI DAN CONTOH-CONTOH GRAF

Pengertian Graf Teori graf ditulis pertama kali pada tahun 1736 oleh seorang matematikawan Swiss yang bernama Leonard Euler. Teori ini digunakan untuk menyelesaikan masalah jembatan Königsberg (sekarang, bernama Kaliningrad) yang terdapat di sungai Pregal dan mengalir mengitari pulau Kneiphof lalu bercabang menjad dua buah anak sungai. Graf merupakan struktur diskrit yang terdiri dari himpunan sejumlah berhingga obyek yang disebut simpul (vertices, vertex) dan himpunan sisi (edges) yang menghubungkan simpul-simpul tersebut. Graf digunakan untuk mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Notasi sebuah graf adalah G=(V,E), dimana: V merupakan himpunan tak kosong dari simpul-simpul (vertices atau node), misalkan V={〖v 〗_1,v_2,...,v_n} E merupakan himpunan sisi-sisi (edges atau arcs) yang menghubungkan sepasang simpul, misalkan E={e_1,e_2,...,e_n} Secara geometri graf digambarkan sebagai sekumpulan noktah atau simpul di dalam sebuah dwimatra yang dihubungkan dengan sekumpulan garis (sisi). Graf dapat dikelompokkan menjadi beberapa kategori berdasarkan beberapa sudut pandang pengelompokannya. Berdasarkan ada dan tidaknya gelang atau sisi ganda pada suatu graf, maka secara umum graf dapat dikelompokkan menjadi dua jenis: Graf sederhana (simple graph) Adalah graf yang tidak mengandung gelang ataupun sisi ganda. Seperti pada gambar disamping, adalah graf sederhana yang mempresentasikan suatu jaringan komputer. Simpul menyatakan komputer, sedangkan sisi menyatakan saluran telepon untuk berkomunikasi. Saluran telepon dapat beroperasi pada dua arah. Pada graf sederhana, sisi n adalah pasangan tak-terurut (unordered pairs). Jadi, menuliskan sisi (u,v) sama saja dengan (v,u). Kita juga dapat mendefinissikan graf sederhana dengan G=(V,E) terdiri dari himpunan tak kosong simpul-simpul dan E adalah himpunan sepasang tak-terurut yang berbeda (isi). Gambar diatas dapat dinyatakan: V={1,2,3,4}E={(1,2),(1,3),(2,3),(2,4),(2,4)} Graf tak-sederhana (unsimple-graph) Adalah graf yang mengandung sisi ganda atau gelang. Ada dua macam unsimple-graph, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang mengandung sisi ganda, seperti pada gambar disamping. Graf tersebut dapat dinyatakan sebagai berikut: V={1,2,3,4}E={(1,2),(2,3),(1,3),(1,3),(2,4),(3,4),(3,4)}={e1,e2,e3,e4,e5,e6,e7} Sedangkan graf semua adalah graf yang mnegandung gelang (loop). Seperti pada gambar berikut: V={1,2,3,4}E={(1,2),(2,3),(1,3),(1,3),(2,4),(3,4),(3,4)}={e1,e2,e3,e4,e5,e6,e7,e8} Pada graf ganda, sisi e3=(1,3) dan sisi e4=(1,3) dinamakan sisi ganda (multiple edges atau paralel edges) karena menghubungkan dua buah simpul yang sama. Sedangkan pada graf semu, e8=(3,3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama. Contoh Graf Dalam kehidupan sehari-hari, banyak persoalan yang dapat disimpulkan sebagai persoalan yang berhubungan dengan himpunan dan relasi binary (hubungan antara dua elemen himpunan), dimana logika dari persoalan tersebut sering kali dapat kita gambarkan dengan sebuah graph. Contoh seorang programer ingin membuat software sistem jaringan transportasi sedemikian rupa sehingga apabila sebuah kendaraan bergerak dari titik A kesemua titik lain kemudian kembali ke titik A dapat dilakukan dengan efisien. Kita lihat di sini titik A, B, ......., M menggambarkan titik-titik lampu merah dimana kendaraan bertahan selama 1 menit, garis atau rusuk menggambarkan relasi ”terhubung” antara titik-titik yang ada. Jadi dapat kita simpulkan, graf adalah gambaran logika dari suatu kejadian, proses, peristiwa atau hal-hal lain yang saling berkaitan. Graph adalah himpunan pasangan terurut (V, E), dimana V adalah himpunan titik (vertex) dan E adalah himpunan rusuk (edge). Untuk terhubung ke b oleh sutu garis/rusuk jika {a, b}∈E. Bila kita perhatikan graph diatas, ternyata unsur-unsur graph adalah titik-titik (vertex) simpul/ noktah yang diwakili oleh A, B,...., M dan rusuk (edge) yang diwakili oleh e_1, e_2, ......., e_19. Graf dari masalah jembatan Konigsberg dapat disajikan sebagai berikut: Misalkan graf tersebut adalah G (V,E) dengan: V={A,B,C,D}E={(A,C),(A,C),(A,B),(A,B),(B,D),(A,D),(C,D)}={e_1,e_2,e_3,e_4,e_5,e_6,e_7} Pada graf tersebut sisi e_1=(A,C) dan sisi e_2=(A,C) dinamakan sisi-ganda (multiple edges atau parallel edges) karena kedua sisi ini menghubungkan dua buah simpul yang sama, yaitu simpul A dan simpul C. Begitu pun dengan sisi e_3 dan sisi e_4. Sementara itu, pada graf di atas, tidak terdapat gelang (loop), yaitu sisi yang berawal dan berakhir pada simpul yang sama. Dari definisi graf, himpunan sisi (E) memungkinkan berupa himpunan kosong. Jika graf tersebut mempunyai himpunan sisi yang merupakan himpunan kosong maka graf tersebut dinakan graf kosong (null graph atau empty graph). Tiga Buah Puzzle The Hands of Time The Hands of Time adalah sebuah puzzle yang terlihat seperti sebuah jam. Pada puzzle tersebut terdapat beberapa lingkaran bertuliskan angka dan dua buah jarum jam yang menunjuk pada angka yang berada di arah jam dua belas (pada jam normal). Pada puzzle ini, pemain dapat memilih untuk memulai dari angka manapun. Pada saat pemain mengklik suatu angka, kedua jarum jam akan bergerak kesana, kemudian satu jarum akan bergerak sebesar angka yang diklik kekiri, dan satu jarum akan bergerak sebesar angka yang diklik ke kanan, sehingga pada langka selanjutnya, pemain memiliki dua pilihan. Setelah satu angka diklik, angka tersebut akan hilang, sehingga jika jarum jam kembali menunjuk ke tempat tersebut, pemain tidak dapat mengklik tempat tersebut. Puzzle ini selesai jika pemain berhasil menghilangkan semua angka yang ada pada papan permainan. Pemain dianggap gagal dan harus mengulang permainan jika kedua jarum jam menunjuk ke tempat yang sudah tidak ada angka sehingga pemain tidak dapat melanjutkan permainan. Ada empat level puzzle tersebut yang harus diselesaikan oleh pemain untuk mendapatkan fragment. Pemain juga diberikan waktu yang terbatas untuk menyelesaikan masing-masing level. Pada level pertama, ada lima angka pada papan permainan. Pada level kedua, ada tujuh atau delapan angka pada papan permainan. Pada level ketiga ada sembilan atau sepuluh angka pada papan permainan. Pada level keempat ada sebelas atau dua belas angka pada papan permainan. Pada puzzle The Hands of Time, pemain harus menklik semua angka tepat 1 kali. Setelah menklik sebuah angka, angka selanjutnya yang dapat diklik bergantung pada angka sebelumnya, yang menunjukkan adanya hubungan antara kedua angka tersebut. Bila setiap angka pada papan permainan diibaratkan sebagai sebuah simpul, dan perpindahan jarum jam dari suatu angka ke angka lain diibaratkan sebagai sebuah sisi berarah, maka puzzle The Hands of Time dapat direpresentasikan sebagai graf sederhana berarah. Setiap simpul pada graf tersebut akan memiliki derajat keluar sebesar dua, kecuali jika jumlah simpul pada graf adalah genap dan angka pada simpul tersebut akan menyebabkan perpindahan tepat ke simpul di seberang simpul asal. Puzzle pada gambar 3 dapat direpresentasikan sebagai graf di bawah ini. Puzzle pada gambar 6 dapat direpresentasikan sebagai graf di bawah ini. Garis berwarna biru digunakan untuk menunjukkan bahwa simpul dengan angka 6 hanya memiliki 1 sisi keluar. Setiap angka hanya dapat diklik satu kali, dan setiap angka harus diklik. Hal tersebut menunjukkan bahwa pemain harus membuat sebuah lintasan Hamilton. Dapat terlihat dengan mudah bahwa graf pada gambar 6 memiliki lintasan Hamilton sebagai berikut, warna kuning menandakan simpul awal. Namun, untuk graf dengan jumlah simpul yang lebih banyak seperti graf pada gambar 7, mencari lintasan Hamilton menjadi lebih sulit. Sampai saat ini, belum ditemukan algoritma untuk mencari lintasan dan sirkuit Hamilton yang efektif. Namun, untuk graf dengan jumlah simpul yang sedikit, seperti pada graf yang merepresentasikan puzzle The Hand of Time, masih dapat digunakan algoritma yang melakukan pengecekan secara brute force. Pengecekan dapat dilakukan dengan mengiterasi satu per satu lintasan yang ada pada graf. Jika lintasan yang sedang diiterasi membentuk sirkuit yang bukan sirkuit Hamilton, pengecekan untuk lintasan itu dihentikan, kemudian lanjut melakukan pengecekan dari lintasan terakhir yang belum membentuk sirkuit. Pengecekan dilakukan terus-menerus hingga menemukan lintasan Hamilton. Lintasan Hamilton untuk graf pada gambar 7 adalah sebagai berikut, warna kuning menandakan simpul awal. Sebuah puzzle The Hand of Time belum tentu memiliki solusi yang unik. Sebuah puzzle bisa saja memiliki lebih dari satu solusi atau tidak memiliki solusi sama sekali. Puzzle bisa saja tidak memiliki solusi sama sekali jika angka-angka untuk puzzle benar-benar diperoleh secara acak. Puzzle pada gambar 2, yang direpresentasikan sebagai graf pada gambar 6 memiliki lebih dari solusi. Salah satu alternatif solusinya adalah sebagai berikut, warna kuning menandakan simpul awal. Jika ada sebuah puzzle yang direpresentasikan sebagai graf seperti graf di bawah ini. Puzzle ini tidak memiliki solusi karena tidak ada lintasan Hamilton di dalam graf tersebut. Flow Free Flow Free adalah sebuah permainan pada platform android yang dapat diunduh secara gratis pada Google Play Store. Game buatan Big Duck Games LLC ini adalah permainan yang ber-genre puzzle dengan ratusan level. Pemain akan diberikan sebuah puzzle berbentuk matriks n x n dimana pada beberapa kotak pada puzzle tersebut akan diletakkan beberapa pasang titik berwarna tertentu. Tujuan dari permainan ini adalah menghubungkan semua titik yang berwarna sama dengan melalui semua kotak yang ada tanpa penghubung antara titik-titik tersebut berpotongan. Puzzle ini dapat dianggap sebagai graf dengan n x n simpul yang simpulnya tersusun dengan rapi sedemikian sehingga membentuk sebuah kotak berukuran n x n. Dengan kata lain, setiap kotak pada puzzle dapat dianggap sebagai simpul, dengan kotak yang berisikan warna tertentu sebagai simpul yang mendapat perlakuan khusus. Dengan menganggap semua kotak pada puzzle adalah sebuah simpul, maka tujuan dari permainan dapat diubah menjadi mencari lintasan-lintasan yang menghubungkan simpul yang berwarna sama dalam graf sedemikian sehingga seluruh simpul pada graf dilalui dan tidak ada lintasan yang saling berpotongan. Gambar diatas merupakan contoh dari puzzle pada level 13 dan level 27. Pemain dapat memilih ukuran puzzle yang ingin dimainkan, mulai dari 5 x 5 sampai 14 x 14. Pemain dapat mengulang langkahnya yang salah, namun jumlah gerakan yang dilakukan pada permainan tersebut tetap bertambah. Banyak gerakan yang paling sedikit yang dilakukan pemain untuk menyelesaikan suatu level akan tercatat pada level tersebut. Jika tidak ada gerakan yang salah atau percuma pada suatu permainan, maka permainan tersebut adalah permainan yang sempurna (perfect) dan tidak mungkin suatu himpunan gerakan yang banyak gerakannya lebih sedikit dari banyak gerakan pada perfect game. Pada permainan ini ditambahkan pula beberapa fitur unik agar permainan menjadi lebih menarik. Diantaranya adalah penambahan jembatan pada suatu kotak sehingga kotak tersebut bisa dilewati dari dua arah dan tidak dianggap berpotongan. Puzzle Sudoku Permainan Sudoku adalah permainan yang dapat melatih logika manusia dalam berfikir cepat dan teliti. Permainan ini tidak sembarang dimainkan, karena bila bermain dengan sembarangan diawal maka tidak bisa menyelesaikan game ini.Papan Sudoku terbuat dari Sembilan buat kotak berukuran 3X3 (disebut blok/subgrid) yang disusun sedemikian rupa sehingga menghasilkan kotak besar berukuran 9X9 (gambar 1). Beberapa kotak sudah diisi sebagai petunjuk awal dan tugas pemain adalah melengkapi angka-angka pada kotak yang lain sehingga keseluruhan papan permainan terisi angka secara lengkap. Dalam permainan Sudoku angka-angka yang harus diisikan harus unik dari 1 hingga 9 sehingga dalam 1 blok/subgrid hanya terdiri atas angka 1-9 yang tidak berulang dalam 1 baris maupun kolom. Angka-angka dalam Sudoku sebenarnya tidak memiliki hubungan aritmetis satu sama lain, boleh digantikan dengan 9 huruf, lambang atau yang berbeda. Gambar 1. Puzzle Sudoku Untuk memecahkan teka-teki Sudoku, dapat menggunakan Algoritma backtracking (runut balik). Algoritma ini merupakan perbaikan dari algoritma Brute Force, dimana solusi dapat ditemukan dengan penelusuran yang lebih sedikit dan dapat mencari solusi permasalahan lebih efektif karena tidak perlu memeriksa semua kemungkinan solusi yang ada. Algoritma backtracking ini mudah diimplementasikan dengan bahasa pemrograman yang mendukung seperti Visual Basic 6.0. Prinsip dasar algoritma backtracking adalah mencoba semua kemungkinan solusi yang ada. Perbedaan dengan algoritma brute force terdapat pada konsep dasar, yaitu pada backtracking semua solusi dibuat dalam bentuk pohon solusi (tree) gambar 2 dan pohon tersebut akan ditelusuri sehingga ditemukan solusi terbaik yang diinginkan. Gambar 2. Pohon solusi (tree) Misalkan pohon di atas menggambarkan solusi dari suatu persoalan. Jika kita ingin mencari solusi dari A ke E, maka jalur yang harus ditempuh adalah (A-B-E). Demikian juga untuk solusi-solusi yang lain. Algoritma backtracking akan memeriksa jalur secara DFS, yaitu dari solusi terdalam pertama yang ditemui yaitu solusi E. Jika ternyata E bukanlah solusi yang diharapkan, maka pencarian akan dilanjutkan ke F. Jalur yang harus dilalui untuk bisa mencapai E adalah (A-B-E) dan untuk mencapai F adalah (A-B-F). Kedua solusi tersebut memiliki jalur awal yang sama, yaitu (A-B). Jadi, dari pada memeriksa ulang jalur dari A kemudian B, maka jalur (A-B) disimpan dulu dan langsung memeriksa solusi F. Untuk kasus pohon yang lebih rumit, cara ini dianggap lebih efisien daripada jika menggunakan algoritma Brute-Force. DAFTAR PUSTAKA Munir, Rinaldi. 2012. Matematika Diskrit. Bandung: Informatika Bandung Adiwijaya. 2013. Matematika Diskrit. Sekolah Tinggi Teknologi Telkom. diakses di https://www.google.co.id/url?q=https://sofianingrumhampatra.files. wordpress.com/2013/01/bab4teorigraf.pdf&sa=U&ved=0ahUKEwjOnrulzfXVAhUEGJQKHeZtAzsQFggRMAY&usg=AFQjCNGpRJXunb7TY03pVa_ B9lqDHn98Zw pada 27 Agustus 2017 Hasanah, Lia. t.tp. Matematika Diskrit. diakses di http://www.academia.edu/8723 643/Definisi_Graf pada 27 Agustus 2017 Reztaputra, Raihannur. Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2014/2015 Wibisono, Samuel. 2008. Matematika Diskrit. Yogyakarta: Graha Ilmu diakses di https://ine2011042063.files.wordpress.com/2014/11/e-book-matematika-diskrit.pdf pada 27 Agustus 2017 http://repository.usu.ac.id/bitstream/handle/123456789/48624/Chapter%20II.pdf;jsessionid=4E9E5F362E858D98D17D9D00CB197AE2?sequence=3