JEMBATAN KNIGSBERG 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 Knigsberg pada tahun 1736. Permasalahan Jembatan Knigsberg 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 Knigsberg mempunyai simpul yang semuanya berderajat ganjil, sehingga tidak mungkin melewati semua jembatan sebanyak satu kali untuk kembali ke tempat semula Kata Kunci: jembatan Knigsberg, graf Euler Pendahuluan Dalam suatu model matematika, berbagai masalah dalam kehidupan sehari-hari biasanya diidentifikasi kemudian dinyatakan dalam suatu sistem yang bersifat matematis. Salah satu bentuk model matematika nakan yang dapat diperguuntuk merepresentasikan sehari-hari adalah diagram titik dan garis. Pada dasarnya banyak sekali masalah nyata yang dapat diwakili dengan diagram titik dan garis, diantaranya penyampaian suatu berita atau gosip agar keliling, tersebar luas, pengantaran surat, penyusunan trayek pedagang peran-cangan jaringan kereta api, telekomunikasi,

berbagai masalah dalam kehidupan

Puji Nugraheni: Jembatan Konigsberg 21

komputer, penyaluran bahan bakar, perancangan arena pameran atau tempat rekreasi agar pengunjung dapat melihat semua stan atau atraksi hi-buran tanpa melewati ulang jalur yang sama dan masih banyak lagi permasalahan yang lainnya. Pada contoh diatas ibu rumah tangga, rumah, kota, stasiun, sentral tele-pon, pusat informasi, komputer, POM bensin dan stand dapat digambarkan sebagai keakraban, titik dan jalan, hubungan prasa-rana

sungai. Ada tujuh buah jembatan yang menghu-bungkan daratan yang dibelah oleh sungai tersebut seperti terlihat dalam gambar berikut:

hubungan, jalur komunikasi, kabel dapat diwakili oleh garis. Diagram titik dan garis seperti di atas dalam model matematika dike-nal sebagai graf. Menurut catatan pertama sejarah, yang permasalahan

C
Masalah Jembatan Knigsberg adalah apakah mungkin mela-lui ketujuh buah jembatan itu ma-singmasing tepat satu kali dan kembali lagi ke tempat semula. Sebagian penduduk jembatan kota itu sepakat bahwa dan memang tidak mungkin melalui setiap hanya sekali 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-

menggunakan graf adalah permasalahan Jembatan Knigsberg pada tahun 1736. Jembatan Knigsberg merupakan jembatan yang terletak di Kota Knigsberg 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

22 Puji Nugraheni: Jembatan Konigsberg

mukan jawaban masalah Jembatan Knigsberg ini dengan menggu-nakan pembuktian yang sederhana. Ia memodelkan masalah ini ke da-lam graf. Daratan yang dihubung-kan oleh jembatan dinyatakan seba-gai titik dan jembatan disimbolkan sebagai garis. Representasi berikut : A B C Jawaban yang dikemukakan oleh Euler adalah orang tidak mungkin melalui ketujuh jembatan itu masing-masing satu kali dan kembali 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 Knigsberg akan memun-culkan teori tentang graf Euler yang akan dibahas lebih lanjut dalam tulisan ini. D graf untuk Jembatan Knigsberg adalah seba-gai

Terminologi Graf Graf didefinisikan sebagai pasangan himpunan (V,E) dengan V adalah himpunan berhingga dan tidak kosong dari simpul-simpul (vertex) dan E adalah himpunan sisi (edges) yang menghubungkan sepa-sang simpul (Rinaldi Munir,2001). Secara geometri graf digambarkan sebagai kumpulan noktah (simpul) di dalam bidang yang dihubungkan dengan sekumpulan garis (sisi). Dua buah simpul dikatakan adjacent bila keduanya terhubung langsung dan sebuah sisi dikatakan berincident dengan kedua simpul yang dihubungkannya. Jika
vp

adjacent dengan v q maka sisi yang incident dengan kedua simpul tersebut dapat ditulis ( v p , v q ). Pada 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

