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