Jembatan Konigsberg

Jemabatan Konigsberg adalah masalah klasik terkenal yang dibahas oleh Leonhard Euler 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 graf (himpunan titik dan garis). Euler menganalisis graf tersebut yang merupakan representatif dari 7 jembatan 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, graf tersebut disebut graf Eulerian.

Contoh

Graf disamping merupakan graf Eulerian  karena semua titik derajatnya genap, itung aja sendiri kalo gak percaya maka hitung 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..

Graph Tertelusuri

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

contoh

Graph disamping adalah graf tertelusuri, 2 titiknya berderajat ganjil dan sisanya berderajat genap, kita harus memulai perjalanan dari titik berderajat ganjil berakhir ke titik berderajat ganjil lainnya