TEORI
GRAF
Teori
graf pertama kali diperkenalkan pada tahun 1736 oleh seoarang matematikawan
asal Swiss, yaitu Leonhard Euler (1707-1783). Tatkala itu, Euler mencoba
menyelesaikan sebuah masalah yang terkenal yaitu masalah jembatan Konigsberg.
Konigsberg adalah sebuah kota tua di Prusia Timur yang sekarang dikenal dengan
nama kota Kaliningrad. Pada saat itu, di kota Konigberg terdapat sungai Pregel
yang mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua anak sungai. Untuk
memungkinkan penduduk kota Konigsberg berjalan dari satu kota ke kota lainnya,
maka dibangun tujuh jembatan diatas sungai Pregel.
Pada
saat itu penduduk kota Konigsberg berusaha membuat sebuah rute sekitar kota
yang mampu membuat mereka menyeberangi ketujuh jembatan satu kali saja. Pada tahun
1736, Euler membuktikan bahwa perjalanan tersebut tidak mungkin dilaksanakan.
Euler membuktikan dengan menyederhanakan gambar situasi jembatan dan daratan
beserta pulau menjadi suatu model matematika yang kemudian disebut graf.
Teori Graf |
Teori Graf |