Soal yang mirip dengan persoalan jembatan Konigsberg di Jerman yang merupakan awal mula penggunaan graf. Soal yang diperlihatkan terlihat sulit, tetapi sebenarnya mudah untuk diselesaikan.
Sebelum menyelesaikan soal di atas, terlebih dahulu saya akan memperkenalkan beberapa istilah dari graf yang akan membantu menyelesaikan soal di atas.
Kumpulan simpul di atas bisa dinotasikan,
V(G)={A,B,C,D,E,F,G,H,I}
dan sisi di atas dinotasikan,
E(G)={{A,B},{A,F},{A,G},{A,H},{B,C},{B,G},{B,I},{C,D},{C,H},{C,I},{D,E},{D,H},{D,I},{E,F},{E,G},{E,I},{F,G},{F,H},{G,H}}
Terlihat ribet, tapi sangat membantu dalam penyelesaian soal.
Sekarang saya akan menggunakan teorema untuk menyelesaikan soal di atas.
Teorema 1
Sebuah graf G nontrivial adalah graf Euler jika dan hanya jika setiap simpul dari G memiliki derajat yang genap.
Dengan bantuan Teorema 1, dengan mudah kita bisa menentukan Jejak Euler dari sebuah graf.
Akibat 2
Sebuah graf G yang terhubung mengandung Jejak Euler jika dan hanya jika terdapat tepat dua simpul dari G yang memiliki derajat ganjil. Lebih jauh, setiap Jejak Euler dari G dimulai dari salah satu dari titik ganjil tersebut dan berakhir di titik ganjil yang lainnya.
Dari Akibat 2, bisa disimpulkan bahwa jalur di atas diawali dari titik G dan berakhir di titik I. Adapun bentuk jalurnya, yaitu:
G-A-F-G-H-F-E-G-B-A-H-C-B-I-H-D-E-I-C-D-I
Anda pun bisa membuat jalur yang lain, ingin mencoba?
Sumber : Chartand, Gary dan Zhang, Ping, Introduction to Graph Theory. Western Michigan University. 20 (2005) 137-138
Tidak ada komentar:
Posting Komentar