Graph problem

Salah satu materi tertua dan paling menarik di Algorithmics adalah algoritma grafik. Secara informal, grafik dapat dianggap sebagai kumpulan titik yang disebut simpul, beberapa di antaranya terhubung dengan segmen garis yang disebut tepi. Grafik merupakan subjek yang menarik untuk belajar, baik untuk alasan teoritis dan praktis. Grafik dapat digunakan untuk memodelkan berbagai macam aplikasi, termasuk transportasi, komunikasi, sosial dan ekonomi jaringan, penjadwalan proyek, dan games. Mempelajari aspek teknis dan sosial yang berbeda dari Internet khususnya adalah salah satu daerah penelitian aktif saat ini melibatkan ilmuwan komputer, ekonom, dan ilmuwan sosial.

algoritma grafik dasar meliputi algoritma graph-traversal, algoritma shortest-path, dan pemilahan topologi untuk grafik dengan tepi diarahkan. Untung, algoritma ini dapat dianggap ilustrasi teknik desain umum.

Beberapa masalah grafik adalah komputasi sangat sulit, contoh yang paling terkenal adalah the traveling salesman problem dan the graph-coloring problem. the traveling salesman problem (TSP) adalah masalah menemukan tur terpendek melalui n kota yang dilihat setiap kota tepat satu kali. Selain aplikasi yang jelas melibatkan perencanaan rute, itu muncul dalam aplikasi modern seperti sirkuit fabrikasi papan dan chip yang VLSI, X-ray kristalografi, dan rekayasa genetika. the graph-coloring problem berusaha untuk menetapkan jumlah terkecil dari warna ke simpul dari grafik sehingga tidak ada dua simpul yang berdekatan adalah warna yang sama. Masalah ini muncul di beberapa aplikasi, seperti penjadwalan acara, jika peristiwa yang diwakili oleh simpul yang terhubung dengan sebuah sisi jika dan hanya jika Peristiwa terkait tidak bisa dijadwalkan pada saat yang sama, solusi untuk the graph-coloring problem menghasilkan jadwal yang optimal.

Atau dapat disimpulkan :

• ·         Algoritma graf dasar: graph traversal, shortest-path, sorting topologik pada graph dengan ujung berarah
• ·         Beberapa problem sangat sulit diselesaikan dengan komputasi –hanya beberapa contoh problem yang dapat diselesaikan dalam waktu yang dapat diterima :

o   Traveling Salesman Problem (TSP)

o   Graph-Coloring Problem (GCP)