JEMBATAN KÖNIGSBERG Puji Nugraheni Jurusan Pendidikan Matematika FKIP Universitas Muhammadiyah Purworejo
Abstrak Berbagai permasalahan dalam kehidupan sehari-hari dapat dimodelkan dengan menggunakan diagram titik dan garis atau dalam matematika lebih dikenal dengan sebutan graf. Titik dalam graf dinamakan simpul dan garisnya dinamakan sisi. Penggunaan graf pertama kali adalah pada permasalahan Jembatan Königsberg pada tahun 1736. Permasalahan Jembatan Königsberg adalah apakah mungkin melewati ketujuh jembatan sebanyak satu kali untuk kembali ke tempat semula. Permasalahan ini telah dipecahkan oleh ahli matematika dari Swiss bernama L. Euler pada tahun 1736. Dalam penemuannya Euler mengemukakan bahwa untuk dapat melewati semua jembatan sebanyak satu kali dan kembali ke tempat semula, maka grafnya harus merupakan graf Euler yaitu graf yang memuat sirkuit Euler. Sedangkan syarat keberadaan sirkuit Euler menurut Euler adalah derajat setiap simpulnya harus genap. Graf yang merepresentasikan permasalahan Jembatan Königsberg mempunyai simpul yang semuanya berderajat ganjil, sehingga tidak mungkin melewati semua jembatan sebanyak satu kali untuk kembali ke tempat semula Kata Kunci: jembatan Königsberg, graf Euler Pendahuluan Dalam suatu model mate-
sehari-hari adalah diagram titik dan
matika, berbagai masalah dalam
garis. Pada dasarnya banyak sekali
kehidupan
biasanya
masalah nyata yang dapat diwakili
diidentifikasi kemudian dinyatakan
dengan diagram titik dan garis,
dalam suatu sistem yang bersifat
diantaranya penyampaian suatu berita
matematis. Salah satu bentuk model
atau
matematika
pengantaran surat, penyusunan trayek
nakan
sehari-hari
yang
untuk
dapat
dipergu-
merepresentasikan
berbagai masalah dalam kehidupan
gosip
pedagang
agar keliling,
tersebar
luas,
peran-cangan
jaringan kereta api, telekomunikasi,
Puji Nugraheni: Jembatan Konigsberg 21
komputer, penyaluran bahan bakar,
sungai. Ada tujuh buah jembatan
perancangan arena pameran atau
yang menghu-bungkan daratan yang
tempat rekreasi agar pengunjung
dibelah oleh sungai tersebut seperti
dapat melihat semua stan atau atraksi
terlihat dalam gambar berikut:
hi-buran tanpa melewati ulang jalur
A
yang sama dan masih banyak lagi permasalahan yang lainnya. Pada contoh diatas ibu rumah tangga, rumah, kota, stasiun, sentral tele-pon,
B
pusat informasi, komputer, POM
D
bensin dan stand dapat digambarkan sebagai
titik
keakraban,
dan jalan,
hubungan prasa-rana
hubungan, jalur komunikasi, kabel
C
dapat diwakili oleh garis. Diagram titik dan garis seperti di atas dalam model matematika dike-nal sebagai graf.
Menurut
permasalahan
catatan
sejarah,
pertama
yang
menggunakan graf adalah permasalahan Jembatan Königsberg pada tahun 1736. Jembatan Königsberg merupakan jembatan yang terletak di Kota Königsberg sekarang bernama Kota Kaliningrat (sebelah timur Prussia, Jerman sekarang), di kota tersebut terdapat Sungai Pregal yang mengalir mengitari
Pulau
Kneiphof
lalu
bercabang menjadi dua buah anak
Masalah Jembatan Königsberg adalah apakah mungkin mela-lui ketujuh buah jembatan itu ma-singmasing tepat satu kali dan kembali lagi ke tempat semula. Sebagian penduduk
kota
sepakat
bahwa
memang tidak mungkin melalui setiap jembatan
itu
hanya
sekali
dan
kembali ke tempat semu-la, tetapi mereka tidak dapat menje-laskan mengapa
demikian
jawaban-nya
kecuali dengan cara coba-coba. Tahun 1736, seorang Matematikawan Swiss, L. Euler adalah orang pertama yang berhasil mene-
22 Puji Nugraheni: Jembatan Konigsberg
mukan jawaban masalah Jembatan
Terminologi Graf
Königsberg ini dengan menggu-nakan
Graf
pembuktian
yang
sebagai
Ia
pasangan himpunan (V,E) dengan V
memodelkan masalah ini ke da-lam
adalah himpunan berhingga dan tidak
graf. Daratan yang dihubung-kan oleh
kosong dari simpul-simpul (vertex)
jembatan dinyatakan seba-gai titik
dan E adalah himpunan sisi (edges)
dan jembatan disimbolkan sebagai
yang
garis.
simpul (Rinaldi Munir,2001). Secara Representasi
sederhana.
didefinisikan
graf
menghubungkan
sepa-sang
untuk
geometri graf digambarkan sebagai
Jembatan Königsberg adalah seba-gai
kumpulan noktah (simpul) di dalam
berikut :
bidang yang dihubungkan dengan A
sekumpulan garis (sisi). Dua buah simpul dikatakan B
D
adjacent bila keduanya terhubung langsung dan sebuah sisi dikatakan berincident dengan kedua simpul
C oleh
Jawaban yang dikemukakan
yang
Euler
adjacent dengan v q maka sisi yang
adalah
orang
tidak
dihubungkannya.
Jika
vp
mungkin melalui ketujuh jembatan itu
incident
masing-masing satu kali dan kembali
tersebut dapat ditulis ( v p , v q ). Pada
ke tempat semula jika derajat setiap titik tidak seluruhnya genap. Yang dimaksud derajat adalah banyaknya garis yang ber-sisian dengan titik. Penemuan Euler tentang pemecahan permasalahan Jembatan Königsberg akan memun-culkan teori tentang graf Euler yang akan dibahas lebih lanjut dalam tulisan ini.
dengan
kedua
simpul
suatu graf juga dikenal derajat (degree) suatu simpul yaitu banyaknya sisi yang berincident dengan simpul tersebut. Sisi pada graf dapat mempunyai orientasi arah. Berdasarkan orientasi arah pada sisi, Rinaldi Munir (2001) membedakan graf atas dua jenis, yaitu:
Puji Nugraheni: Jembatan Konigsberg 23
D
1. Graf Tak Berarah (Undirected
C
Graph) jika sisinya tidak mempu-nyai
B
A
Suatu graf dikatakan tak bera-rah
Gambar 2 (b) Graf berarah
orientasi arah.
Pada suatu graf G juga di-
Pada graf tak berarah, urutan
kenal adanya lintasan dari simpul v p
pasangan simpul yang dihu-
ke
bungkan oleh sisi tidak diperhatikan atau
yaitu
vq
p
2. Graf Berarah (Directed Graph
simpul
v p , v i1 , v i 2 ,..., vim , v q sehingga
(v , v ), (v v ),...,(v
( v p , v q ) = ( v q , v p ).
i1
i1
i2
im
, vq
)
adalah
sisi
pada graf G. Contoh: Diketahui graf G
atau Digraph)
pada gambar 3
Graf yang setiap sisinya diberikan
rangkaian
orientasi
arah
A
disebut
sebagai graf berarah. Pada graf berarah urutan pasangan sim-pul yang
dihubungkan
oleh
B
sisi
C
diperhatikan atau
D
( v p , v q ) ≠ ( v q , v p ). Berikut merupakan contoh graf tak berarah dan graf berarah: D
C
A
B
Gambar 2 (a) Graf tak
Lintasan pada graf G diatas adalah lintasan A, B, C, D. Pada lintasan ini simpul A dinamakan simpul awal (initial vertex) dan D dinamakan simpul akhir (terminal vertex).
berarah
Suatu
lintasan
dikatakan
lintasan sederhana (simple path) ji-ka 24 Puji Nugraheni: Jembatan Konigsberg
tidak
melalui
sama
himpunan V terdapat lintasan dari v p
sebanyak dua kali dan suatu lin-tasan
ke v q . Jika tidak demikian, maka G
dikatakan
sisi
yang
lintasan
elementer
(elementary path) jika tidak melalui simpul yang sama sebanyak dua kali. Lintasan dengan simpul awal sama dengan simpul akhir disebut sirkuit. Berdasarkan
lintasannya,
maka
sirkuit dibedakan menjadi dua yaitu
disebut
graf
(disconnected
tak
terhubung
graph).
Sedangkan
untuk graf berarah dikatakan terhubung
jika
graf
tak
berarahnya
terhubung. Contoh : A
sirkuit sederhana (simple sircuit) jika sirkuitnya tidak melalui sisi yang
B
C
sama sebanyak dua kali dan sirkuit elementer (elementary circuit) jika sirkuitnya tidak mela-lui simpul yang
D
Gambar 4 (a) Graf tak berarah terhubung
sama sebanyak dua kali. Contoh :
E
B
Pada gambar 3, A, B, C, A adalah sirkuit sederhana dan juga sirkuit
A
D
elementer, sedangkan A, B, D, C, B, C
A bukan sirkuit sederhana dan juga
jika
G
tidak terhubung
Dua simpul v p dan simpul v q terhubung
H
Gambar 4 (b). Graf tak berarah
bukan sirkuit elementer.
disebut
F
terdapat
D
lintasan dari v p ke v q .Graf tak
C
berarah G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul v p dan v q dalam
A
B
Gambar 5 (a)Graf berarah terhubung
Puji Nugraheni: Jembatan Konigsberg 25
dimulai dengan masalah Jem-batan B
Königsberg.
E
A
mele-wati
setiap Jembatan Königsberg sebanyak
D F
C
Perjalanan
Gambar 5 (b)Graf berarah tidak terhubung Anak graf (subgraph) dari graf G = (V,E) adalah graf G1 = (V1,E1) dengan V1 V dan
E1 E .
sekali
dan
keberangkatan
kembali
ke
tempat
membentuk
sirkuit
yang diberi nama sirkuit Euler. Jika perjalanan melewati ketujuh jembatan itu titik harus kembali ke tempat keberangkatan
maka
akan
membentuk lintasan Euler. Sehingga lintasan Euler ada-lah lintasan yang melalui masing-masing sisi dalam
Contoh :
graf tepat satu kali. Sedangkan sirkuit B
A
Euler ada-lah sirkuit yang melewati C
D
masing-masing sisi tepat satu kali. Graf yang mempunyai sirkuit Euler
E
disebut graf Euler (Eulerian graph)
Gambar 6 (a) Graf G
dan graf yang mempunyai lintasan Euler dinamakan graf semi-Euler
A
C D
(semi-Eulerian graph). Contoh:
E
B
A
C
D
Gambar 6 (b) Graf G1 (anak graf dari G) Graf Semi Euler dan Graf Euler Pada awal tulisan ini sudah dipaparkan tentang sejarah graf yang 26 Puji Nugraheni: Jembatan Konigsberg
Gambar 7 (a) Graf semi-Euler tak berarah
B
Pembuktian
C E
A
tersebut
adalah:
D
Pembuktian
untuk
syarat
perlu. Misalkan G memiliki lin-tasan
G
F
penyataan
Euler,
Gambar 7 (b) Graf Euler tak
G
jelas
terhubung.
Jika
lintasan Euler dilalui, maka pada
berarah
setiap simpul terdapat dua sisi yang graf
ber-incident, kecuali pada simpul
Gambar 7 (a) : C, A, B, C, D, A.
awal dan simpul akhir. Jadi setiap
Sirkuit Euler pada graf Gambar 7 (b)
simpul selain simpul awal dan sim-
: A, B, C, D, G, C, E, G, F, E, B, F,
pul akhir harus berderajat genap. Jika
A.
simpul awal dan simpul akhir sama
Lintasan
Euler
pada
Syarat perlu dan cukup me-
maka terbentuk sirkuit Euler. Pembuktian
ngenai keberadaan lintasan Euler
untuk
syarat
maupun sirkuit Euler di dalam sua-tu
cukup. Misal dibuat lintasan Euler
graf ternyata sangat sederhana. Euler
mulai dari salah satu dari dua simpul
menemukan syarat tersebut ketika
yang berderajat ganjil dan akan
memecahkan
melewati semua sisi pada graf itu
masalah
Jemba-tan
sehingga tidak ada sisi yang dilewati
Königsberg. Hasil penemuan Euler ten-tang
lebih dari sekali. Untuk simpul yang
keberadaan lintasan Euler dipaparkan
berderajat genap, bila lintasan itu
kembali oleh Liu, C L (1985) sebagai
masuk ke simpul me-lewati sebuah
berikut:
sisi,
Suatu graf tak berarah memiliki
meninggalkan simpul itu melewati
lintasan Euler jika dan hanya jika ia
sisi
terhubung (connected) dan memiliki
pembuatan lintasan berakhir, pasti
nol atau dua simpul berderajat
telah sampai pada simpul
ganjil.
berderajat ganjil lainnya. Jika semua
maka yang
ia
selalu
lain.Sehingga
bisa ketika yang
Puji Nugraheni: Jembatan Konigsberg 27
sisi didalam graf itu dilewati dengan
berderajat genap. Sehingga jelaslah
cara ini maka jelas akan diperoleh
masalah Jembatan Königsberg bah-
lintasan Euler. Jika tidak semua sisi
wa tidak mungkin melalui ketujuh
di dalam graf itu terl-ewati, sisi-sisi
buah jembatan itu masing-masing
yang tidak terlewati itu dianggap
tepat satu kali dan kembali lagi ke
sebagai anak graf, sehingga semua
tempat semula karena jika Jem-batan
simpul yang terda-pat dalam anak
Königsberg direpresentasikan dalam
graf ini berderajat genap. Dengan
sebuah graf, graf tersebut tidak
diawali dari salah satu simpul pada
memiliki sirkuit Euler dise-babkan
anak graf tersebut, sekali lagi dibuat
semua simpulnya berderajat ganjil.
lintasan yang melalui semua sisi-sisi
Lintasan dan sirkuit Euler
pada anak graf. Karena semua simpul
juga terdapat pada graf berarah.
berde-rajat genap, maka pasti lintasan
Berikut pemaparan Rinaldi Munir
pada anak graf itu akan kembali ke
(2001) tentang keberadaan lintasan
simpul awal. Dari penggabungan
dan sirkuit Euler pada graf berarah:
lintasan yang pertama dan kedua akan
Graf berarah G memiliki sirkuit
diperoleh lintasan yang bera-wal dan
Euler jika dan hanya jika G terhu-
berakhir pada simpul yang berderajat
bung dan setiap simpul memiliki
ganjil. Jika diperlukan, cara ini dapat
derajat-masuk
diulang sampai diperoleh lintasan
sama. G memiliki lintasan Euler jika
yang melalui semua sisi pada graf
dan hanya jika G terhubung dan
tersebut.
setiap simpul memiliki derajat-masuk
Berdasarkan hasil teori ten-
dan
derajat-keluar
dan derajat-keluar sama kecuali dua
tang keberadaan lintasan Euler di
simpul,
atas, akan diperoleh akibat bahwa
derajat-keluar
satu
lebih
besar
graf tak berarah G adalah graf Euler
derajat-masuk
dan
yang
kedua
(memiliki sirkuit Euler) jika dan
memiliki derajat-masuk satu lebih
hanya
besar dari derajat-keluar.
jika
setiap
simpulnya
28 Puji Nugraheni: Jembatan Konigsberg
yang
pertama
memiliki
Contoh :
pameran dan permasalahan tukang
D
pos.
C
1. Jalur pengunjung pameran A
Contoh
B
sederhana
dari
masalah ini adalah misalkan pada
Gambar 8 (a) Graf semi-
suatu gedung terdapat enam stan
Euler yang berarah
yang akan diguna-kan untuk pameran.
A
F E
G
Masing-masing
stan
dihubungkan oleh beberapa pintu
B
dengan stan yang lain, lebih jelasnya denah gedung seperti
D C
gambar berikut:
Gambar 8 (b) Graf Euler yang berarah Lintasan Euler pada graf Gambar 8 (a) : D, A, B, D, C, B. Gambar 9
Sirkuit Euler pada graf Gambar 8 (b) : A, G, C, B, G, E, D, F, A.
Permasalahannya ada-lah Penerapan Graf Semi-Euler dan
apakah
mungkin
Graf-Euler
pengunjung
pameran
setiap dapat
dalam
melihat semua stan tanpa harus
permasalahan jembatan Königs-berg,
melewati jalan yang sama dan
graf Euler juga dapat digu-nakan
jika mungkin bagaimana jalur
untuk menyelesaikan perma-salahan
tersebut. Permasalahan ini da-pat
yang lain diantaranya yang akan
diselesaikan
dibahas adalah jalur pengun-jung
gunakan
Selain
digunakan
graf,
dengan
meng-
masing-masing
Puji Nugraheni: Jembatan Konigsberg 29
stan diwakili oleh simpul dan
melewati jalan yang sama un-tuk
pintu
menghubungkan
denah tempat pameran seperti
antara dua stan diwakili oleh sisi.
pada gambar 9. Salah satu jalur
Sehingga
yang
yang
permasalahan
ini
dapat
dilewati
oleh
adalah apakah di dalam graf
pengunjung adalah masuk ke stan
tersebut terdapat lintasan Euler,
A, stan D, stan E, stan B, stan C,
jika terdapat bagaimana contoh
stan F, kemudian keluar. 2. Permasalahan tukang pos
lintasan Eulernya.
Permasalahan ini perta-
Representasi graf Gambar 9:
ma kali dikemukakan oleh Mei
Gambar10
Gan (dari Cina) pada tahun 1962.
G
A
B
C
Ia mengemukakan per-masalahan yaitu seorang tu-kang pos akan mengantar surat ke alamat-alamat
E
D
F
sepanjang jalan di suatu daerah. Bagai-mana ia merencanakan rute
graf
perjalanannya supaya ia mele-wati
yang diperoleh, terdapat dua
setiap jalan tepat satu kali dan
simpul berderajat ganjil yaitu
kembali lagi ke tempat awal
simpul G dan F, sedangkan
keberangkatan.
Dari
representasi
simpul yang lainnya berderajat
Permasalahan
ini
tidak
syarat
lain adalah menentukan sirkuit
keberadaan lintasan Euler pada
Euler di dalam graf yang mere-
genap.
Sesuai
penjelasan
dengan
sebelumnya,
maka
pasti terdapat lintasan Euler pada graf
tersebut
pengunjung melihat
presentasikan peta jalan tempat tukang pos mengantar surat. Jika grafnya merupakan graf Euler
atau
setiap
pameran
dapat
maka, maka sirkuit Eulernya
tanpa
mudah ditentukan. Tetapi jika
semua
stan
30 Puji Nugraheni: Jembatan Konigsberg
grafnya bukan graf Euler maka
dibelah oleh sungai Pregal di Kota
yang dapat diten-tukan adalah
Königsberg sekarang bernama Kota
lintasan Eulernya saja.
Kaliningrat (sebelah timur Prussia, Jerman
B
C D
tempat semula adalah tidak mungkin. Permasalahan ini telah da-pat
G
F
masing-masing
tepat satu kali dan kembali lagi ke
E
A
sekarang)
dipecahkan
Gambar 11. Graf untuk permasalahan tukang pos Cina
oleh
seorang
mate-
matikawan Swiss, L. Euler pada tahun 1736. Euler mere presen-
Graf pada gambar 11
tasikan Jembatan Königsberg da-lam
merupakan graf Euler karena
suatu graf. Masing-masing jembatan
derajat setiap simpul pada graf
diwakili oleh sisi dan daratan yang
tersebut adalah genap, sehingga
dihubungkan oleh jembatan diwakili
dapat
Eu-
oleh simpul. Sehingga permasalahan
lernya. Salah satu alternatif rute
Jembatan Königsberg adalah apakah
yang dapat ditempuh oleh tukang
pada graf tersebut dapat dibuat sirkuit
pos Cina supaya ia melewati
Euler. Menurut Euler syarat kebe-
setiap jalan tepat satu kali dan
radaan sirkuit Euler adalah grafnya
kembali lagi ke tempat awal
harus merupakan graf terhubung dan
keberang- katan adalah A, B, C,
derajat
D, E, F, C, E, B, F, A.
Ternyata pada graf tersebut derajat
ditentukan
sirkuit
setiap
simpulnya
genap.
setiap simpulnya ganjil sehingga Penutup
tidak dapat dibuat sirkuit Euler atau
Permasalahan Jembatan Königsberg
yaitu
apakah
mungkin
melalui ketujuh buah jembatan yang menghubungkan
daratan
orang tidak mungkin dapat mele-wati jembatan itu masing-masing sekali untuk kembali ke tempat semula.
yang Puji Nugraheni: Jembatan Konigsberg 31
Daftar Pustaka Bondy, J.A & Murty, U.S.R. 1976. Graph Theory with Applications. London : The Macmilan Press
Liu, C.L. 1985. Element of Discrete Mathematics. McGraw-Hill Rinaldi
32 Puji Nugraheni: Jembatan Konigsberg
Munir. 2001. Matematika Diskrit. Bandung: Informa-tika