1. Graf Tak Berarah (Undirected Graph) Suatu graf dikatakan tak bera-rah jika sisinya tidak mempu-nyai orientasi arah. Pada graf tak berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan atau ( v p , v q ) = ( v q , v p ). 2. Graf Berarah (Directed Graph atau Digraph) Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Pada graf berarah urutan pasangan sim-pul yang dihubungkan oleh sisi diperhatikan atau ( v p , v q ) ( v q , v p ). Berikut merupakan contoh graf tak berarah dan graf berarah:
D A C B
A

D B

Gambar 2 (b) Graf berarah Pada suatu graf G juga dikenal adanya lintasan dari simpul v p ke
vq

yaitu

rangkaian

simpul

v p , v i1 , v i 2 ,..., vim , v q sehingga

(v , v ), (v v ),...,(v
p i1 i1 i2

im

, vq

adalah

sisi

pada graf G. Contoh: Diketahui graf G pada gambar 3

A B D
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). Suatu lintasan dikatakan lintasan sederhana (simple path) ji-ka

Gambar 2 (a) Graf tak berarah

24 Puji Nugraheni: Jembatan Konigsberg

tidak

melalui

sisi

yang

sama

himpunan V terdapat lintasan dari v p ke v q . Jika tidak demikian, maka G disebut graf tak graph). graf tak terhubung Sedangkan berarahnya

sebanyak dua kali dan suatu lin-tasan dikatakan 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 sirkuit sederhana (simple sircuit) jika sirkuitnya tidak melalui sisi yang sama sebanyak dua kali dan sirkuit elementer (elementary circuit) jika sirkuitnya tidak mela-lui simpul yang sama sebanyak dua kali. Contoh : Pada gambar 3, A, B, C, A adalah sirkuit sederhana dan juga sirkuit elementer, sedangkan A, B, D, C, B, A bukan sirkuit sederhana dan juga bukan sirkuit elementer. Dua simpul v p dan simpul v q disebut terhubung jika terdapat

(disconnected bung jika

untuk graf berarah dikatakan terhuterhubung. Contoh :

Gambar 4 (a) Graf tak berarah terhubung

Gambar 4 (b). Graf tak berarah tidak terhubung

lintasan dari v p ke v q .Graf tak berarah G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul v p dan v q dalam

D A B

Gambar 5 (a)Graf berarah terhubung

Puji Nugraheni: Jembatan Konigsberg 25

dimulai dengan masalah Jem-batan

Knigsberg. sekali dan

Perjalanan kembali

mele-wati ke tempat sirkuit

setiap Jembatan Knigsberg sebanyak keberangkatan membentuk

Gambar 5 (b)Graf berarah tidak terhubung Anak graf (subgraph) dari graf G = (V,E) adalah graf G1 = (V1,E1) dengan V1 V dan

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 graf tepat satu kali. Sedangkan sirkuit

E1 E .
Contoh :
A B C D E

Euler ada-lah sirkuit yang melewati masing-masing sisi tepat satu kali. Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian graph) dan graf yang mempunyai lintasan Euler dinamakan graf semi-Euler (semi-Eulerian graph). Contoh:
B A

Gambar 6 (a) Graf G

C D E

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
C D

B A F E

C D G

Pembuktian adalah:

penyataan untuk

tersebut syarat Jika

Pembuktian Euler, G jelas

perlu. Misalkan G memiliki lin-tasan terhubung. lintasan Euler dilalui, maka pada setiap simpul terdapat dua sisi yang pada graf ber-incident, kecuali pada simpul awal dan simpul akhir. Jadi setiap simpul selain simpul awal dan simpul akhir harus berderajat genap. Jika simpul awal dan simpul akhir sama maka terbentuk sirkuit Euler. Pembuktian untuk syarat cukup. Misal dibuat lintasan Euler mulai dari salah satu dari dua simpul yang berderajat ganjil dan akan melewati semua sisi pada graf itu sehingga tidak ada sisi yang dilewati lebih dari sekali. Untuk simpul yang berderajat genap, bila lintasan itu masuk ke simpul me-lewati sebuah sisi, sisi maka yang ia selalu bisa ketika yang meninggalkan simpul itu melewati [Link] pembuatan lintasan berakhir, pasti telah sampai pada simpul berderajat ganjil lainnya. Jika semua Puji Nugraheni: Jembatan Konigsberg 27

