Nila Widhianti
09305141014
JEMBATAN
KONIGSBERG
1. Pendahuluan
Konigsberg, sebuah kota
di bagian utara Jerman, memiliki
sebuah kisah terkenal
yang memberikan pengaruh besar
pada kehidupan seorang bernama
Euler dan sejarah perkembangan teori Graf. 
Teka-Teki
Jembatan Konigsberg
Sungai
Pregel yang melalui
Konigsberg membagi wilayah daratan
pada kota tersebut menjadi empat
bagian. Tujuh buah
jembatan dibangun di
atas sungai tersebut
pada bagian yang memungkinkan
untuk bepergian antar keempat
wilayah tersebut. Pada
abad ke-17, warga Konigsberg
gemar berjalan di tepi sungai, hingga
akhirnya beberapa dari
mereka memikirkan apakah
mungkin untuk berjalan
di Konigsberg dan melalui setiap
jembatan hanya sekali. Teka-teki
tersebut menarik perhatian Euler, yang
diyakini ketika itu berada di St. Petersburg. Ia kemudian meneliti bahwa
kasus tersebut dapat direpsersentasikan dalam sebuah diagram
seperti pada Gambar 2.1.
Pembahasan
Pada
tahun 1736, seorang
pakar matematika ternama,
Leonard Euler, menulis sebuah
artikel yang membahas tidak hanya solusi atas teka-teki Konigsberg semata, akan
tetapi juga delengkapi dengan metode
umum untuk persoalan
serupa lainnya dalam artikel yang
berjudul asli "Solutio Problematis
Ad Goemetriam Situs Pertinetis". Selanjutnya akan didefinisikan terminologi
langkah dari pembuktian Euler.
Dalam pembuktiannya, Euler menggunakan
simpul, sisi dan sirkuit.
Setelah
diketahui definisi lintasan, lintasan tidak
sederhana, sirkuit dan
lintasan tertutup, akan ditelaah
dua teori Euler dengan
pembuktiannya mengunakan sejumlah prinsip paling
mendasar dalam teorema
graf yang diperkenalkan oleh
Euler sendiri. Seperti yang
Euler jelaskan sebelumnya,
teka-teki jembatan
Konigsberg dapat direpresentasikan dalam bentuk
diagram [gambar 2.1].
Euler membuat sebuah titik
untuk setiap wilayah daratan, kemudian
menambahkan garis antara setiap
titik tersebut sebagai
pengganti jembatan yang
menghubungkan mereka.
Dengan demikian, dengan melihat
graf tersebut, kita dapat memulai dari
titik a kemudian ke b, d, c, b, a, b,
akan tetapi tidak
terdapat cara untuk kembali
ke simpul a, karena d memiliki derajat sisi genap
(jumlah sisi yang
menghubungkan simpul). Dengan demikian,
jelaslah bahwa teka-teki Konigsberg
adalah mustahil, dan
hal ini membuat Euler
mempresentasikan teori Graf Euler hasil pemikirannya. Metode ini
juga dapat digunakan untuk Graf Terhubung Langsung.
Euler
gagal menunjukkan bahwa
jika setiap simpul dari
graf terhubung G bernilai
bilangan genap, maka G
bersifat Eulerian . Hingga akhirnya pada
tahun 1873, Carl
Hierholzer berhasil
melengkapi pembuktian Euler tersebut. Teorema dan
pembuktian Holzier yang menampilkan sebuah
cara yang brilian
untuk menunjukkan kenapa dan
bagaimana teorema tersebut
berlaku adalah sebagai berikut :
Teorema
1:
Sebuah graf terhubung
tidak sederhana G bersifat
Eulerian jika dan
hanya jika setiap simpul memiliki derajat bernilai
genap.Bukti Pertama-tama mari kita
anggap bahwa G bersifat Eulerian. Kemudian G mengandung
sebuah sirkuit Euler
C. Anggap C
dimulai pada simpul u
(dan, dengan demikian, berakhir di
u). Akan dibuktikan
bahwa setiap simpul G
memiliki derajat bernilai genap. Sebut v sebuah simpul lain
pada graf G, karena C tidak dimulai
maupun berakhir pada v, maka setiap
kali u ditemukan
pada C, akan ada dua buah sisi yang terlibat (satu untuk memasuki v dan
satu yang lain untuk meninggalkan v).
Dengan demikian, dapat kita
simpulkan bahwa v
memiliki derajat bernilai genap.
Karena C dimulai
dan berakhir pada u, maka
terdapat sebuah sisi yang
berawal dari u
dan sebuah sisi
lagi yang berakhir pada
u. Jika kemudian
u muncul kembali, maka akan bertambah dua buah sisi, sehingga u juga
berderajat genap.Sebaliknya, anggap bahwa
G merupakan sebuah graf
terhubung tidak sederhana dengan setiap
simpulnya memiliki derajat bernilai genap.Akan
ditunjukkan bahwa G
mengandung sebuah sirkuit
Euler.Darisemua di G,
pandang T sebagai
yang terpanjang. Anggap T sebagai sebuah
u – v. Maka, setiap kali kita menemui T, kita akan menemui dua sisi G,
yang pertama untuk memasuki v
dan yang kedua
untuk meninggalkan v. Karena T berakhir
pada v dan jumlah
sisi v yang
bernilai ganjil telah diperhitungkan. Akan tetapi, jika v
memiliki derajat bernilai genap, maka akan ada paling sedikit sebuah
sisi di v, sebut
sebagai vw, yang tidak
muncul di T.
Kana tetapi kemudian T
dapat diperpanjang hingga
w, bertentangan dengan asumsi
bahwa T memiliki panjang yang
maksimum.
Karena T merupakan sebuah u-u, dengan C = T adalah sebuah
sirkuit. Maka jika C
mengandung semua sisi
G, maka C adalah sebuah
sirkuit Euler dan
pembuktian ini selesai.Kemudian jika C
tidak mengandung semua sisi dari G, maka
akan ada sejumlah sisi G yang
tidak terdapat pada
C. Karena G terhubung, maka sejumlah
sisi e = xy tidak pada
C adalah sebuah
kebetulan dengan simpul x
pada C. Ambil
H = G
– E(C), sehingga H merupakan
subgraf dari G yang diperoleh
dengan menghilangkan sisi
C. Setiap simpul C muncul ketika
jumlah sisi pada C bernilai
genap.Karena setiap simpul di
G juga memiliki
derajat genap, maka begitu
pula dengan H,
dengan catatan H mungkin
saja tidak terhubung. Dengan kata lain, H
paling sedikit memiliki
satu komponen tidak sederhana,
sebut sebagai H1, yang
dimulai dari x.
Seperti yang baru saja kita lihat,
tersebut harus berakhir di x
dan merupakan sebuah
sirkuit x –
x di C' pada H1.Jika kita
ingin memasukkan C' ke dalam sirkuit
C, maka ketika
kita tiba di
x, kita menemukan sebuah
sirkuit C'' pada G
dengan panjang melebihi
C, yang dalam kasus kali ini merupakan sebuah
kontradiksi. Hal ini menunjukkan bahwa C
engandung setiap sisi dari G dan
merupakan sebuah sirkuit Euler.
Teorema
2
Sebuah graf terhubung
G mengandung lintasanEuler jika
dan hanya jika
tepat dua simpul pada G memiliki
derajat ganjil. Sehingga, setiap lintasan Euler pada G dimulai di salah satu
dari kedua simpul berderajat
ganjil tersebut dan berakhir pada simpul yang satunya. Bukti Pertama-tama
anggap bahwa G mengandung sebuah
lintasan Euler T.
Sehingga T merupakan sebuah
lintasan u –
v untuk sepasang simpul u dan v
tertentu. Kemudian kita membentuk sebuah
graf terhubung H dari
graf G dengan
menambahkan sebuah simpul baru
berderajat dua pada graf G dan menggabungkannya dengan simpul u dan v.
Dengan demikian, C:
T,x,u adalah sebuah sirkuit euler
di H. Berdasarkan Teorema 1, setiap simpul H berderajat genap dan hanya
u dan v yang memiliki derajat ganjil di G = H – x.Sebagai kebalikannya,
kita lakukan dengan kasus
serupa. Anggap G
sebuah graf terhubung yang
mengandung tepat dua simpul u
dan v yan
berderajat ganjil. Akan
ditunjukkancbahwa G mengandung
sebuah lintasan Euler T, di mana T adalah lintasan u – v
atau v –
u. Tambahkan sebuah
simpul baru x berderajat
dua ke G dan
gabungkan dengan u dan
v, sehingga menghasilkan sebuah graf H. Dengan demikian,
H adalah sebuah graf terhubung
dengan semua simpulnya berderajat
genap. Berdasarkan teorema 1, H merupakan sebuah
graf Euler yang mengandung sirkuit
Euler C. Karena simpul
manapun yang menjadi
awal dan akhir sirkuit
tidak menjadi masalah,
maka kita asumsika bahwa
salah satu sisi sebagai
awal sirkuit C dan satu sisi yang lain sebagai akhirnya. Menghapus
x dari C akan
menghasilkan sebuah lintasan Euler T pada G
yang dimulai dari
salah satu di
antara u dan v dan berakhir di
satu yang lainnya. Tidak ada teori
lain selain yang
dikemukakan oleh Euler yang
telah memberikan kontribusi luar biasa
di bidang Teorema
Graf.
Kesimpulan
Teka-Teki Jembatan
Konigsberg telah memberikan
dampak dalam perkembangan Ilmu Matematika .
Teka-teki tersebut telah membuka
jalan bagi terciptanya
teorema baru yang disebut teorema
graf. aplikasi teorema graf sangat beragam di bidang ilmu pengetahuan dan teknologi. Solusi permasalahan
pada Teka-Teki Tujuh Jembatan Konigsberg
dapat diperoleh dengan menganalogikan setiap jembatan sebagai
sisi dan setiap daratan sebagai simpul pada graf, sehingga terbentuk sebuah
graf lengkap. Dan
dengan memperhitungkan derajat dari setiap simpul yang terdapat dalam
graf, menggunakan metode yang diungkapkan dalam pembuktian di atas, kita akan
dapat mengetahui apakah
graf tersebut merupakan suatu
lintasan di mana
setiap sisi dilalui hanya satu
kali saja.Fakta bahwa teorema
graf lahir ketika
Euler menyelesaikan masalah berdasarkan
Teka-Teki Jembatan
Konigsberg menyatakan hubungan tersediri antara
jaringan spasial (seperti
jalur transportasi) dengan graf.
Dengan kelahiran teorema
graf, banyak teorema
lain dikembangkan, dan terdapat
sejumlah besar aplikasi penggunaan
teorema graf. Salah satunya adalah Teka-Teki
Tukang Pos Cina
yang terkenal, di mana dengan berbagai variasi, dapat digunakan di
aplikasi lain. Salah satu contohnya
adalah metode pengumpulan
sampah dan pembersihan jalan, pembersihan salju, pelukisan garis
pada ruas jalan, sistem patroli mobil polisi, metode pengambilan
sensus dan pengaturan sistem jaringan komputer.
Daftar
Pustaka
I.
Chartrand, Gary (2005), Introduction to
Graph Theory, pp, 133-138.
II.
Gross, Jonathan (1999), Graph Theory and
Its Applications, pp, 208-119.
III.
Hartsfield, Nora (1990), Pearls in Graph Theory A comprehensive introduction,
pp, 49-55.
IV.
Harary, Frank, (1972), Graph Theory,
pp, 64-65, 204.
V.
Wilson J. Robin, (1976), Graph Theory
1936-1936, pp, 2-20.
VI.
Guan, Meigu, (1962), Graphic programming
usind odd and even points, Chinese Math, pp, 273- 274.
VII.
Edmonds, J. and Johnson, E. (1973),
Matching Euler tours and the Chinese
postman, Math. Programming 5, pp,
88-124.
VIII.
Hierholzer, C. (1873), Uber die
Moglicheit, einen Linienzug ohne Wiederholung und ohne Unterfrechnung zu umfahren. Math. Ann. 6,
pp, 30- 32.
Tidak ada komentar:
Posting Komentar