Teori graf merupakan salah satu cabang matematika diskrit yang berkembang pesat dan memiliki banyak aplikasi dalam berbagai bidang, seperti ilmu komputer, teknik, jaringan komunikasi, transportasi, hingga ilmu sosial. Graf sendiri adalah struktur matematika yang digunakan untuk memodelkan hubungan antar objek. Karena kemampuannya dalam merepresentasikan konektivitas dan struktur relasional, graf menjadi alat yang sangat efektif dalam menyelesaikan berbagai permasalahan nyata yang kompleks.