Modul
3
Keterhubungan
P
|
ada Modul 2, Anda telah mempelajari berbagai
konsep yang terkait dengan graph seperti representasi graph, simpul-simpul
berdekatan, derajat simpul, dan berbagai graph khusus atau istimewa. Pengertian-pengertian
tersebut sangat penting dan bermanfaat sehingga konsep-konsep itu akan terus
dikembangkan dalam modul-modul berikutnya.
Dalam modul ini Anda akan mempelajari konsep lintasan
dan keterhubungan. Pengertian tersebut berawal dari permasalahan
sehari-hari seperti perjalanan seorang penjaja barang (salesman), penyusunan jadwal kegiatan dan yang sejenis. Kemudian,
dengan mengetahui konsep lintasan diharapkan dapat menentukan lintasan dalam
perjalanan yang memiliki jarak terpendek sehingga diperoleh waktu dan beaya
yang minimal.
Setelah menyelesaikan modul ini Anda
diharapkan memiliki kemampuan sebagai berikut:
1. menjelaskan
konsep perjalanan dalam graph terhubung;
2. menjelaskan
konsep lintasan, lintasan, sirkuit, dan sikel;
3. membandingkan
antara lintasan dan lintasan, lintasan dan sirkuit, sirkuit dan sikel;
4. menjelaskan
simpul pemotongan dan jembatan dalam suatu graph yang diberikan;
5. membedakan
dampak penyingkiran simpul pemotongan
dan jembatan;
6. menjelaskan
konsep lintasan terpendek;
7. menggunakan
Algoritma Dijkstra untuk menghitung panjang lintasan terpendek;
8. menjelaskan
konsep sirkuit Euler dan graph Euler;
9. menetapkan
apakah suatu graph adalah graph Euler;
10. menjelaskan
sirkuit Hamilton dan lintasan Hamilton;
11. menjelaskan
graph terlacak (traversable);
12. menetapkan
apakah suatu graph adalah graph Hamilton.
Kemampuan-kemampuan tersebut sangat bermanfaat
bagi semua guru matematika SMU. Dengan kemampuan ini cakrawala matematika Anda
akan menjadi semakin luas dan dapat meningkatkan rasa percaya diri. Dampak positip akan
diperoleh yaitu Anda semakin cinta terhadap bidang studi matematika ini. Suatu
sikap bangga dan bahagia akan muncul dalam menjalankan tugas mengajar
matematika yang akan menumbuhkan motivasi serta usaha untuk menjadi pengajar
yang profesional
Untuk membantu Anda menguasai kemampuan di
atas, dalam modul ini akan disajikan pembahasan dalam butir uraian, dalam 2
Kegiatan Belajar (KB) sebagai berikut:
Kegiatan Belajar 1: Lintasan.
Kegiatan Belajar 2: Graph Terhubung.
Agar Anda berhasil dengan baik mempelajari
modul ini ikuti petunjuk belajar sebagai berikut:
1. Bacalah
dengan cermat bagian Pendahuluan modul ini sampai Anda memahami apa, untuk
apa, dan bagaimana mempelajari modul ini.
2. Baca
sepintas bagian demi bagian dan temukan kata-kata kunci dan kata-kata yang Anda anggap baru.
Jangan kuatir jika Anda belum memahami pada pembacaan yang pertama.
3. Tangkaplah
pengertian demi pengertian dari isi modul ini melalui pemahaman sendiri
dan tukar pikiran dengan mahasiswa/guru lain atau dengan tutor Anda.
4. Jika
pada pembacaan yang pertama dan Anda belum paham adalah kejadian yang lumrah.
Coba ulangi lagi. Gunakan alat-alat bantu pensil dan kertas untuk coret-coret
jika dipandang perlu.
5. Mantapkan
pemahaman Anda melalui diskusi mengenai hasil pemahaman Anda dalam
kelompok kecil atau bersama tutor.
Kegiatan
Belajar 1
Lintasan
M
|
isalkan G suatu himpunan tidak kosong dan hingga.
Didefinisikan V(G) adalah himpunan semua simpul dari G dan E(G) adalah himpunan
semua rusuk dari G. Himpunan G yang dilengkapi dengan V dan E, dinotasikan
G(V,E) disebut graph jika V(G) bukan himpunan kosong. Jika banyaknya simpul
(atau titik) p dan banyaknya rusuk (atau garis)
q maka graph G dinotasikan dengan G(p,q).
Koleksi atau kelompok graph yang banyak
terapannya adalah graph terhubung. Pada Kegiatan Belajar 1 akan dibahas
graph-graph terhubung serta beberapa konsep yang terkait seperti lintasan, lintasan
dan sirkuit.
Misalkan
G sebuah graph. Suatu graph H
disebut subgraph atau graph
bagian dari G,
jika V(H) Í V(G) dan E(H) Í E(G). Jika suatu graph F isomorphik
dengan subgraph H dari G, maka F juga merupakan subgraph dari G.
Contoh 1
Diberikan graph G dan
H subgraph dari G, seperti tersaji pada Gambar 3.1. Misalkan F suatu graph yang
isomorphik dengan H maka F merupakan subgraph dari G.
Gambar 3.1.
Perjalanan (Walk)
Misalkan
u dan v adalah simpul-simpul dari graph G. Perjalanan u-v di G adalah barisan berganti-ganti antara simpul dan
rusuk dari G yang diawali dengan simpul u dan diakhiri dengan simpul v,
sedemikian rupa sehingga setiap rusuk menghubungkan simpul-simpul tepat
sebelumnya dan sesudahnya.
Contoh 2
Perhatikan
Gambar 3.1, barisan : c, cb, b, bf, f, fc, c, cd, d, de, e, ed, d adalah perjalanan c – d. Sedangkan barisan
: a, af, f, fb, b, bc, c, de, e adalah bukan perjalanan a-e, karena rusuk de
tidak menghubungkan simpul sebelumnya, yaitu c dan simpul sesudahnya, yaitu e.
Berdasarkan pengertian ini, dapat diketahui bahwa
dalam perjalanan membolehkan pengulangan simpul atau rusuknya. Sebagaimana pada contoh perjalanan c-d, baik simpul c maupun rusuk de
muncul dua kali (berulang).
Sesungguhnya dalam
suatu perjalanan, kita hanya memerlukan daftar dari simpul-simpulnya. Hal itu
karena setiap rusuk dalam suatu perjalanan selalu menghubungkan simpul sebelum
dan sesudahnya. Artinya, dengan hanya menyajikan daftar simpul-simpulnya, dapat
langsung diketahui rusuk-rusuknya juga. Dengan demikian suatu perjalanan dapat
disajikan secara lebih sederhana. Sebagai contoh, perjalanan c-d dapat
dituliskan cukup barisan : c, b, f, c, d, e, d.
JEJAK (Trail)
Suatu jejak u-v (u-v trail) di dalam graph G adalah perjalanan
yang tidak mengulangi sebarang rusuk.
Contoh 2
Perhatikan Gambar 3.1. Perjalanan c-d pada Contoh 1 bukan suatu jejak c-d, sebab rusuk
de dilalui (berulang) dua kali. Sedangkan perjalanan c-d yang berbentuk c. b. f. c. d merupakan jejak c-d di graph G karena tidak terdapat pengulangan
rusuk-rusuknya.
LINTASAN (path)
Suatu lintasan u-v (u-v path) adalah perjalanan u-v yang tidak mengulangi sebarang
simpul dan sebarang rusuk. Dengan kata lain, suatu lintasan u-v adalah jejak
u-v yang tidak mengulangi sebarang simpul.
Contoh 3
Perhatikan Gambar 3.1.
Perjalanan c, e, d
adalah lintasan c-d, sedangkan perjalanan c, b, f, c,
d merupakan jejak c-d, tetapi bukan
merupakan lintasan c-d, karena simpul c
berulang.
.
Terhubung (connected)
Dua
buah simpul u dan v di dalam
graph G dikatakan terhubung (connected), jika u = v, atau jika u ¹ v, terdapatlah lintasan u-v di G. Suatu graph G dikatakan terhubung jika setiap dua simpul di G adalah terhubung,
jika tidak demikian G disebut takterhubung (disconnected).
Contoh 4
Misalkan graph G, sebagaimana terlukis pada Gambar
3.2. di bawah. terhubung, sedangkan graph H tidak terhubung. Hal itu karena
terdapat dua simpul pada H, yaitu w dan z yang tidak terhubung.
 |
w z
Komponen (component)
Suatu subgraph H dari graph G disebut komponen dari G jika H tidak termuat di
dalam sebarang subgraph terhubung dari G yang mempunyai simpul dan rusuk lebih
banyak daripada H.
Contoh 5
Perhatikan Gambar
3.3., graph G mempunyai empat komponen.
G
Gambar 3.3
Berdasarkan
pengertian komponen ini dapat diketahui bahwa suatu graph yang mempunyai
komponen lebih dari satu akan membentuk suatu graph tidak terhubung. Sedangkan suatu
graph yang hanya memiliki satu komponen adalah graph terhubung.
Jika
G suatu graph yang tidak terhubung dan memiliki dua komponen yang berbentuk
graph lengkap maka G disebut graph dengan komponen lengkap.
Contoh 6
Graph G adalah graph dengan komponen
lengkap karena G memiliki 2 komponen graph lengkap, yaitu K4 dan K2.
 |
