JEMBATAN KÖNIGSBERG

Abstract

Abstrak

Berbagai permasalahan dalam kehidupan sehari-hari dapat dimodelkan dengan menggunakan diagram titik dan garis atau dalam matematika lebih dikenal dengan sebutan graf. Titik dalam graf dinamakan simpul dan garisnya dinamakan sisi. Penggunaan graf pertama kali adalah pada permasalahan Jembatan Königsberg pada tahun 1736. Permasalahan Jembatan Königsberg adalah apakah mungkin melewati ketujuh jembatan
sebanyak satu kali untuk kembali ke tempat semula.

Permasalahan ini telah dipecahkan oleh ahli matematika dari Swiss
bernama L. Euler pada tahun 1736. Dalam penemuannya Euler mengemukakan bahwa untuk dapat melewati semua jembatan sebanyak satu kali dan kembali ke tempat semula, maka grafnya harus merupakan graf Euler yaitu graf yang memuat sirkuit Euler. Sedangkan syarat keberadaan sirkuit Euler menurut Euler adalah derajat setiap simpulnya harus genap. Graf yang merepresentasikan permasalahan Jembatan Königsberg mempunyai simpul yang semuanya berderajat ganjil, sehingga tidak mungkin melewati semua jembatan sebanyak satu kali untuk kembali ke tempat semula
Kata Kunci: jembatan Königsberg, graf Euler