Minggu Ke VII 7.1 Graf Hamilton Pada tahun 1859 Sir William Rowan Hamilton (1805-1865) menciptakan permainan dalam bentuk dodekahedron teratur, yaitu suatu polieder dengan dua belas muka dan dua puluh titik-sudut, setiap muka berbentuk segilima teratur dan tiga rusuk bertemu pada satu titik sudut seperti tampak pada Gambar 7.1. Titik-titik sudut ini diberi nama kotakota terkenal seperti London, New York, Delhi, Paris, dan lain-lain. Tujuan permainan ini ialah mencari suatu lintasan sepanjang rusuk dodekahedron ini yang mengunjungi setiap titik hanya satu kali dan kembali ke titik semula. Permainan ini dikenal dengan nama “perjalanan keliling dunia”. Salah satu lintasannya diperlihatkan pada Gambar 7.2 dalam bentuk sisi-sisi yang dicetak tebal.
Gambar 7.1
Gambar 7.2
DEFINISI GRAF HAMILTON. Graf terhubung G disebut graf Hamilton kalau ada sirkuit (path tertutup) yang memuat semua simpul graf G. Dalam hal hanya ada lintasan terbuka yang memuat semua simpul graf G, maka graf G disebut semi Hamilton. Jelas bahwa sirkuit Hamilton pada graf terhubung dengan n simpul mempunyai n sisi, sedangkan lintasan Hamiltonnya mempunyai (n - 1) sisi. Selain itu kita dapat menyimpulkan apakah suatu graf merupakan graf Hamilton atau semi Hamilton dengan hanya memeriksa graf-bagiannya tanpa sisi ganda dan gelang karena sirkuit atau lintasan Hamilton melintasi setiap simpulnya hanya sekali. Dengan menggunakan definisi jenis graf pada Pasal 3, mudah diperiksa bahwa graf teratur berderajat 2 merupakan graf Hamilton yang paling sederhana dengan sirkuitnya adalah semua sisi graf ini. Oleh karena itu, graf ini disebut juga graf sirkuit. Selain itu graf lengkap Kn, untuk n 3, juga merupakan graf Hamilton. Sekarang amatilah empat graf pada Gambar 7.3. Dalam paparan sebelumnya telah diperlihatkan bahwa graf pada Gambar (a) adalah graf Euler. Selain itu graf ini juga merupakan graf Hamilton. Sirkuit Hamilton digambarkan dengan sisi yang dicetak tebal, yaitu A B C D E G F A
34
Graf pada Gambar (b) adalah suatu graf Euler, dan salah satu jalurnya ialah B C G F E G B . Selain itu graf ini juga semi Hamilton dengan lintasannya ialah B C G E F ; tetapi graf ini bukan graf Hamilton. Mudah diperiksa bahwa graf pada Gambar (c) bukan graf Euler, tetapi graf Hamilton dengan sirkuitnya ialah B C G E F B . Selanjutnya graf pada Gambar (d) bukan graf Euler dan bukan pula graf Hamilton. Jadi dapat disimpulkan bahwa tidak ada ciri-ciri yang menunjukkan adanya hubungan antara graf Hamilton dan graf Euler. D C
E F
• G
C
E
B
F
• G
B
C
E F
• G
A B
C
E F
• G
D B
A Gambar 7.3 Dari beberapa gambaran graf Hamilton ternyata derajat simpul bukan merupakan ciri adanya graf Hamilton. Sampai sekarang belum berhasil diperoleh syarat perlu dan cukup agar suatu graf merupakan graf Hamilton, seperti ciri graf Euler pada Teorema 10. Pada umumnya teorema-teorema yang ada adalah cerminan dari gagasan bahwa “semakin banyak sisi suatu graf, maka semakin besar peluangnya mempunyai sirkuit Hamilton”. Salah satu sifat yang menguraikan syarat cukup bagi adanya sirkuit Hamilton dikemukakan oleh G. A. Dirac pada tahun 1952, dalam bentuk seperti berikut. Teorema 7.1. Kalau G merupakan graf sederhana dengan n simpul dan d(v) n/2, untuk setiap simpul v, maka G merupakan Graf Hamilton.
u
v
x
w
y
z Gambar 7.4
Contoh 7.1. Dengan Teorema 13 ternyata graf pada Gambar 5.1 merupakan graf Hamilton karena banyaknya simpul n = 6, dan d(v) = 3 untuk setiap V. Salah satu sirkuit Hamilton bagi graf ini ialah u v z w x y u. Sirkuit Hamilton selalu memuat tepat dua sisi yang bertemu pada setiap simpul. Oleh karena itu tidak adanya sirkuit Hamilton dapat diperlihatkan dengan kegagalan kita sewaktu membangunnya terhadap graf yang sisi gandanya dan gelangnya telah dihapus, dengan berpedoman pada tiga hal berikut.
35
PANDUAN 1 Jika suatu simpul dua, maka kedua sisi yang bertemu pada simpul tersebut harus merupakan bagian dari sirkuit Hamilton. PANDUAN 2 Tidak ada sirkuit-bagian sejati, yaitu sirkuit yang tidak melalui semua simpul graf, boleh dibentuk ketika membangun sirkuit Hamilton. PANDUAN 3 Apabila sirkuit Hamilton yang sedang disusun ternyata melalui simpul v, maka semua sisi yang lainnya dengan simpul ujung v dapat disisihkan dari graf Contoh 7.2. Jelaskan mengapa graf pada gambar 7.5 tidak mempunyai sirkuit Hamilton. Kita dapat menerapkan Panduan 1 pada simpul-simpul a, b, d dan e. Sebagai tanda bahwa kedua sisi pada masing-masing simpul tersebut terpakai, kita gambarkan sepotong ruas-garis di samping masing-masing sisi itu seperti tampak pada Gambar 7.3. Ada dua kontradiksi yang muncul. Pertama, menggunakan Panduan 1 bagi simpul a dan d mengharuskan a b sirkuit Hamilton melalui sisi {a, c}, {a, d}, dan { d, c} yang membentuk segitiga. Kenyataan ini melanggar Panduan 2. Kedua, menggunakan Panduan 1 bagi ke empat simpul berderajat dua mengharuskan sirkuit Hamilton memuat lebih dari d c dua sisi yang bertemu pada simpul c. Jadi dapat disimpulkan bahwa graf tersebut tidak mempunyai Gambar 7.5 sirkuit Hamilton. Dalam kenyataannya seorang usahawan yang ingin memasarkan hasil produksinya ke beberapa daerah pemasaran tentunya berharap semua daerah pemasaran dikunjungi dan kembali ke daerahnya dengan biaya atau jarak tempuh minimum. Masalah ini dikenal sebagai masalah pedagang keliling dan dapat dimodelkan dengan graf lengkap berbobot, yang bobot setiap sisinya menyatakan jarak tempuh atau biaya perjalanan antar-daerah yang diwakili oleh simpul-simpul graf. Dalam hal ini kita berusaha untuk mencari sirkuit Hamilton yang jumlah bobotnya terkecil. Pada prinsipnya kita dapat menyelesaikan masalah ini dengan mencacah semua sirkuit Hamilton dan memilih satu di antaranya dengan jumlah bobotnya terkecil. Sayangnya cara seperti ini tidak laik untuk graf yang simpulnya cukup banyak, misalnya jika ada 20 daerah pemasaran (barangkali daerah sebanyak ini cukup beralasan untuk kebanyakan usahawan); maka akan melibatkan 20!/2 penjumlahan bobot atau kira-kira sama dengan 1.2 x 1018. Seandainya suatu komputer mampu melakukan semilyar kali penjumlahan dalam satu detik, maka tugas ini baru selesai dalam waktu sekitar 38 tahun. Sampai sekarang belum ada algoritma yang efisien untuk menghasilkan jawaban optimum. Algoritma yang secara parsial menghasilkan jawab optimum, belum tentu hasil keseluruhannya optimum seperti diteladankan pada Gambar 7.6(a); dalam hal ini R
36
mewakili rumah dan simpul lainnya mewakili kota yang akan dikunjungi, sedangkan bobot sisi mencerminkan jarak antar-kota. C R
10 60 15 20
C 10
20
B 25
R
C 10
15
B
60
20
R
B 20
25
25
A (a)
A A (b) (c) Gambar 7.6 Dalam setiap langkah maluri kita cenderung memilih kota yang jaraknya terdekat dari kota yang terakhir dikunjungi. Prinsip ini dikenal sebagai algoritma “serakah”. Dengan algoritma serakah diperoleh trayek berbentuk R C A B R yang jarak totalnya ialah 110 seperti tampak pada Gambar (b) dengan garis-garis yang dicetak tebal. Akan tetapi dari gambar mudah diperiksa (karena banyaknya simpul hanya empat) bahwa jarak terpendek ialah 75 dengan trayek R C B A R seperti tampak pada Gambar (c). Soal-soal Latihan 1) Carilah jalur Euler atau jalur terbuka Euler, jika ada, pada keempat graf tersebut. (a) (b) •
•
•
•
• •
(c)
•
(d)
•
2) Apakah dimungkinkan ada susunan kartu domino seperti persoalan pada Teladan 3 dalam hal (a) Hanya ada 10 kartu, yaitu {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5} (b) Tujuh kartu dengan pasangan angka yang sama disisihkan dari tumpukan kartu
37
(c) Semua kartu yang mengandung angka lebih dari 4 disisihkan dari tumpukan kartu. 3) Andaikan denah suatu bangunan yang terdiri atas 5 suangan dan 18 pintu diberikan seperti pada Gambar berikut. Dapatkah seorang anak melintasi setiap pintu hanya satu kali saja dan kembali ke ruangan semula ketika ia berangkat ? R1
R2
R3
R5
R4
4) Graf pada gambar berikut merupakan suatu model jalan yang dapat dilewati pengunjung suatu pameran lukisan dalam sebuah gedung. Pintu masuk dan keluar gedung itu adalah pada lokasi M. Dapatkah Anda menyusun petunjuk dalam bentuk tanda-tanda panah sehingga pengunjung yang mengikuti petunjuk itu diharapkan tidak melihat lukisan yang sama lebih dari satu kali.
•
M 5) Tugas pengantar surat pos ialah menyebar surat-surat ke alamat tujuan di seluruh pelosok kota dengan berawal dan berakhir dari kantor pos induknya. Nalurinya cenderung tidak ingin melintasi kembali jalan yang pernah dilaluinya hanya sekedar untuk mencapai tempat lain dari tujuan yang belum selesai. Dapatkah Anda menyusun trayek perjalanan yang diharapkan pak pos yang berlokasi di P apabila model grafnya seperti berikut. •
• •
•
•
6) Perhatikan denah enam belas jembatan berikut ini j4 j1 j j12 j11 j2 3
j13 j14
j5 j6
j10 j7
j8
j9
j16
38
j15
sungai
Susunlah model graf untuk menjelaskan dapat atau tidaknya seseorang melintasi jembatan hanya satu kali dan kembali ke tempat semula ia berangkat. 7) Carilah empat sirkuit yang sisi-sisinya saling lepas dari graf pada gambar berikut :
•
8) Tentukan m dan n agar graf Km, n dan Kn merupakan graf Euler.! 9) Periksalah apakah graf-graf pada gambar berikut ini merupakan graf Hamilton atau semi Hamilton atau bukan keduanya ? a)
b)
c)
d)
10) Berikan contoh graf dengan jalur Euler identik dengan sirkuit Hamilton.! 11) Periksalah apakah graf-graf pada gambar berikut merupakan graf Euler atau graf Hamilton, atau keduanya. Berikan pula jalur Euler dan sirkuit Hamilton jika dimungkinkan. 6 a) 1 3 5 b) 5
2
4
6
4
3
1
5
c)
2
1
d) 4
1
6 2
3
2 39
5 4
3
12) Hubungan keakraban di antara tujuh siswa disajikan pada tabel berikut : Nama Siswa A B C D E F
A
B
C
D
E
F
G
-
a -
ta a -
ta a ta -
a ta a a -
ta ta a a a -
ta a a ta a ta
a berarti akrab dan ta berarti tidak akrab Guru matematika memberikan tugas rumah kepada ketujuh siswa ini. Tugas itu disampaikan kepada A dengan pesan agar disebarkan secara estafet kepada siswa lainnya melalui jalur hubungan keakraban ini untuk kemudian tugas itu dikembalikan lagi melalui A pula. Dapatkah tugas ini disebarkan dengan cara seperti itu ?. 13) Andaikan sebuah mesin dalam suatu industri obat dapat membuat delapan jenis obat per hari. Lama produksi setiap jenisnya ialah satu jam per hari. Mesin ini harus disesuaikan dahulu agar menghasilkan obat yang bentuknya berbeda dengan yang baru saja diproduksi. Demikian pula pada setiap akhir jam kerja mesin itu harus dikembalikan ke keadaan awal agar siklus produksi besoknya sama dengan haris sebelumnya. Lamanya waktu untuk menyesuaikan mesin itu bergantung pada jenis produksi sebelum dan sesudah penyesuaian itu dikerjakan; data untuk keperluan itu disajikan pada tabel di bawah ini (dalam satuan menit). Jenis produksi A B C D E F G
A
B
C
D
E
F
G
H
_
5 _
2 3 _
6 4 1 _
6 5 6 2 _
5 6 5 4 3 _
2 1 5 5 6 3 _
5 6 6 5 2 6 1
Karena lamanya penyesuaian itu tidak selalu sama, maka akan ada perbedaan waktu sebagai akibat berbedanya urutan proses jenis produksi itu. Apabila setiap hari dimulai dengan memproduksi jenis A, dapatkah Anda menata urutan proses produksi ini agar tidak ada penyesuaian yang menyita waktu lebih dari 3 menit. Jika ternyata 40
hal ini tidak mungkin, adakah penyelesaiannya kalau setiap penyesuaian tidak menyita waktu lebih dari 4 menit ?. 14) Tentukanlah sirkuit Hamilton dengan bobot minimum pada graf berikut. Apakah hasilnya identik dengan algoritma serakah ?. B 10
18 5
22
A
A
15
10
B
50 C E
10
40 30 20 20 70 40
10
30
D
15) Berikan contoh bahwa konvers teorema 13 tidak benar.
C
D
16) Jelaskan bahwa pada sebagian papan catur berukuran 4 x 4 petak ada empat sirkuit berbeda dengan panjang 4 yang dapat mewakili langkah kuda. Semua simpul sirkuit pertama dinomori dengan angka 1, dan dengan cara serupa semua simpul setiap sirkuit lainnya dinomori dengan angka 2, 3, dan 4. Selanjutnya dengan cara yang sama pula, buatlah sirkuit-sirkuit serupa pada tiga bagian papan catur berukuran 4 x 4 petak. Kemudian bentuk kembali papan catur berukuran 8 x 8 dengan menggunakan keempat bagian papan catur tadi. Dengan menelusuri nomor-nomor simpul tadi, dapatlah Anda menemukan perjalanan kuda sedemikian sehingga setiap petak disinggahi satu kali dan kembali ke petak semula.
41