G
Sirkuit (Circuit),
dan Sikel (cycle)
jejak
u-v dengan sifat u = v dan paling sedikit memuat tiga rusuk disebut sirkuit. Dengan kata lain, suatu
sirkuit adalah jejak yang mempunyai simpul awal dan
simpul akhirnya sama. Suatu
sirkuit yang tidak mengulang sebarang simpul (terkecuali yang pertama dan
terakhir) disebut sikel.
Contoh 7
Graph G yang terlukis
pada Gambar 3.3, lintasan : a, b, c, e, b, f, a,
adalah suatu sirkuit
tetapi bukan sikel, sebab simpul b terulang. Sedangkan lintasan : b, d, c, e, b membentuk sirkuit dan sekaligus sikel.
Berdasarkan definisinya, diketahui bahwa suatu
lintasan adalah barisan yang berganti-ganti antara simpul-simpul dan
rusuk-rusuk. Meskipun kita telah membuat persetujuan untuk menyajikan suatu lintasan dengan
simpul-simpul, namun perlu diketahui bahwa suatu lintasan itu membentuk
subgraph. Artinya, himpunan simpul dan rusuk yang ditetapkan oleh suatu
lintasan membangun suatu subgraph.
Contoh 8
Perhatikan
Gambar 3.3, dengan mudah diketahui bahwa
barisan : a, b, e, c, b, f membentuk
suatu lintasan. Kemudian, jika didefinisikan
subgraph H dari G dengan V(H) = {a, b, e, c, f} dan E(H) = {ab, be, ec, cb, bf},
maka didapat bahwa H juga suatu
lintasan dalam G.
Pada
umumnya, ada kebiasaan memandang subgraph tersusun atas simpul-simpul dan
rusuk-rusuk dari suatu lintasan, lintasan, sirkuit atau sikel berturut-turut
sebagai lintasan, lintasan, sirkuit, atau sikel.
Berikut akan diberikan beberapa contoh
yang terkait dengan graph terhubung dengan perluasannya.
Contoh 9
Misalkan G(p,q) adalah suatu graph dengan banyak
simpul p dan banyak rusuk q. Jika nilai p = 2n untuk sebarang bilangan asli n,
dan G mempunyai dua komponen lengkap. Buktikanlah bahwa banyaknya rusuk minimum
q adalah: q(minim) = (p2 - 2p)/4. Kemudian, jika G mempunyai nilai q
minimum tentukan jenis graph dari G(V,E)
Bukti
Berdasarkan definisi, diketahui bahwa graph
lengkap, Kp, memiliki adalah p simpul sehingga banyaknya rusuk
adalah p(p - 1)/2. Ingat, setiap 2 simpul menyumbang satu rusuk.
Diketahui G(V, E), dengan p = 2n dan mempunyai
dua komponen. Misalkan komponen pertama mempunyai x simpul, maka komponen kedua
memiliki (2n - x) simpul. Karena masing-masing komponen merupakan graph
lengkap, maka komponen pertama Kx dan komponen kedua K2n-x.
Banyaknya rusuk masing-masing komponen
adalah x (x - 1)/2 dan
(2n - x) (2n - x) (2n - x - 1)/2.
Jadi, banyaknya rusuk graph G adalah
q = x (x - 1)/2 + (2n - x)(2n - x - 1)/2
= (x2 - x + 4n2 - 4nx
+ x2 - 2n + x)/2
= x2 - 2nx + 2n2 - n
Perhatikan bahwa q merupakan fungsi kuadrat dalam
variabel x. Nilai minimum q dicapai untuk
x = n, sehingga didapat
q minimum = n2 - 2n2 + 2n2 - n = n2 - n.
Tetapi menurut ketentuan, p = 2n atau n = p/2,
sehingga diperoleh
q minimum = (p2 - 2p)/4.
Jika
q mengambil nilai minimum ini maka kedua komponen itu adalah Kx = Kn dan K2n-x = Kn. Jadi dua buah graph lengkap sebagai
komponen G adalah graph lengkap Kp/2.
Contoh 10
Diberikan graph G(p,q) dengan p > 2. Jika derajat setiap simpul v dari G lebih dari
(p - 1)/2, biasa ditulis: der (v) > (p - 1)/2, untuk setiap v di G
maka buktikan bahwa G terhubung!
Bukti. Pembuktian menggunakan
teknik bukti kontrapositif. Andaikan graph G tak terhubung dan der (v) >
(p - 1)/2. Karena G tak terhubung maka G mempunyai dua atau lebih komponen.
Misalkan G1 salah satu komponen dari G dan u sebuah simpul dalam G1. Karena setiap
simpul dalam G berlaku der(v) >
(p - 1)/2 maka berlaku juga untuk simpul dalam G1, sehingga
diperoleh der(u) = (p - 1)/2.
Akibatnya, banyaknya simpul-simpul dalam
G1 adalah 1 + (p – 1)/2 = (p + 1)/2. Berdasarkan fakta ini diketahui
bahwa banyaknya simpul dalam G lebih dari dua kali (p + 1)/2, yakni, lebih dari
p + 1. Dengan kata lain, jika G takterhubung dan der (v) > (p - 1)/2
maka banyak simpul > p+1, yakni tidak samadengan p. Kesimpulannya, pernyataan pada Contoh 10 benar, yakni G suatu
graph terhubung.
Contoh 11
Buktikanlah bahwa relasi terhubung yang
didefinisikan dalam graph terhubung adalah relasi ekuivalen.
Sebelum membuktikan soal tersebut Anda
diingatkan kembali arti relasi ekuivalen. Relasi ekuivalen adalah suatu relasi yang
bersifat refleksif, simetris, dan transitif. Relasi ini memiliki peran penting
dalam matematika.. Lebih formalnya,
suatu relasi R pada himpunan A disebut relasi ekuivalen
jika ketiga syarat berikut dipenuhi:
(i) aRa
untuk semua a Î A;
yang disebut sifat refleksif
(ii) aRb Þ bRa untuk semua a, b Î A; yang disebut sifat simetris
(iii) aRb
dan bRc Þ aRc untuk semua a, b, c Î A; yang disebut sifat transitif.
Sekarang akan kita buktikan contoh 3. Misalkan
G graph terhubung dan a, b, c adalah tiga simpul sebarang di G.
(i) Simpul
a dan a terhubung menurut definisi keterhubungan. Sehingga terbukti aRa.
(ii) Misalkan
a dan b terhubung atau aRb. Menurut definisi, terdapat lintasan a-b. Lintasan
ini dapat dinyatakan dalam barisan simpul: a, p, q, ..., x, b. Jika barisan
simpul ini kita balik urutannya maka didapat barisan: b, x, ..., q, p, a. Berdasarkan
definisi, barisan ini menunjukkan adanya lintasan b-a sehingga simpul b dan a
terhubung atau bRa. Dengan demikian, jika diketahui aRb kita
peroleh bRa, dan terbukti bRb Þ bRa.
(iii) Misalkan
simpul a dan b terhubung dan simpul b dan c terhubung. Dengan kata lain
diketahui aRb dan bRc. Akan kita buktikan aRc. Karena aRb
dan bRc, maka terdapat lintasan a-b dengan barisan simpul: a, c, d, ...,
t, b dan lintasan b-c dengan barisan simpul; b, p, q, ..., z, c. Jika barisan
ini kita gabungan diperoleh: a, c, d, ..., t, b, p, q, ..., z, c. Barisan ini
menunjukkan adanya lintasan a-c atau aRb dan bRc Þ aRc.
Simpul Pemotongan dan
Jembatan
Pada bagian ini, Anda akan diperkenalkan
dengan kelompok simpul dan rusuk yang dalam beberapa hal memiliki banyak kemiripan.
Jika e adalah suatu rusuk dalam graph G, maka G
– e adalah subgraph dari G yang mempunyai banyak simpul sama dengan G
dan mempunyai banyak rusuk seperti G terkecuali sebuah rusuk e. Jika v adalah
suatu simpul dalam graph G yang paling sedikit mempunyai dua simpul, maka G
– v adalah subgraph dari G yang himpunan simpulnya memuat semua simpul
dari G terkecuali v dan himpunan rusuk terdiri atas semua rusuk di G terkecuali
rusuk-rusuk yang bertemu (hadir) di v.
Suatu
simpul v di dalam graph terhubung G disebut simpul pemotongan (cut-vertex) jika G – v takterhubung.
Contoh 11
Graph
G yang tersaji pada Gambar 3.4, simpul c adalah satu-satunya simpul pemotongan.
Sekarang
perhatikan konsep yang terkait untuk rusuk-rusuk. Rusuk e di dalam graph
terhubung G disebut suatu jembatan (bridge)
jika G – e takterhubung.
Contoh 12
Perhatikan
Gambar 3.4, rusuk r4 adalah suatu
jembatan karena G - r4 membentuk graph tak terhubung.
Jika v adalah simpul pemotongan dari graph
terhubung G, maka G – v memuat dua atau
lebih komponen. Akan tetapi, jika
e suatu jembatan dari G, maka G – e mempunyai tepat dua komponen.
Teorema berikut ini akan menunjukkan rusuk-rusuk yang mana saja dari suatu
graph merupakan suatu jembatan.
Teorema 3.1. tidak
Misalkan
G adalah graph terhubung. Suatu rusuk e
di G adalah suatu jembatan di G jika dan hanya rusuk e tidak terletak
dalam sebarang sikel di G.
Sebelum membuktikan teorema di atas, perlu diingat
bahwa teorema itu suatu biimplikasi (memuat syarat perlu dan cukup). Teorema 3.1.
terdiri atas dua pernyataan yang masing-masing harus dibuktikan. Kedua
pernyataan itu adalah sebagai berikut:
(1) Syarat perlu :
Jika e adalah suatu jembatan
dalam graph terhubung G, maka rusuk e tidak terletak dalam sebarang sikel C di
G.
(2) Syarat Cukup
Jika C sebarang sikel di graph
terhubung G, dan e suatu rusuk di G yang tidak termuat di C, maka e suatu
jembatan di G.
Bukti (1)
Dibuktikan dengan
teknik kontrapositif. Misalkan rusuk e = ab adalah jembatan di graph terhubung
G yang termuat dalam sikel C : a, b, c, d, ..., x, a. Maka subgraph G –
e memuat lintasan a-b, yakni, a, x, ..., d, c, b. Akan ditunjukkan bahwa G – e terhubung.
Misalkan a1 dan b1
adalah dua simpul sebarang dalam subgraph G – e. Akan ditunjukkan bahwa G - e
memuat lintasan a1 – b1 . Hal itu sesuai dengan definisi
graph terhubung. Karena G diketahui diketahui, maka ada lintasan yang menghubungkan simpul a1 dan b1.
Misal kita namakan lintasan ini J. Jika jembatan e tidak terletak di lintasan
J, maka lintasan J pun adalah lintasan di G – e, maka G – e terhubung. Sekarang
andaikan jembatan e terletak pada lintasan J. Maka lintasan J dapat dinyatakan
dalam barisan a1, ..., a, b, ..., b1 atau dalam a1,
..., b, a, ..., a1. Dalam kasus pertama, a1 terhubungkan
ke a, atau a1Ra dan b terhubungkan ke b1,
atau bRb1 di G - e, sedangkan dalam kasus kedua, a1
terhubungkan ke b atau a1Rb dan a terhubungkan ke a1
atau aRa1. Dan telah kita lihat bahwa a dan b di G - e
terhubung atau aRb. Karena relasi “keterhubungan”, adalah relasi
ekuivalen, jadi transitif, maka a1Ra, aRb, bRb1
berakibat a1Rb1 atau a1 dan b1
terhubungkan. Maka jika e termuat dalam sikel, subgraph terhubung G - e, dan demikian e bukanlah
jembatan. Kontradiksi dengan ketentuan. Pengandaian yang mengatakan bahwa e terletak di J harus
diingkar.
Bukti (2)
Akan dibuktikan dengan teknik kontrapositif. Andaikan
graph G terhubung dan rusuk e = ab bukan jembatan di G. Akan kita
buktikan bahwa rusuk e termuat dalam suatu jembatan di G. Karena rusuk e bukan
jembatan, akibatnya G - e terhubung. Dengan demikian terdapat lintasan a-b di G
- e. Lintasan ini kita namakan J. Tetapi J bersama-sama e membentuk suatu sikel
di G yang memuat jembatan e. Kontradiksi dengan pengandaian.
Berdasarkan hasil (1)
dan (2), terbuktilah contoh 3.
Contoh 12
Misalkan G adalah graph terhubung dan semua
simpulnya berderajat genap. Buktikanlah
bahwa G tidak mungkin memuat jembatan!
Bukti
Akan dibuktikan d teknik kontradiksi. Andaikan
graph terhubung G memuat jembatan e = ab. Maka G – e terhubung, dan terdiri
atas dua komponen. Salah satu komponen G1 memuat simpul a dan
komponen yang lain G2 memuat simpul b. Semua simpul dalam graph G1
berderajat genap terkecuali simpul a, yakni, simpul a berderajat ganjil.
Tetapi hal ini kontradiksi dengan sifat yang mengatakan bahwa banyaknya simpul
berderajat ganjil. Tetapi hal ini kontradiksi dengan sifat yang mengatakan
bahwa banyaknya simpul berderajat ganjil adalah genap. Pengandaian itu salah.
Graph G tidak memuat jembatan.
Contoh 13
Misalkan G adalah graph terhubung, dan misalkan a,
b, dan c adalah tiga simpul di G. Diketahui pula bahwa setiap lintasan a-b
simpul c. Bagaimanakah sifat simpul c? Buktikan jawaban Anda!
Penyelesaian
Misalkan J sebarang lintasan a - b di G,
yang memuat simpul c. lintasan J dapat dinyatakan dalam barisan simpul: a, p,
..., s, c, t, ..., b. Jika simpul c disingkirkan, maka subgraph G – c terdiri
atas dua atau lebih komponen, dan tidak ada satu pun lintasan a-b. Jadi simpul
c adalah simpul pemotongan.
GRAPH BERLABEL
Suatu
graph G disebut graph berlabel jika semua rusuk-rusuknya atau simpul-simpulnya
dikawankan dengan suatu bilangan atau data lainnya. Khususnya, jika setiap
rusuk e di G diberikan bilangan tak negatif k(e), maka k(e) disebut berat,
bobot atau panjang dari rusuk e. Gambar 3.5
menunjukkan suatu graph berlabel dengan panjang setiap rusuknya diberikan
dengan memberikan bilangan pada gambarnya. Panjang lintasan u-v adalah jumlah panjang
rusuk-rusuk dalam lintasan u-v. Kita dapat menafsirkan bahwa simpul-simpulnya
adalah kota-kota dan label k(e) sebagai jarak antara kota-kota itu.
Permasalahan yang penting di sini adalah mencari lintasan minimum dari dua kota
yang diketahui.
Contoh 14
Diberikan graph G, sebagai berikut
 |
