Definisi
Graph adalah sebuah notasi abstrak yang terdiri dari kumpulan
titik-titik (vertices / nodes / points) beserta
garis-garis (edges/arcs/lines) yang saling terhubung, dimana satu buah garis
menghubungkan dua buah titik. Susunan sebuah graph adalah titik-titiknya, dan
ukurannya adalah jumlah garisnya.
Biasanya sebuah graph digunakan untuk menggambarkan hubungan
antara objek-objek. Banyak permasalahan
yang bisa digambarkan dengan graph, seperti komunikasi jaringan,
pengorganisasian data, hubungan sosial dan lain sebagainya.
Permasalahan dalam Graph
Graph Traversal
Dikenal juga sebagai graph search, adalah sebuah proses
pengunjungan (pengecekan/perubahan) setiap titik pada sebuah graph. Adapun beberapa
algoritma untuk graph traversal :
- Depth-first search (DFS) - DFS dikhususkan untuk graph yang terbatas. DFS mengunjungi turunan dari sebuah titik terlebih dahulu daripada titik yang bersebelahan (ada pada level yang sama).
- Breadth-first search (BFS) - BFS adalah teknik lain untuk melakukan traversing pada graph yang terbatas. Berbeda dengan DFS, BFS mengunjungi semua titik yang ada pada level sama terlebih dahulu sebelum mengunjungi titik turunannya.
Graph Coloring
Graph Coloring adalah sebuah metode untuk menetapkan warna pada
titik dari sebuah graph sehingga tidak ada dua titik yang berdekatan memiliki
warna yang sama. Adapun beberapa permasalahan dalam graph coloring sebagai
berikut :
- Vertex Coloring - Mewarnai titik pada sebuah graph agar tidak ada dua titik berdekatan (terhubung dengan garis yang sama) yang memiliki warna sama.
- Edge Coloring - Mewarnai garis pada sebuah graph agar tidak ada dua garis berdekatan (terhubung dengan titik yang sama) yang memiliki warna sama.
- Face Coloring - Mewarnai pada setiap face (wilayah pada planar graph) agar tidak ada dua face berdekatan (berbagi titik / garis yang sama) memiliki warna yang sama.
Sumber :
0 komentar:
Posting Komentar