G = (V, E)
Dimana : G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc
V adalah himpunan tidak kosong dari verteks-verteks {v1, v2, …, vn } yang dalam hal ini verteks merupakan himpunan tidak kosong dari verteks-verteks (vertices atau node) dan E adalah himpunan edge {e1, e2, …, en } atau sisi yang menghubungkan sepasang verteks.
Beberapa istilah dalam graph
1. Incident
Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w),
maka v dan w disebut “terletak” pada e, dan e disebut incident dengan v dan w.
2. Degree
Didalam Graph ada yang disebut dengan Degree, Degree mempuyai 3 jenis antara lain :
• Degree dari suatu verteks x dalam undigraph adalah jumlah busur yang incident dengan
simpul tersebut.
• Indegree dari suatu verteks x dalam digraph adalah jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut..
• Outdegree dari suatu verteks x dalam digraph adalah jumlah busur yang ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluar” atau berasal dari simpul tersebut.
3. Adjacent
Pada graph tidak berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut. Simpul v dan w disebut adjacent.
Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v.
4. Successor dan Predecessor
Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.
5. Path
Sebuah path adalah serangkaian simpul-simpul berbeda yang adjacent secara berturut-turut
dari simpul satu ke simpul berikutnya.
Jenis -jenis Graph
1. Directed Graph (Digraph)
Jika sisi-sisi graph hanya berlaku satu arah. Misalnya : {x,y} yaitu arah x ke y, bukan dari y ke
x, x disebut origin dan y disebut terminus. Secara notasi sisi digraph ditulis sebagai vektor (x, y).
2. Graph Tak Berarah (Undirected Graph atau Undigraph)
Setiap sisi {x, y} berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis sisi pada undigraph tidak memiliki mata panah dan secara notasional menggunakan kurung kurawal.
3. Weighted Graph
Weighted Graph adalah Graph yang sisi / busurnya memiliki nilai (bobot). Weighted Graph terdiri dua jenis :
- Weighted Direct Graph
Bobot berlaku satu arah saja
- Weighted Undirect Graph
Bobot Berlaku 2 arah
Masalah Dalam Graph
Beberapa Beberapa masalah masalah sangat sulit diselesaikan dengan cara komputasi hanya beberapa contoh yang dapat diselesaikan dalam waktu yang dapat diterima.
GCP(Graph Coloring Problem) atau Pewarnaan Graph
Pewarnaan graf adalah pemberian warna terhadap vertex-vertex graf di mana 2 buah vertex yang berdampingan tidak boleh mempunyai warna yang sama.
Masalah pewarnaan graf diyakini pertama kali muncul sebagai masalah pewarnaan peta, dimana warna setiap daerah pada peta yang berbatasan dibuat berlainan sehingga mudah untuk dibedakan. Hal ini kemudian mengembangkan teorema-teorema menarik dan
berujung pada teorema 4 warna, yang menyatakan : “bilangan kromatik graf
planar tidak lebih dari 4.”
Masalah pewarnaan graf memiliki banyak aplikasi di dalam bidang lain, misalnya membuat jadwal, pemetaan, penentuan frekuensi untuk radio, pencocokan pola, dan lain-lain.
Masalah ini bahkan telah berkembang luas menjadi suatu permainan yang sangat
terkenal di kalangan masyarakat luas, yaitu sudoku.
TSP (Traveling Salesman Problem)
Travelling salesman problem adalah suatu permasalahan dalam bidang diskrit dan optimasi kombinatorial. Sebagai permasalahan kombinatorial, persoalan ini tergolong memilingi kemungkinan jawaban yang sangat banyak.
Berikut beberapa contoh penanganan permasalahan Travelling Salesman Problem:
TSP dengan 3 kota: Permasalahan 3 kota tidak memerlukan komputasi karena jumlah kemungkinan solusi hanya 1.
TSP dengan 4 kota: Permasalahan 4 kota tidak memerlukan komputasi karena jumlah
kemungkinan hanya (4-1)! / 2 = 3.
Permasalahan dengan jumlah kota yang semakin banyak akan menghasilkan semakin banyak kemungkinan. Untuk 20 kota akan menghasilkan 19!/2 kemungkinan atau
sekitar 6,08 x 〖10〗^16. Namun, tidak semua travelling salesman problem
melibatkan graf lengkap.
Sumber :
https://id.scribd.com/doc/129557072/Graph
https://www.academia.edu/5508323/Makalah_graph
lecturer.ukdw.ac.id/anton/download/TIstrukdat11.ppt
ardiansyah.tif.uad.ac.id/publications/paper_ardiansyah_jurnal_informatika.pdf
https://www.academia.edu/8724613/Penyelesaian_Travelling_Salesman_Problem_dengan_Algoritma_Heuristik
Bagikan
Graph Problems
4/
5
Oleh
Rifaldi Yunus