Gambar 7 (b) Graf Euler tak berarah Lintasan Euler

Gambar 7 (a) : C, A, B, C, D, A. Sirkuit Euler pada graf Gambar 7 (b) : A, B, C, D, G, C, E, G, F, E, B, F, A. Syarat perlu dan cukup mengenai keberadaan lintasan Euler maupun sirkuit Euler di dalam sua-tu graf ternyata sangat sederhana. Euler menemukan syarat tersebut ketika memecahkan Knigsberg. Hasil penemuan Euler ten-tang keberadaan lintasan Euler dipaparkan kembali oleh Liu, C L (1985) sebagai berikut: Suatu graf tak berarah memiliki lintasan Euler jika dan hanya jika ia terhubung (connected) dan memiliki nol atau dua simpul berderajat ganjil. masalah Jemba-tan

sisi didalam graf itu dilewati dengan cara ini maka jelas akan diperoleh lintasan Euler. Jika tidak semua sisi di dalam graf itu terl-ewati, sisi-sisi yang tidak terlewati itu dianggap sebagai anak graf, sehingga semua simpul yang terda-pat dalam anak graf ini berderajat genap. Dengan diawali dari salah satu simpul pada anak graf tersebut, sekali lagi dibuat lintasan yang melalui semua sisi-sisi pada anak graf. Karena semua simpul berde-rajat genap, maka pasti lintasan pada anak graf itu akan kembali ke simpul awal. Dari penggabungan lintasan yang pertama dan kedua akan diperoleh lintasan yang bera-wal dan berakhir pada simpul yang berderajat ganjil. Jika diperlukan, cara ini dapat diulang sampai diperoleh lintasan yang melalui semua sisi pada graf tersebut. Berdasarkan hasil teori tentang keberadaan lintasan Euler di atas, akan diperoleh akibat bahwa graf tak berarah G adalah graf Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpulnya

berderajat genap. Sehingga jelaslah masalah Jembatan Knigsberg bahwa tidak mungkin melalui ketujuh buah jembatan itu masing-masing tepat satu kali dan kembali lagi ke tempat semula karena jika Jem-batan Knigsberg direpresentasikan dalam sebuah graf, graf tersebut tidak memiliki sirkuit Euler dise-babkan semua simpulnya berderajat ganjil. Lintasan dan sirkuit Euler juga terdapat pada graf berarah. Berikut pemaparan Rinaldi Munir (2001) tentang keberadaan lintasan dan sirkuit Euler pada graf berarah: Graf berarah G memiliki sirkuit Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua simpul, yang pertama satu dan yang memiliki besar kedua derajat-keluar derajat-masuk lebih

memiliki derajat-masuk satu lebih besar dari derajat-keluar.

28 Puji Nugraheni: Jembatan Konigsberg

Contoh :
D C

pameran dan permasalahan tukang pos. 1. Jalur pengunjung pameran Contoh sederhana dari

masalah ini adalah misalkan pada suatu gedung terdapat enam stan yang akan diguna-kan untuk pameran. Masing-masing stan dihubungkan oleh beberapa pintu dengan stan yang lain, lebih jelasnya denah gedung seperti gambar berikut:

Gambar 8 (a) Graf semiEuler yang berarah

F E

D C

Gambar 8 (b) Graf Euler yang berarah Lintasan Euler pada graf Gambar 8 (a) : D, A, B, D, C, B. Sirkuit Euler pada graf Gambar 8 (b) : A, G, C, B, G, E, D, F, A. Permasalahannya ada-lah Penerapan Graf Semi-Euler dan Graf-Euler Selain digunakan dalam permasalahan jembatan Knigs-berg, graf Euler juga dapat digu-nakan untuk menyelesaikan perma-salahan yang lain diantaranya yang akan dibahas adalah jalur pengun-jung apakah pengunjung mungkin pameran setiap dapat Gambar 9

