Teori graf merupakan sebuah topik bahasan yang saat ini telah banyak dikembangkan, seiring dengan perkembangannya tersebut teori graf telah banyak memiliki penerapan bagi masyarakat. Teori ini muncul pertama kali pada tahun 1736 , yakni ketika euler mencoba untuk mencari solusi dari permasalahan yang sangat terkenal yaitu jembatan konigsberg seperti pada gambar diatas tentang representasi graf pada permasalahan jembatan konigsberg.
Sejak dipekenalkan, hingga saat ini teori graf memiliki banyak aplikasi baik dalam matematika maupun berbagai disiplin ilmu lainnya. Beberapa apikasi tersebut antaralain pencarian lintasan terpendek, pesoalan pedagang keliling, persoalan tukang pos china, pendesainan chip, penggambaran hubungan dalam suatu ekosistem, permainan game, perancangan jadwa dan lain-lain.
