Problema & Model Graf

Problema & Model Graf
Secara umum, langkah-langkah yang perlu dilalui dalam penyelesaian suatu masalah dengan bantuan komputer adalah sebagai berikut :
Problema ? Model Yang Tepat ? Algoritma ? Program Komputer



Contoh problema graf :
1. Petugas kantor telepon yang ingin mengumpulkan koin-koin dari telepon umum. Berangkat dari kantor & kembali ke kantornya lagi.
Yang diharapkan ? suatu rute perjalanan dengan waktu minimal.
Masalah di atas dikenal sebagai Travelling Salesman Problem
Sebagai contoh :


Untuk menyelesaikan masalah di atas dapat dipakai Algoritma Tetangga Terdekat (yakni menggunakan Metode Greedy)

2. Perancangan Lampu Lalu Lintas.

Yang diharapkan ? pola lampu lalu lintas dengan jumlah fase minimal.
Sebagai contoh :

Untuk menyelesaikan masalah di atas dapat dipakai Algoritma Pewarnaan Graf (juga dikenal sebagai Graph Coloring, yakni menggunakan Metode Greedy)