Jembatan Konigsberg

Jemabatan Konigsberg adalah masalah klasik terkenal yang dibahas oleh Leonhard Euler pada tahun 1736

Peta kota konigsberg pada tahun 1736

Peta kota konigsberg pada tahun 1736

Penduduk kota Konigsberg di Prusia (sekarang Rusia) suka jjs (jalan-jalan sore) keliling kota, karna kota mereka indah dilalui oleh sungai Pregel dengan tujuh jembatan yang melintas disungai tersebut.  Lalu suatu hari ada seseorang yang bertanya bisa gak sich kita berjalan dari suatu titik melalui tujuh jembatan dan kembali ketitik semula dengan hanya melewati setiap jembatan hanya sekali saja?

Semua orang lalu mencobanya tapi gagal lalu sang walikota mengirim surat beserta peta kota konigsberg  ke Leonhard Eular jenius matematika untuk menjawab pertanyaan tersebut, Lalu dia menyerderhanakan peta tersebut menjadi lalu disederhanakan lagi menjadi

Ini yang disebut graph (himpunan titik dan garis). Euler menganalisis grap tersebut yang merupakan representatif dari 7jembatan konigsberg. Kemudian Euler meyimpulkan bahwa perjalan tersebut tidak mungkin, dengan alasan derajat (banyaknya garis yang berujung disuatu titik, yang disingkat der) titik-titiknya ganjil, der(A)=5, der(B)=der(C)=der(D)=3.

Supaya perjalanan tersebut mungkin maka derajat semua titiknya haruslah genap supaya garis keluar sama dengan garis masuk.

Lalu Euler menyimpulkam jika derajat semua titik dari suatu graph adalah genap maka kita bisa melakukan perjalan dari satu titik melalui semua garis TEPAT sekali dan melewati semua titik (kalo titik boleh dilewati lebih dari sekali) lalu kembali ke titik awal, grap tersebut disebut eulerian graph.

Contoh

Grap disamping merupakan eulerian grap karena semua titik derajatnya genap, itung aja sendiri kalo gak percaya makaitung aja sendiri. Maka kita bisa membuat suatu perjalan dimulai dari suatu titik dan melewati semua garis tepat sekali lalu kembali ketitik semula atau dengan bahasa lain grap tersebut bisa digambar tanpa harus mengangkat pensil, dicoba ya..

Traversable graph

Hampir serupa dengan eulerian grap, melalui semua garis tepat sekali dan melewati semua titik (kalo titik boleh berulang) tetapi TIDAK kembali ketiti awal. Syarat dari traverseble grap adalah mempunyai tepat 2 titik berderajat ganjil, perjalanan dimulai dari titik berderajat ganjil berakhir dititik berderajat ganjil yang lainnya

contoh

Graph disamping adalah trversable graph, 2 titiknya berderajat ganjil dan sisanya berderajat genap, kita harus memulai perjalanan dari titik berderajat ganjil beralhir ke titik berderajat ganjil lainnya

Advertisements

About Aria Turns

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika
This entry was posted in graph theory and tagged , , , . Bookmark the permalink.

7 Responses to Jembatan Konigsberg

  1. Ean says:

    ouahch sulit sngt ea gan, & tp bs gak lbh d jls’in scr detail lagi ke kita2 ne yg trglng orng awam(tentunya agr bs paham), hehhehemmmm 🙂

  2. Tri Utami says:

    Sangat menarik ^^.. Tp apa fungsi graf ini dalam kehidupan sehari2?

  3. Tukang Makan says:

    graft=? what is that?

    graph kale mas. 😀

  4. Aria Turns says:

    setau gw definisi traversable graft harus mempunyai titik berderajat ganjil tepat 2 kalo gak ya berarti bukan traversable graft

  5. rudi says:

    wah..menarik.ttg graf ini.klo yg traversabel graf, titik dengan derajat ganjilnya > 2, kira2 tetep berlaku gk ya??

  6. Dino says:

    Wah nek iki rodo mumet..

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s