Graph Problem

Secara informal, grafik dapat dianggap sebagai kumpulan titik yang disebut simpul, beberapa yang dihubungkan oleh segmen garis disebut tepi. Grafik merupakan subjek yang menarik untuk dipelajari, baik teoritis dan praktis. Grafik dapat digunakan untuk memodelkan berbagai aplikasi, termasuk transportasi, komunikasi, sosial dan ekonomi jaringan, penjadwalan proyek, dan games. Belajar teknik yang berbeda dan aspek sosial khususnya internet adalah salah satu daerah penelitian aktif saat ini melibatkan ilmuwan komputer, ekonom, dan ilmuwan social. 
Algoritma grafik dasar meliputi algoritma graph-traversal (bagaimana seseorang bisa mencapai semua titik dalam jaringan?), algoritma shortest-path (apa rute terbaik antara dua kota?), dan pemilahan topologi untuk grafik dengan tepi diarahkan (adalah satu set kursus dengan prasyarat mereka konsisten atau kontradiksi-diri?). Untung, algoritma ini dapat dianggap ilustrasi teknik desain umum;
Beberapa masalah grafik adalah komputasi sangat sulit; contoh paling terkenal adalah masalah salesman bepergian dan masalah mewarnai grafik. Masalah salesman keliling (TSP) adalah masalah menemukan tur terpendek melalui n kota yang mana setiap kota di kunjungi hanya satu kali. Selain aplikasi yang jelas melibatkan perencanaan rute, muncul dalam aplikasi modern seperti sirkuit fabrikasi papan dan chip yang VLSI, X-ray kristalografi, dan rekayasa genetika. Masalah mewarnai grafik berusaha untuk menetapkan jumlah terkecil dari warna untuk simpul grafik sehingga simpul yang berdekatan tidak memiliki warna yang sama. 

Sumber : 
- Levitin, Anany. Introduction to The Design and Analysis of Algorithms