Gambar
3.5.
Kita akan menemukan
banyak lintasan P-Q dengan panjang yang bervariasi. Misal lintasan P-Q : P, D,
E, F, Q, dengan panjang 4+6+4+2 = 16. Dengan cara yang sama akan diperoleh
lintasan P-Q yang lain.
Ternyata, lintasan P-Q minimum
adalah lintasan : P, A, D, B, E, C, Q yang panjangnya 14 satuan. Coba Anda
mencoba lintasan yang lain, pasti
panjangnya akan lebih besar atau sama dengan 14.
LINTASAN TERPENDEK
Konsep
lintasan akan memberikan banyak manfaat bag kita. Khususnya dalam menentukan lintasan
terpendek sehingga dapat meminimkan waktu dan beaya.
Lintasan terpendek adalah lintasan dengan
sifat jumlah nilai rusuk-rusuk yang dilaluinya terkecil (S k(e) minimum). Untuk graph dengan banyak rusuk yang relatif sedikit, lintasan
terpendek dari simpul a ke simpul z dengan mudah dapat dicari,
bahkan dengan mencongak. Tetapi untuk graph dengan banyak rusuk yang besar,
pencarian lintasan terpendek tidak lagi mudah. Untuk menentukannya dibutuhkan
suatu alat bantu yang biasa disebut algoritma. Algoritma ini memberikan cara
menghitung lintasan terpendek dari simpul yang diketahui a ke seluruh simpul.
Misalkan k(e) menyatakan panjang rusuk e, dan misalkan m
adalah variabel panjang yang akan dihitung. Untuk kenaikan nilai-nilai m,
algoritma itu dikerjakan dengan cara memberikan label pada simpul-simpul yang lintasan
terpendeknya dari simpul a adalah m. Algoritma menentukan lintasan terpendek
diketahui oleh E. W. Dijkstra. Detailnya akan dibahas pada bagian berikut.
ALGORITMA LINTASAN TERPENDEK (ALGORITMA DIJKSTRA)
Ada beberapa versi algoritma Dijkstra untuk
mencari lintasan terpendek dari simpul a ke simpul z dalam graph terhubung G.
Salah satu versinya adalah sebagai berikut:
1. Tetapkan m = 1 dan
berikan pada simpul a dengan (-, 0) (tanda “-” berarti kosong).
2. Periksa setiap rusuk e = pq dari simpul berlabel p ke beberapa simpul
tak berlabel q. Misalkan
label p adalah (r, k(p)). Jika k(p) + k(e) = m, berikan simpul q dengan label
(p, m).
3. Jika semua simpul belum
berlabel, naikan m dengan 1 dan terus ke Langkah (2). Jika tidak demikian,
teruskan ke Langkah (4). Jika Anda hanya tertarik untuk mencari lintasan
terpendek ke z, maka jika z telah berlabel kita dapat terus ke Langkah (4).
4.
Untuk sebarang simpul y, lintasan
terpendek dari simpul a ke y mempunyai panjang k(y), yakni, bagian kedua dari
label y; dan lintasan demikian dapat diperoleh dengan cara melacak balik atau
mundur dari y (dengan menggunakan bagian pertama dari label) seperti diberikan
atau dideskripsikan di bawah ini.
Perhatikan bahwa jarak (panjang) dari simpul a
ke simpul tertentu, algoritma ini menjawab pertanyaan-pertanyaan berikut:
Berapakah panjang yang dapat diperoleh dengan kenaikan 1 unit?, berapa dengan 2 unit, dengan 3 unit,
..., dengan m unit, ...?. Verifikasi formal untuk algoritma ini memerlukan
induksi matematik (atas bilangan pada
simpul-simpul berlabel).
Ide kuncinya adalah bahwa untuk mencari lintasan
terpendek dari simpul a ke sebarang simpul
yang lain, kita harus mencari lintasan terpendek dari simpul a ke
simpul-simpul ‘penyela’. Jika Ji = v1, v2,
..., vi adalah lintasan terpendek ke simpul vi, maka Ji
= Ji-1 + (vi-1, vi ) dengan Ji-1 = v1,
v2, ..., vi-1 adalah lintasan terpendek ke vi-1.
Demikian pula Ji-1 = Ji-2 + (vi-2,vi-1)
dan seterusnya.
Untuk mencatat lintasan terpendek ke vi , kita perlu
menyimpannya (sebagai bagian = ‘absis’, atau pasangan pertama dari label
dalam algoritma di atas) adalah nama untuk simpul terakhir berikutnya pada Ji
, yakni, vi-1 pada lintasan
adalah vi-2, simpul terakhir berikutnya pada Ji-2. Dengan
terus melacak balik proses ini, kita dapat menemukan keseluruhan Ji.
Algoritma yang diberikan di atas jelas
memiliki ketidakefisienan. Jika semua jumlah dari k(p) + k(e) dalam Langkah 2
bernilai paling sedikit m’ > m, maka panjang yang akan dihitung m segera
saja dinaikkan ke m’.
Contoh 15
Sepasang suami
istri ingin bepergian dari simpul N (Nganjuk) ke simpul R (Rangkasbitung)
melalui jaringan jalan raya, seperti ditunjukkan dalam Gambar 3.6.
|
||||||||
|
||||||||
 |
