Graph Problem

Secara informal, grafik dapat dianggap sebagai kumpulan titik yang disebut simpul, beberapa yang dihubungkan oleh segmen garis yang disebut tepi. Teori Graph merupakan salah satu cabang dari bidang Matematika Diskrit yang mempunyai banyak terapan di berbagai bidang. 

Graph adalah kumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge).

                                   G = (V, E)

        Dimana :            G = Graph
                                   V = Simpul atau Vertex, atau Node, atau Titik

                                   E = Busur atau Edge, atau arc

Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalahyang bisa diselesaikan dengan bantuan graf. Seringkali graf digunakan untuk merepresentasikan suaru jaringan. Misalkan jaringan jalan raya dimodelkan graf dengan kota sebagai simpul (vertex/node) dan jalan yang menghubungkansetiap kotanya sebagai sisi (edge) yang bobotnya (weight ) adalah panjang dari jalan tersebut.

Beberapa masalah grafik adalah komputasi sangat sulit; paling terkenal contoh adalah masalah salesman bepergian dan masalah grafik-mewarnai. Travelling 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. Masalah grafik-mewarnai berusaha untuk menetapkan jumlah terkecil dari warna untuk simpul dari grafik sehingga tidak ada dua simpul yang berdekatan adalah warna yang sama. Ini Masalah muncul dalam beberapa aplikasi, seperti penjadwalan acara: jika peristiwa yang diwakili oleh simpul yang terhubung dengan sebuah sisi jika dan hanya jika sesuai Peristiwa tidak bisa dijadwalkan pada saat yang sama, solusi untuk masalah pewarnaan graf  yaitu dengan menghasilkan jadwal yang optimal.

Referensi :  http://lppm.trigunadharma.ac.id/public/fileJurnal/hpiM4-Jurnal-DW-TeoriGraph.pdf

                    https://id.scribd.com/doc/129557072/Graph

                    Design & Analisis Algorithms [ Anany Levitin ]