Teori Graf

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