||||||||
 |
||||||||
Penyelesaian.
Kita gunakan Algoritma
Lintasan terpendek. Pertama, N kita berikan label N(-, 0). Untuk m = 1, tidak
dapat melakukan pelabelan (Periksalah rusuk-rusuk Nb, Nd, dan Nf). Untuk m = 2,
k(N) + k(Nb) = 0 + 2 = 2, dan dengan demikian simpul b kita berikan label (N,
2). Untuk m = 3 atau 4, kita tidak dapat memberikan pelabelan baru. Untuk m =
5, k(b) + k(bc) = 2 + 3 = 5, dan dengan demikian simpul c kita berikan label
(b, 5). Kita dapat meneruskan cara ini untuk melabelkan simpul-simpul seperti
dalam Gambar 3.6. Akhirnya, dengan melacak mundur dari simpul R kita
memperoleh: R-m-j-k-h-d-c-b-N, yang panjangnya 24 unit (5 + 2 + 3 + 5 + 2 + 2 +
3 + 2 = 24). Jadi lintasan terpendek yang dicari adalah (dibalik):
N-b-c-d-h-k-j-m-R.
 |
1)
Buktikanlah bahwa suatu graph G
adalah terhubung jika dan hanya jika untuk setiap dua simpul sebarang u dan v
di G, terdapat perjalanan u-v di G.
2)
Misalkan G1 dan G2
adalah graph-graph yang isomorphik. Buktikanlah bahwa jika G1
terhubung, maka G2 juga terhubung!
3)
Jika G adalah graph terhubung yang
tidak isomorphik dengan K2, dan jika e adalah suatu jembatan di G,
buktikanlah bahwa e bertemu (hadir) dengan simpul pemotongan di G!
4)
Apakah Teorema 3.1 masih tetap
benar jika kata “sikel” ditukar dengan kata “sirkuit”? Jelaskan jawab Anda!
5)
Pada Gambar 3.6, carilah lintasan
terpendek dari simpul c ke simpul m, dengan menggunakan algoritma Dijkstra!
Petunjuk Jawaban Latihan
1)
(i) Jika G terhubung, maka untuk setiap pasang simpul u dan v di G
terdapat lintasan u-v di G. Karena suatu lintasan adalah perjalanan maka
terdapat perjalanan u-v di G.
(ii) Di G berlaku untuk setiap dua simpul u dan v
ada perjalanan u-v, tinggal menunjukkan
bahwa perjalanan u-v di G memuat lintasan u-v di G. Dalam perjalanan u-v ada
kemungkinan mengulang rusuk atau simpul. Mengingat relasi terhubung adalah
relasi ekuivalen, simpul atau rusuk yang terulang dalam perjalanan itu dapat dibuang.
Hal itu berakibat suatu perjalanan u-v dapat dibentuk menjadi lintasan u-v. Sebagai
ilustrasi, perjalanan u-v: u, c, ..., p, c, d, ..., v dapat dibentuk menjadi lintasan u-v: u, c..., p, d, ..., v.
2)
Dua buah graph yang isomorphik
terdapat korespondensi 1-1 antara simpul-simpul dan rusuk-rusuk dan
‘mempertahankan’ keterhubungan. Karena Graph G1 terhubung, maka ada lintasan
u1 – v1 di G1 untuk dua simpul sebarang
di G1. Karena G1
dan G2 isomorphik, maka di G2 terdapat lintasan u2
- v2. Jadi G2
terhubung.
3)
Graph G paling sedikit mempunyai 3
simpul. Karena G terhubung dan mempunyai rusuk e sebagai jembatan, maka G - e
tepat mempunyai dua komponen dan setiap komponen adalah terhubung. Menurut Teorema
3.1, rusuk e tidak termuat dalam sikel di G yang manapun. Jika e = uv, maka
graph G - v paling sedikit terdiri atas dua komponen yang masing-masing tidak
memuat rusuk e = uv. Jadi u dan v adalah simpul pemotongan.
4)
Benar. Sebab, setiap sirkuit adalah sikel.
5)
14. c-d-h-k-j-m.
Dalam graph G, perjalanan u-v adalah
barisan berganti-ganti antara simpul dan rusuk di G, diawali dan diakhiri
dengan simpul, setiap rusuk menghubungkan 2 simpul tepat di depan dan
dibelakannya dalam barisan itu.
Perjalanan yang tidak mengulang rusuk disebut jejak.
Suatu jejak yang tidak mengulang simpul disebut lintasan. Jejak yang simpul
awal dan akhirnya berimpitan disebut sirkuit. Sirkuit yang tidak
mengulang simpul disebut sikel. Suatu graph G dikatakan terhubung jika
setiap pasang simpul u dan v di G ada jejak u-v di G.
Jika graph G terhubung dan rusuk e suatu jembatan,
maka G - e adalah graph terhubung dengan dua komponen. Simpul v dalam graph
terhubung G disebut simpul pemotongan jika G - v adalah graph takterhubung
dan paling sedikit terdiri atas dua komponen.
Graph G disebut berlabel jika setiap rusuk
atau simpul di G dikawankan dengan suatu bilangan tertentu atau data tertentu. Panjang
perjalanan adalah jumlah bilangan pada rusuk-rusuk yang digunakan dalam
perjalanan itu.
 |
1) Manakah
di antara contoh graph di bawah ini takterhubung dengan tiga komponen dengan
sifat ketiga komponennya isomorphik:
 |
|||||||
|
 |
 |
|||||
A. G1 dan G3
B. G2 dan G3
C. G1 dan G2
D. G2 dan G4
2) Graph
G(V,E) adalah graph takterhubung, dengan banyak simpul p. Jika banyaknya
komponen dari G melebihi p, maka banyaknya anggota himpunan graph yang demikian
adalah ....
A. takhingga
B. tepat
satu
C. paling
banyak = p
D. hampa/kosong
3) Perhatikanlah
graph G pada Gambar 3.7 di bawah ini:
 |
