SEJARAH SINGKAT TEORI GRAF

soalampuhh.blogspot.com

Teori graf lahir pada tahun 1736 melalui tulisan euler yang berisi tentang pemecahan masalah jembatan konigsberg yang sangat terkenal di eropa. Kurang lebih seratus tahun setelah lahirnya tulisan euler tersebut tidak ada perkembangan yang berarti berkenaan dengan teori graf.

tahun 1847, G.R Kirchoff(1824-1887) berhasil mengembangkan teori pohon (Theory of trees) yang digunakan dalam persoalan jaringan listrik. sepuluh tahun kemudian, A Cayley (1821-1895) juga menggunakan konsep pohon untuk menjelaskan permasalahan kimia hidrokarbon.

Pada masa Kirchoff dan cayley juga telah lahir dua hal penting dalam teori graf. Salah satunya berkenaan dengan konjektur empat warna yang menyatakan bahwa untuk mewarnai sebuah atlas cukuoo dengan menggunakan empat macam warna sedemikian hingga tiap negara yang berbatasan memiliki warna yang berbeda.

Para ahli teori garaf meyakini bahwa orang yang pertama kali mengemukakan masalah empat warna adalah A.F. Mobius (1790-1868) dalam salah satu kuliahnya di tahun 1840. sepuluh tahum kemudian A. Demorgan(1806-1871) kembali membahas masalah ini bersama ahli-ahli matematika lainnya di kota london. Dengan demikian tulisan Demorgan dianggap sebagai referansi pertama berkenaan dengan empat warna. Masalah empat warna ini menjadi terkenal setelah cayley mempublikasikannya tahun 1979 dalam proceeding of the royal geographic society volume pertama.

hal yang penting untuk dibicarakan sehubungan dengan perkembangan teori graf adalah apa yang dikemukakan oleh Sir W.R Hamilton (1805-1865). pada tahun 1859 dia berhasil menemukan permainan yang kemudian dijualnya kesebuah pabrik mainan di Dublin. permainan tersebut dari kayu berbentuk dodecahedron beraturan yakni berupa sebuah polihedron dengan 12 muka dan 20 pojok. Tiap muka berbentuk sebuah pentagon beraturan dan tiap pojoknya dibentuk oleh tiga sisi berbeda. tiap pojok dari dodecahedron tersebut dipasangkan dengan sebuah kota terkenal seperti london, newyorkk, paris, dll masalah dalam permainan ini adalah kita diminta untuk mencari suatu rute melalui sisi sisi dodecahedron sehingga tiap kota dari 20 kota yang ada dapat dilalui tepat satu kali. walaupun saat ini tidak ada seorangpun yang bisa menemukan syarat perlu dan cukup dari eksistensi rute yang dicari.

kurang lebih setengah abad setelah hamilton, aktivitas dalam bidah teori graf dapat dikatakan relatif kecil. pada tahun 1920 an kegiatan tersebut muncul kembali yang dipelopori oleh D. Konig. Konig berupaya mengumpulkan hasil-hasil pemikiran para ahli matematika tentang teori graf termsuk hasil pemikiran sendiri, kemudian dikemasnya dalam bentuk buku yang diterbitkan pada tahun 1936. Buku tersebut dianggap sebagai buku pertama tentang teori graf.

Tiga puluh tahun terakhir ini merupakan periode yang sangat intensif dalam aktivitas pengembangan teori graf baik murni maupun terapan. sejumlah besar penelitian telah dilakukan,ribuan artikel telah diterbitkan, dan lusinan buku telah banyak ditulis. diantara orang yang terkenal yang banyak berkecimpung dalam bidang ni adalah Claude Berge, Oysten Ore, Paul Erdos, William Tutte, dan Frank Harary.

sumber: common text book matematika diskrin (universitas indonesia)

Share :