melihat semua stan tanpa harus melewati jalan yang sama dan jika mungkin bagaimana jalur tersebut. Permasalahan ini da-pat diselesaikan gunakan graf, dengan mengmasing-masing

Puji Nugraheni: Jembatan Konigsberg 29

stan diwakili oleh simpul dan pintu yang menghubungkan ini antara dua stan diwakili oleh sisi. Sehingga permasalahan adalah apakah di dalam graf tersebut terdapat lintasan Euler, jika terdapat bagaimana contoh lintasan Eulernya. Representasi graf Gambar 9: Gambar10
G A B C

melewati jalan yang sama un-tuk denah tempat pameran seperti pada gambar 9. Salah satu jalur yang dapat dilewati oleh pengunjung adalah masuk ke stan A, stan D, stan E, stan B, stan C, stan F, kemudian keluar. 2. Permasalahan tukang pos Permasalahan ini pertama kali dikemukakan oleh Mei Gan (dari Cina) pada tahun 1962. Ia mengemukakan per-masalahan yaitu seorang tu-kang pos akan mengantar surat ke alamat-alamat

sepanjang jalan di suatu daerah. Bagai-mana ia merencanakan rute perjalanannya supaya ia mele-wati setiap jalan tepat satu kali dan kembali lagi ke tempat awal keberangkatan. Permasalahan ini tidak lain adalah menentukan sirkuit Euler di dalam graf yang merepresentasikan peta jalan tempat tukang pos mengantar surat. Jika grafnya merupakan graf Euler maka, maka sirkuit Eulernya mudah ditentukan. Tetapi jika

Dari

representasi

graf

yang diperoleh, terdapat dua simpul berderajat ganjil yaitu simpul G dan F, sedangkan simpul yang lainnya berderajat genap. Sesuai dengan syarat maka setiap dapat tanpa keberadaan lintasan Euler pada penjelasan graf melihat sebelumnya, atau stan pasti terdapat lintasan Euler pada tersebut semua pengunjung pameran

30 Puji Nugraheni: Jembatan Konigsberg

grafnya bukan graf Euler maka yang dapat diten-tukan adalah lintasan Eulernya saja.
B A F E D G C

dibelah oleh sungai Pregal di Kota Knigsberg sekarang bernama Kota Kaliningrat (sebelah timur Prussia, Jerman sekarang) masing-masing tepat satu kali dan kembali lagi ke tempat semula adalah tidak mungkin. Permasalahan ini telah da-pat dipecahkan oleh seorang matematikawan Swiss, L. Euler pada tahun 1736. Euler mere presentasikan Jembatan Knigsberg da-lam suatu graf. Masing-masing jembatan diwakili oleh sisi dan daratan yang dihubungkan oleh jembatan diwakili oleh simpul. Sehingga permasalahan Jembatan Knigsberg adalah apakah pada graf tersebut dapat dibuat sirkuit Euler. Menurut Euler syarat keberadaan sirkuit Euler adalah grafnya harus merupakan graf terhubung dan derajat setiap simpulnya genap. Ternyata pada graf tersebut derajat setiap simpulnya ganjil sehingga tidak dapat dibuat sirkuit Euler atau orang tidak mungkin dapat mele-wati jembatan itu masing-masing sekali untuk kembali ke tempat semula.

Gambar 11. Graf untuk permasalahan tukang pos Cina Graf pada gambar 11 merupakan graf Euler karena derajat setiap simpul pada graf tersebut adalah genap, sehingga dapat ditentukan sirkuit Eulernya. Salah satu alternatif rute yang dapat ditempuh oleh tukang pos Cina supaya ia melewati setiap jalan tepat satu kali dan kembali lagi ke tempat awal keberang- katan adalah A, B, C, D, E, F, C, E, B, F, A. Penutup Permasalahan Jembatan Knigsberg yaitu apakah mungkin yang melalui ketujuh buah jembatan yang menghubungkan daratan

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 Munir. 2001. Matematika Diskrit. Bandung: Informa-tika

32 Puji Nugraheni: Jembatan Konigsberg