Barisan
simpul A, B, C, F, E, F adalah ....
A. lintasan
yang bukan lintasan
B. sirkuit
C. sikel
D. lintasan
4) Barisan
simpul C, E, B, D, E, F, C dalam graph pada Gambar
3.7 adalah ....
A. lintasan
B. sikel
C. sirkuit
D. sikel
yang bukan sirkuit
5) Barisan
simpul A, C, F, E, D, C, A dalam graph G pada Gambar 3.7 adalah ....
A. perjalanan
B. sirkuit
C. lintasan
D. lintasan
6) Perhatikan
graph pada Gambar 3.8 di bawah ini
Berapakah
banyaknya titik pemotong dalam graph G pada Gambar 3.8?
A. 0
B. 1
C. 2
D. 3
7) Perhatikanlah
graph G pada Gambar 3.8. Berapakah banyaknya jembatan dalam graph itu?
A. 0
B. 1
C. 2
D. 3
8) G
adalah graph dengan 11 simpul, rusuk e adalah jembatan dan simpul v adalah
simpul pemotong. Maka terdapatlah sebuah komponen dari G - e dengan
banyaknya simpul paling sedikit ....
A. 6
simpul
B. 7
simpul
C. 8
simpul
D. 9
simpul
Untuk soal nomor 9 dan 10, perhatikanlah
graph pada Gambar 3.9 di bawah ini.
9) Dengan
menggunakan Algoritma Dijkstra, hitunglah lintasan terpendek dari A ke Y!
A. 19
B. 21
C. 23
D. 25
10) Berapakah
lintasan terpendek dari simpul D ke R dalam graph pada Gambar 3.9?
A. 19
B. 21
C. 23
D. 25
Cocokkanlah jawaban Anda dengan Kunci Jawaban
Tes Formatif 1 yang terdapat di bagian akhir modul ini. Hitunglah jawaban yang
benar. Kemudian, gunakan rumus berikut untuk mengetahui tingkat penguasaan Anda
terhadap materi Kegiatan Belajar 1.
 |
