Teori Dasar Graf

Teori Dasar Graf


Kelahiran Teori Graf
Teori Graf mulai dikenal pada saat seorang matematikawan bangsa Swiss, bernama Leonhard Euler, berhasil mengungkapkan Misteri Jembatan Konigsberg pada tahun 1736. Di Kota Konigsberg (sekarang bernama Kalilingrad, di Uni Soviet) mengalir sebuah sungai bernama sungai Pregel. Di tengah sungai tersebut terdapat dua buah pulau. Dari kedua pulau tersebut terdapat jembatan yang menghubungi ke tepian sungai dan diantara kedua pulau. Jumlah jembatan tersebut adalah 7 buah.


Konon kabarnya, penduduk kota Konigsberg sering berjalan-jalan ke tempat tersebut pada hari-hari libur. Kemudian muncul suatu keinginan untuk dapat menikmati daerah tersebut dengan melalui ketujuh jambatan tepat satu kali, yakni bermula dari satu tempat (A, B, C atau D) dan kembali ke tempat semula. Mereka berusaha untuk memperoleh rute yang sesuai dengan keinginan tersebut, dengan selalu mencoba menjalaninya. Setelah mencoba berkali-kali dan karena sudah cukup lama tidak diperoleh rutenya, akhirnya penduduk tersebut mengirim surat kepada Euler. Euler dapat memecahkan masalah tersebut, yakni bahwa perjalanan / rute yang diinginkan (yakni berawal dari suatu tempat, melalui ketujuh jembatan tepat satu kali, dan kembali ke tempat semula) tidak mungkin dicapai.


Secara singkat, dalam tulisannya, Euler menyajikan keadaan jembatan Konigsberg tersebut.

Dalam masalah di atas, daratan (tepian A dan B, serta pulau C dan D) disajikan sebagai titik dan jembatan disajikan sebagai ruas garis. Euler mengemukakan teoremanya yang mengatakan bahwa perjalanan yang diinginkan di atas (yang kemudian dikenal sebagai perjalanan Euler) akan ada apabila graf terhubung dan banyaknya garis yang datang pada setiap titik (derajat simpul) adalah genap.