Arti tingkat penguasaan: 90 - 100% = baik sekali
80
- 89%
= baik
70
- 79%
= cukup
< 70% = kurang
Apabila mencapai tingkat penguasaan 80% atau
lebih, Anda dapat meneruskan dengan Kegiatan Belajar 2. Bagus! Jika masih di bawah 80%, Anda harus mengulangi materi
Kegiatan Belajar 1, terutama bagian yang belum dikuasai.
Kegiatan
Belajar 2
Graph Euler
D
|
i tengah kota Konigberg (Rusia) terdapat sungai
Pregel. Di tengah sungai itu terdapat dua buah pulau yang dihubungkan oleh
sebuah jembatan. Pulau-pulau itu juga dihubungkan ke tepian-tepiannya. Salah
satu pulau dihubungkan dengan 4 jembatan dan pulau yang satu lagi dengan dua
jembatan. Jadi ada 7 jembatan seperti terlihat dalam Gambar 3.10.
Permasalahannya adalah mungkinkah melewati ketujuh jembatan itu terus-menerus
tanpa mengulangi salah satu jembatan?
Situasi di Konigsberg itu dapat disajikan
dengan multigraph, seperti diperlihatkan pada Gambar 3.11. Simpul-simpul itu menyajikan
daerah tepian dan pulau-pulau, dan rusuk menyajikan jembatan-jembatan. Perlu
diingat bahwa multigraph adalah graph di mana diperkenankan adanya dua simpul
yang dihubungkan lebih dari satu rusuk.
Masalah jembatan di Konigsberg sebenarnya
adalah masalah menentukan apakah multigraph M pada Gambar 3.11 mempunyai
lintasan (kemungkinan sirkuit) yang memuat semua rusuk. Anda mungkin
menggunakan metode coba-coba, dan Anda mungkin akan memperoleh kesimpulan bahwa
lintasan yang demikian tidak ada. Akan tetapi, bagaimana Anda membuktikan
bahwa lintasan seperti itu tidak ada. Kita sajikan bukti ini dalam teorema
berikut.
Teorema 3.2.
Multigraph M pada Gambar 3.11
tidak mempunyai lintasan yang memuat semua rusuknya.
Bukti
Dibuktikan dengan
teknik kontrapositif. Andaikan multigraph tersebut mempunyai lintasan L
yang memuat semua rusuk di M. Maka L berawal dari salah satu dari 4 simpul A,
B, C, atau D dan berakhir pada salah satu dari simpul-simpul A, B, C, atau D.
(pada simpul yang sama jika lintasan itu suatu sirkuit). Diperoleh, paling sedikit ada dua simpul di
antara A, B, C, dan D di mana L tidak berawal dan tidak berakhir.
Misalkan simpul ini, di antara B, C, dan D kita namakan v.
Perhatikan bahwa setiap simpul B, C, dan D
berderajat 3. Akibatnya, setelah suatu rusuk di L masuk pertama kali di v dan
ada rusuk lainnya di L untuk meninggalkan v, tepat ada satu rusuk yang bertemu
di v dan belum berada di L. Jadi v harus berada di L sekali lagi dengan masuk
melalui rusuk yang bertemu di v dan belum digunakan. Akan tetapi setelah sampai
di v untuk kedua kalinya, tidak ada lagi rusuk untuk keluar dari v, sehingga L
harus berakhir di v. Hal ini tidak mungkin, sebab L tidak berakhir di v. Maka,
tidak ada lintasan L, yang berarti kontradiksi dengan pengandaian.
Permasalahan jembatan Konigsberg pertama kali
dipecahkan oleh matematikawan Swiss Leonhard Euler (1707-1783). Jenis lintasan
seperti yang dicari dalam masalah jembatan Konigsberg itu telah digunakan untuk
memberikan nama koleksi graph (multigraph) dengan sifat ini.
a. GRAPH EULER
Suatu
sirkuit yang memuat semua simpul dan semua rusuk dari multigraph M disebut sirkuit
Euler. Suatu graph yang memuat semua sirkuit Euler
disebut graph Euler, sedangkan multigraph yang memuat sirkuit Euler
disebut multigraph Euler.
Contoh 16
Graph
G pada Gambar 3.12 adalah graph Euler sebab G memuat semua sirkuit Euler dari
G.
Teorema berikut ini memberikan cara sederhana
menentukan apakah suatu multigraph atau graph adalah multigraph atau graph
Euler.
Teorema 3.3. tidak
Multigraph
M adalah multigraph Euler jika dan hanya jika M, terhubung dan setiap simpulnya
berderajat genap.
Untuk membuktikan Teorema 3.3.
harus dibuktikan dua pernyataan yaitu:
1. Jika multigraph M adalah multigraph Euler,
maka M terhubung dan setiap simpulnya berderajat genap.
2. Jika multigraph M terhubung dan setiap
simpulnya berderajat genap, maka M adalah multigraph Euler.
Sebelum membuktikan teorema 3.3, Anda akan
diberikan contoh prosedur yang digunakan dalam graph G pada Gambar 3.12.
Perhatikan salah satu simpul, umpamanya a. Kita buat lintasan L berawal di simpul
a dan sepanjang mungkin. Maksudnya, kalau bisa sekali pemilihan sudah kita peroleh sirkuit yang memuat semua
simpul dan rusuknya. Misalkan kita pilih, L: a, b, c, f, g, a, c, g, b, f, a.
Dalam kasus ini, L bukanlah sirkuit Euler, sebab lintasan L tidak memuat seluruh simpul dan rusuk di G.
Akan tetapi, c adalah simpul pada L1 yang bertemu dengan rusuk-rusuk
yang tidak termuat dalam L. Jika kita melanjutkan L1 sepanjang
mungkin, salah satu pilihan L1 adalah: c, d, e, c. Sekarang kita
masukkan L1 ke dalam L dengan
cara memasukkan c pada pertama kali dijumpai dalam barisan, dan Anda akan
memperoleh:
a, b, c, d, e, c , f, g, a, c, g, b, f, a,
yang merupakan sirkuit Euler.
Sekarang
kita buktikan kedua pernyataan dalam teorema tersebut.
Bukti (1)
Misalkan G graph Euler. Maka G memuat sirkuit
Euler S, yang berawal dan berakhir, umpamanya di v simpul di G, setiap dua simpul
di G terhubungkan oleh lintasan (yang dapat dimodifikasi menjadi suatu lintasan).
Jadi G terhubung. Sekarang, tinggal menunjukkan bahwa setiap simpul berderajat
genap. Pertama, perhatikan sebarang simpul u dalam G yang bukan v. Karena u
bukan simpul awal dan bukan simpul akhir dari S maka setiap kali kita masuk ke
u melalui suatu rusuk dan keluar melalui rusuk yang lain. Dengan demikian
setiap kali S melalui simpul u derajat simpul u bertambah (naik) dengan 2. Akibatnya,
simpul u berderajat genap. Karena u simpul sebarang dalam G maka semua simpul
dalam G, selain v mempunyai derajat genap. Tinggal membuktikan simpul v
berderajat genap. Dalam kasus simpul v, setiap kali masuk ke v, kecuali yang
pertama kali dan terakhir kali, derajat simpul v juga naik dengan 2, dan pada
saat pertama kali meninggalkan v serta masuk kembali ke v yang terakhir kalinya,
maka derajatnya bertambah 2. Jadi v juga
berderajat genap.
Bukti (2)
Diketahui graph G terhubung dan setiap simpulnya
berderajat genap. Akan dibuktikan bahwa G adalah graph Euler. Pilih sebuah
simpul v di G, dan suatu lintasan L berawal di v. Lanjutkan lintasan ini
sepanjang mungkin sampai pada simpul w sedemikian rupa sehingga hanya
rusuk-rusuk yang bertemu dengan w, telah berada di L semua. Maka L tak dapat
dilanjutkan.
Akan diperlihatkan bawah w = v. Andaikan w
¹ v. Setiap
kali lintasan masuk dan keluar dari w, kita menggunakan 2 rusuk. Ketika
lintasan masuk ke w untuk terakhir kalinya, hanya digunakan satu rusuk. sehingga
simpul w berderajat ganjil. Akan tetapi, diketahui bahwa w berderajat genap akibatnya
harus ada paling sedikit satu rusuk yang bertemu di w, untuk jalan keluar dari w, yang bukan berada di L. Artinya
L dapat dilanjutkan dan tidak berhenti di w, jika w ¹ v. Hal ini kontradiksi dengan hipotesa dan dapat disimpulkan bahwa w =
v, dan terbuktilah bahwa L adalah sirkuit. Tinggal membuktikan bahwa L memuat
semua rusuk dan simpul di G.
Misalkan sirkuit L tidak memuat semua rusuk di
G. Karena G terhubung, harus ada paling sedikit satu simpul u di L yang bertemu dengan rusuk-rusuk yang
tidak di L. Singkirkan simpul u di G dan perhatikan submultigraph H yang
terjadi. Karena L tidak memuat semua rusuk di G, maka H pasti masih mempunyai
rusuk. Selanjutnya setiap simpul di L bertemu dengan rusuk di L yang banyaknya
genap. Misalkan H1 adalah simpul di L bertemu dengan rusuk di L
yang banyaknya genap. Misalkan H1
adalah komponen dari H yang memuat simpul u. Jika kita membuat lintasan
L1 yang berawal di u sepanjang mungkin, maka L1, seperti
terdahulu, harus berakhir di u (yakni, L1 harus merupakan sirkuit).
Sekarang ada cara membuat sirkuit S1 berawal dan berakhir di v, yang
mempunyai lebih banyak rusuk daripada L. Hal ini kita kerjakan dengan
memasukkan sirkuit L1 ke dalam sirkuit L pada tempat terjadinya u.
Jika S1 telah memuat semua rusuk
dan simpul di G, maka S1 adalah sirkuit Euler di G dan G adalah
multigraph Euler. Jika S1 tidak memuat semua rusuk dan simpul di G
prosedur di atas dapat diulangi, sehingga akhirnya akan diperoleh sirkuit Euler
di G (prosedur ini akan berakhir/selesai karena multigraph diasumsikan
berhingga). Jadi, terbukti bahwa L adalah sirkuit yang memuat semua simpul dan
rusuk di G sehingga G adalah graph Euler.
Sekarang kita perhatikan konsep yang analog.
Jika suatu graph G mempunyai lintasan, bukan sirkuit, yang memuat semua simpul
dan rusuk di G, maka G disebut graph terlacak (traversabel graph) dan lintasan itu disebut lintasan Euler.
Contoh 15
Diberikan graph G,
seperti terlukis pada Gambar 3.13 berikut.
Graph G bukan graph
Euler, sebab terdapat simpul di G yang berderajat ganjil. Akan tetapi, graph G
merupakan graph terlacak karena memiliki lintasan Euler L: a, b, d, c, b, b, e,
d.
Teorema berikut menyatakan persyaratan graph terlacak.
Bukti teorema ini sangat mudah dan ditinggalkan sebagai latihan.
Teorema 3.4. Multigraph G
adalah terlacak jika dan hanya jika G terhubung dan tepat mempunyai dua simpul
ganjil. tidak
Selanjutnya, setiap lintasan Euler di G
berawal pada salah satu dari simpul berderajat ganjil dan berakhir pada simpul
ganjil yang satu lagi.
Sekarang jelas bahwa multigraph pada Gambar
3.11 (Masalah Jembatan Konigsberg) bukan graph Euler dan bukan graph terlacak.
Jadi tidak ada lintasan di M yang memuat semua rusuk di M.
Sifat penting dari multigraph Euler dan
terlacak adalah bahwa apabila sekali simpul telah digambar, kita dapat
menggambar seluruh multigraphnya dalam satu gerakan terus menerus. Dengan kata
lain, rusuk-rusuk dalam multigraph terhubung dapat digambar “tanpa mengangkat
pensil dari kertas gambar” asalkan banyaknya simpul berderajat ganjil adalah
dua atau nol.
Contoh 16
Gambar 3.14 menunjukkan denah perjalanan dan
kota-kota yang dilewati. Jika Anda tinggal di kota A, mungkinkah Anda berjalan
keliling kota-kota berawal di A tepat melalui jalan-jalan itu sekali saja? Jika
Anda tinggal di kota B, mungkin hal itu dikerjakan?
Penyelesaian
Untuk menyelesaikan masalah ini, kita pandang
denah itu sebagai multigraph. Perhatikanlah bahwa semua simpul berderajat genap
dan terhubung. Maka, multigraph itu adalah multigraph Euler dan memuat sirkuit
Euler S. Sirkuit S memuat setiap rusuk dari graph G masing-masing sekali dan
simpul-simpul boleh jadi berulang. Oleh karena sirkuit dapat berawal dari
sebarang simpul, maka dari simpul manapun dapat memulai perjalanan mengelilingi
denah kota tersebut. Jadi, baik dari kota A maupun B dapat melakukan perjalanan
mengelilingi denah kota dengan melalui jalan-jalan tepat sekali dan kembali ke
kota awal.
Contoh 17
Gambar 3.15 adalah denah sebuah rumah dengan
beberapa ruang dan beberapa pintu yang menghubungkan ruang-ruang atau dengan
bagian luar. Mungkinkah seseorang berjalan dengan berawal pada suatu tempat
(baik di dalam maupun di luar rumah) dengan terus menerus dan melalui semua pintu
hanya sekali?
Penyelesaian
Kita dapat menggunakan multigraph sebagai
model matematika pada permasalahan ini.
Pertama-tama kita sajikan ruang-ruang itu sebagai simpul. Setiap dua
simpul dihubungkan oleh rusuk-rusuk sesuai dengan banyaknya pintu antara
ruang-ruang yang bersangkutan (termasuk ‘ruang’ di luar rumah). Graph representasi dari masalah ini tersaji
pada Gambar 3.15 (b). Jawaban terhadap pertanyaan ini bergantung apakah
multigraph itu multigraph Euler, terlacak, atau bukan.
Dari Gambar 3.15 (b), tampak bahwa
simpul-simpul B, D, E, dan O berderajat ganjil, sehingga multigraph itu bukan
multigraph Euler, bukan pula terlacak (sebab lebih dari 2 simpul yang
berderajat ganjil). Jadi, tidaklah mungkin berjalan melalui seluruh pintu tepat
sekali.
GRAPH HAMILTON
Pada seksi ini akan dibahas konsep sikel
Hamilton. Suatu konsep yang mirip dengan
sirkuit Euler, yang demukan oleh Sir William Rowan Hamilton, 1805 - 1865, seorang
matematikawan Irlandia.
Suatu
graph G disebut graph Hamilton jika di G terdapat sikel yang
memuat setiap simpul di G. Suatu sikel yang memuat semua simpul di G dinamakan sikel
Hamilton. Jadi graph Hamilton adalah graph yang memuat sikel Hamilton.
Contoh 18
Perhatikan
graph Graph pada Gambar 3.16 berikut.
Graph G1 memuat sikel Hamilton, misal a, b, e, d, c, a sehingga membentuk graph
Hamilton.
Gambar 3.16
Graph
G2 bukan merupakan grap Hamilton. Untuk membuktikan G2
bukan graph Hamilton, digunakan teknik kontrapositif. Andaikan G2
graph Hamilton, maka ia memuat sikel Hamilton S. Karena sikel S memuat setiap
simpul di G2; maka S memuat b, c, dan d. Masing-masing b, c, dan d
berderajat 2. Dengan demikian S harus memuat dua rusuk yang bertemu dengan
setiap b, c, dan d. Hal ini berarti bahwa S memuat, misalnya, ketiga rusuk ab,
ac, dan ad. Akan tetapi, sebarang sikel hanya dapat memuat dua rusuk yang
bertemu dengan suatu simpul pada sikel (ingat sikel tidak mengulang simpul). Sedangkan
dalam sikel ini, a sudah memuat 3 rusuk sehingga S bukan sikel Hamilton. Jadi G2
tidak mungkin memuat sikel Hamilton yang berarti bukan graph Hamilton.
Kontradiksi dengan pengandaian G2 sebagai graph Hamilton.
Berikut ini adalah
teorema yang menyatakan syarat perlu bagi suatu graph agar menjadi graph
Hamilton.
Teorema
3.5. Jika G adalah
graph dengan banyak simpul p > 3, sedemikian rupa sehingga derajat
setiap simpul v di G minimal p/2 (dengan kata lain der(v) > 2 untuk setiap v di G), maka G
adalah graph Hamilton.
Catatan
Anda harus faham bahwa
pernyataan dalam Teorema 3.5 itu adalah syarat
perlu, bukan syarat perlu
dan cukup. Artinya, terdapat suatu graph G dengan p >
3 dan deg v < p/ 2
untuk setiap v di G adalah graph Hamilton.
Contoh 16
Misalkan G adalah
graph ‘segi lima’ ( P5), maka didapat p = 5 dan der(v) = 2 < 5/2. Akan tetapi G memuat
sikel Hamilton sehingga G adalah graph Hamilton.
Bukti
Untuk membuktikan
Teorema 3.5, digunakan metode induksi matematika atas banyaknya simpul p di G.
1.
Jika G mempunyai p = 3 dan der v > 3/2
untuk setiap v di G, maka der v = 2 sehingga didapat graph G = K3. Jadi G adalah
graph Hamilton dan teorema benar untuk p = 3.
2.
Teorema dianggap benar untuk p >
4. Misalkan J adalah lintasan terpanjang di G.
Misalkan J : u1, u2, ..., uk, seperti
pada Gambar 3.17. Ini berarti bahwa J memuat simpul paling banyak yang mungkin
dimuat oleh J di G.
Karena tidak ada lagi lintasan di G yang
memuat simpul lebih banyak daripada simpul yang dimiliki J, maka setiap simpul yang bertemu dengan u1
harus berada di J. Hal itu juga berlaku, setiap simpul yang bertemu (atau
disebut juga “berdekatan”) dengan uk harus berada di J. Karena u1
paling sedikit berdekatan dengan p/2 simpul yang semuanya berada di J, maka J
paling sedikit memuat sebanyak 1 + p/2
simpul.
Selanjutnya, haruslah terdapat simpul ui
di J, dengan 2 < i < k, sedemikan rupa sehingga ui
berdekatan dengan u1 dan uk berdekatan dengan ui-1.
Jika tidak demikian, maka untuk setiap simpul ui berdekatan dengan u1,
dan simpul ui-1 tidak akan berdekatan dengan uk. Akan
tetapi, karena paling sedikit ada p/2
simpul-simpul ui berdekatan dengan simpul u1, maka akan
ada paling sedikit p/2 simpul-simpul ui-1 yang tidak akan berdekatan dengan uk.
Akibatnya der uk < (p - 1) - p/2 < p/2 dan sesuatu yang tidak mungkin terjadi, sebab
der uk > p/2. Dengan demikian, terdapat suatu simpul ui
di J sedemikian rupa sehingga u1ui
dan ui-1 uk kedua-duanya
merupakan rusuk G (periksa Gambar 3.18). Akibatnya, terdapat sikel S: u1,
ui, ui+1, ..., uk-1 uk-2, ..., u1
yang memuat semua simpul di J.
Jika semua simpul di G telah berada di S, maka
S adalah sikel Hamilton dan G adalah graph Hamilton.
Misalkan ada suatu simpul w di G yang tidak
berada di S. Karena S memuat paling sedikit 1 + p/2 simpul, sebanyak kurang dari
p/2 simpul di G tidak berada di S. Karena der w > p/2, maka simpul w
harus berdekatan dengan suatu simpul uj di S. Akan tetapi, rusuk uwj
dan S membangun lintasan yang banyaknya simpul 1 lebih banyak daripada simpul-simpul
yang berada di J. Kondisi ini tidak mungkin terjadi sebab J memuat
simpul-simpul paling banyak. Kontradiksi ini berakibat bahwa S memuat semua
simpul di G, sehingga G adalah graph Hamilton.
Untuk menentukan keberadaan sirkuit Hamilton,
jika ada dapat dilakukan dengan cara mencoba-coba. Hal tersebut mudah jika untuk graph dengan banyak simpul sedikit. Akan
tetapi membuktikan bahwa tidak ada sirkuit Hamilton dalam suatu graph
yang diketahui, dapat menjadi sangat
sulit.
Kita akan memusatkan diri pada masalah bagaimana
menunjukkan bahwa tidak adanya sirkuit Hamilton dalam suatu graph. Tidak adanya
sirkuit Hamilton memerlukan sejenis sistem analisis logis. Berikut ini adalah tiga
aturan yang harus diikuti. Ide dasar dari aturan ini adalah bahwa dalam suatu sirkuit Hamilton
setiap simpul harus hanya ada dua rusuk yang bertemu padanya; dengan kata lain
setiap simpul dalam sirkuit Hamilton harus hanya berderajat dua. Detailnya
sebagai berikut :
Aturan 1. Jika simpul v berderajat 2, kedua rusuk yang bertemu di v harus
merupakan bagian dari sirkuit Hamilton.
Aturan 2. Tidak ada subsirkuit sejati, yakni sirkuit yang tidak memuat
semua simpul di dalam graphnya, tidak dapat dibangun apabila membangun sirkuit
Hamilton.
Aturan 3. Setelah sirkuit Hamilton kita bangun melalui suatu simpul w,
semua rusuk lain (yang tidak digunakan) yang bertemu di w dapat dibuang (karena
mereka tidak dapat digunakan lagi mengingat setiap simpul harus berderajat 2).
Perhatikan bahwa setelah membuang rusuk-rusuk
seperti dibenarkan dalam Aturan 3, kita kemudian dapat menggunakan Aturan 1.
Contoh 19
Tunjukkan
bahwa graph dalam Gambar 3.19, tidak mempunyai sirkuit Hamilton.
Penyelesaian
Menurut Aturan 1, simpul-simpul a, b, d, e
berderajat 2. Jadi rusuk-rusuk ini berada dalam sirkuit Hamilton. Hal ini
ditandakan dengan garis kecil seperti dalam gambar. Jadi rusuk-rusuk ac, ad,
dc, bc, bd harus dipakai dalam
sirkuit. Ada dua kontradiksi di sini.
Pertama: dengan digunakannya rusuk ac, ad, dan bc maka terjadilah subsirkuit.
Ini bertentangan dengan Aturan 3.
Kontradiksi kedua: Dengan harus digunakannya rusuk-rusuk ac, dc, bc, ec,
derajat simpul c menjadi 4 sehingga lebih dari 2, hal ini kontradiksi dengan
aturan 1. Kontradiksi yang manapun mengakibatkan bahwa graph dalam Gambar 3.19
tidak memuat sirkuit Hamilton.
Contoh 20
Tunjukkan bahwa graph dalam Gambar 3.20 bukanlah
graph Hamilton!
Bukti
Menurut Aturan 1,
simpul a, dan g harus masuk dalam
sirkuit, sebab berderajat 2, sehingga lintasan: b, a, c dan lintasan: e, g, i
harus menjadi bagian dari sirkuit. Perhatikan simpul i. Kita telah melihat
bahwa rusuk gi menjadi bagian dari sirkuit. Karena rusuk gi simetri terhadap
rusuk ij dan ik, tidak masalah apakah kita memilih salah satunya. Menggunakan
Aturan 3, kita buang rusuk ik, maka simpul k berderajat 2, sehingga menurut
Aturan 1, jk dan hk harus menjadi bagian dari sirkuit. Karena jk harus menjadi
bagian sirkuit, maka menurut Aturan 3, rusuk jf harus dibuang. Akibatnya
derajat simpul f menjadi 2. Maka di f, fe dan fb harus menjadi bagian dari
sirkuit. Dengan penambahan fe, maka
simpul e harus berderajat 2, jadi rusuk eh dan ed harus menjadi bagian sirkuit
(sebab rusuk eg telah ditetapkan ikut dalam sirkuit). Akibatnya simpul berderajat 2, sehingga rusuk kh dan hc harus menjadi
bagian sirkuit.
Gambar 3.20.
Sekarang terjadi kontradiksi. Perhatikan,
bahwa simpul d sekarang telah berderajat 2. Kita harus menggunakan rusuk db dan
ed sebagai bagian sirkuit. Tetapi dengan demikian terjadilah subsirkuit sejati
a, b, d, c, yang menurut Aturan 2 tidak dibenarkan. Jadi, graph dalam Gambar
3.20 bukan graph Hamilton.
1)
Buktikan Teorema 3.4, yaitu
multigraph G adalah terlacak jika dan hanya jika G terhubung dan tepat
mempunyai dua simpul ganjil
2)
Suatu multigraph terhubung
mempunyai tepat 4 buah simpul berderajat ganjil. Sifat apakah yang dimiliki
oleh multigraph ini?
3)
Buktikanlah bahwa suatu graph G
adalah graph Euler jika dan hanya jika G terhubung dan himpunan rusuk-rusuknya
dapat dipartisi ke dalam sikel-sikel!
4)
Misalkan G adalah graph. Lintasan
J di G disebut lintasan Hamilton jika J memuat setiap rusuk di G.
Pandanglah graph G dengan banyak simpul p > 2 sedemikian rupa
sehingga deg v > (p - 1)/2 untuk setiap simpul v di G. Buktikanlah
bahwa G memuat lintasan Hamilton!
5)
Perhatikanlah graph dalam Gambar
3.21 di bawah ini. Buktikanlah bahwa graph itu tidak memuat sirkuit Hamilton!
Petunjuk Jawaban Latihan
1)
Misalkan u dan v dua simpul di G
yang berderajat ganjil. Tambahkan rusuk uv, maka semua simpul di G sekarang
berderajat genap dan terhubung. Akibatnya, G memuat sirkuit Euler. Jika sirkuit
berawal di u, akan berakhir di u lagi. Tetapi jika rusuk uv dicabut kembali
maka terjadilah lintasan Euler yang berawal di u dan berakhir di v. Sebaliknya,
pandang G terhubung dan terlacak, yakni, terdapat lintasan Euler. Jika
ditambahkan rusuk uv maka terjadilah sirkuit Euler. Jadi G terhubung dan semua
simpul berderajat genap. Jika rusuk uv dicabut kembali, maka akibatnya simpul u
dan v berderajat ganjil.
2)
Graph G terhubung dan mempunyai 4
rusuk berderajat ganjil. Misalkan simpul-simpul ini u, v, x, dan y. Pandang G
dan uv. Graph ini mempunyai lintasan Euler dengan rusuk uv sebagai salah satu rusuknya. Lintasan ini
berawal di x dan berakhir di y. Dengan penalaran yang sama, terdapat lintasan
yang berawal di u dan berakhir di v dengan rusuk xy berada di dalamnya.
Sekarang rusuk xy dan uv dicabut kembali.
Kesimpulan: di G terdapat dua
lintasan yang dua rusuknya saling asing.
3)
Jika G terhubung dan himpunan
rusuknya dapat dipartisi ke dalam sikel-sikel, maka setiap simpul v di G
termuat dalam sejumlah sikel. Jika sikel-sikel digabung mengikuti simpul c,
maka terjadilah sirkuit Euler. Konversinya: Jika G graph Euler, maka G
memuat sirkuit Euler. Setiap sirkuit memuat suatu sikel.
4)
Buatlah graph H dari graph G
dengan cara menambahkan satu simpul w dan hubungkan w dengan setiap simpul pada
G. Maka graph H mempunyai sebanyak p’
simpul = p + 1, dengan
p > 2, dan
setiap simpul di H berderajat > 1 + (p - 1)/2 = (p + 1)/2 = p’/2.
Jadi graph H memenuhi Teorema 3.5, sehingga H merupakan graph Hamilton.
5)
Perhatikan mana rusuk-rusuk yang
harus dibuang. Anda tinggal menetapkan terjadinya kontradiksi.
Graph Euler ialah graph yang memuat sirkuit
Euler. Sirkuit Euler adalah sirkuit yang memuat semua simpul dan semua rusuk
graph itu. Sirkuit adalah lintasan (tidak mengulang rusuk) yang bertemu simpul
awal dan simpul akhir. Suatu graph G adalah graph Euler jika dan hanya jika G
terhubung dan semua simpulnya berderajat genap. Graph G adalah terlacak jika
dan hanya jika G terhubung dan memuat tepat dua simpul berderajat ganjil.
Sikel adalah sirkuit yang tidak mengulang simpul,
terkecuali simpul awal dan akhir. Graph G adalah graph Hamilton jika G memuat
sikel Hamilton. Sikel Hamilton adalah sikel yang memuat semua simpul di dalam
graphnya. Jika graph G mempunyai simpul p > 3 dan derajat tiap simpul
di G > p/2, maka G adalah graph Hamilton. Ingatlah bahwa pernyataan
ini bukan diimplikasi. Sampai saat ini belum diketemukan syarat perlu dan
cukup untuk graph Hamilton.
 |
1) Graph
G dalam Gambar 3.22 adalah ....
A. graph
Euler
B. graph
terlacak
C. graph
Hamilton
D. graph
sebarang
2) Graph
H dalam Gambar 3.22 di atas (pada soal 1) adalah ....
A. graph
Euler
B. graph
terlacak
C. graph
Hamilton
D. graph
sebarang
3) Graph
I dalam gambar 3.22 dia tas (pada soal 1) adalah ....
A. graph
Euler
B. graph
terlacak
C. graph
Hamilton
D. graph
sebarang
4) Graph J dalam gambar 3.22 di atas (pada soal
1) adalah ....
A. graph
Euler
B. graph
terlacak
C. graph
Hamilton
D. graph
sebarang
5) Misalkan
G1 dan G2 adalah dua buah graph Euler yang tidak
bersekutu satu simpul pun. Misalkan v1 sebuah
simpul di G1 dan v2 sebuah simpul di G2. Misalkan G adalah graph yang terdiri
atas G1 dan G2, bersama-sama dengan rusuk v1v2. Maka graph
g adalah ....
A. graph
Euler
B. graph
terlacak
C. graph
Hamilton
D. graph
sebarang
6) Pernyataan
berikut ini yang benar adalah ....
A. setiap
graph Euler adalah graph Hamilton
B. setiap
graph Hamilton adalah graph Euler
C. setiap
graph Hamilton adalah graph terlacak
D. setiap
graph Euler adalah graph terlacak
7) Yang
manakah di antara multigraph atau graph berikut adalah terlacak?
A. G
B. H
C. K
D. G
dan K
8) Manakah
di antara graph berikut ini yang memuat sirkuit Hamilton?
A. G
B. H
C. G
dan H
D. K
9) Manakah
di antara graph pada soal no. 8 yang memuat lintasan Hamilton?
A. A
B. H
C. K
D. H
dan K
10) Perhatikan
graph G dalam gambar di bawah ini: Graph G bukan graph Hamilton sebab
A. menurut
Teorema 3.5, banyaknya simpul di G, p = 7, derajat setiap simpul deg v >
p/2 = 7/2, tidak dipenuhi. Jadi G bukan graph Hamilton
B. banyaknya
simpul ganjil 0 buah, jadi G bukan graph Hamilton
C. rusuk
ac, fc, dan gc harus menjadi bagian dari sirkuit, sehingga simpul c terpaksa
memuat tiga rusuk. Jadi tidak memuat sirkuit Hamilton
D. semua
simpul berderat genap, jadi G pasti graph Hamilton
Cocokkanlah jawaban
Anda dengan Kunci Jawaban Tes Formatif 2 yang terdapat di bagian akhir modul
ini. Hitunglah jawaban yang benar. Kemudian, gunakan rumus berikut untuk
mengetahui tingkat penguasaan Anda terhadap materi Kegiatan Belajar 2.
|
Arti tingkat penguasaan: 90 - 100% = baik sekali
80
- 89%
= baik
70 - 79% =
cukup
< 70% = kurang
Apabila mencapai
tingkat penguasaan 80% atau lebih, Anda dapat meneruskan dengan modul
selanjutnya. Bagus! Jika masih di
bawah 80%, Anda harus mengulangi materi Kegiatan Belajar 2, terutama bagian
yang belum dikuasai.
Kunci Jawaban Tes Formatif
Tes Formatif 1
1) D. G2 dan G4
2) D. paling banyak = p
3) A. lintasan dan bukan lintas
4) C. sirkuit
5) A. perjalanan; mengulang susuk dan simpul
6) D. 3: d, e, f
7) C. 2: ad, ef
8) A. 6 simpul
9) A. 19
10) B. 21
Tes Formatif 2
1) B. graph lacak
2) D. graph sebarang
3) A. graph sebarang
4) C. graph Hamilton
5) B. graph lacak.
6) D. setiap graph Euler adalah graph lacak
7) D. G dan K
8) D. G. K
9) D. K
10) C. menurut Aturan 1
Daftar Pustaka
Bradley, J. (1988). Introduction to Discrete Mathematics, New
York: Addition Wesley
Chartrand, Garry, 1985. Introductory Graph
Theory. New York: Dover.
Chartrand, Garry, dan Lesniak, Linda. 1986. Graphs
& Digraphs. Second Edition. belmont, California: Wadsworth. Inc.
Lipschutz, Seymour, 1976, Discrete Matemathics.
Schaum’s Outline Series. New York: McGraw-Hill.
Liu, C.H. 1985. Elements of Discrete
Matematics. New York: McGraw-Hill.
Tucker, Alan,
1984. Applied
Combinatorics.
Second Editon. New York: Hohn Wiley.
.jpg)
0 komentar:
Posting Komentar