Graph problems

Graf adalah konstruksi matematis abstrak yang digunakan untuk memodelkan masalah dunia nyata dengan membagi masalah menjadi satu set node yang terhubung. Kami menyebut setiap node sebagai simpul dan setiap koneksi sebagai tepi. Misalnya, peta kereta bawah tanah masng-masing titik mewakili stasiun, dan masing-masing garis mewakili rute antara dua stasiun

- Pengelompokan graf dapat didasarkan pada ada tidaknya sisi ganda atau sisi kalang, pada jumlah simpul,atau berdasarkan orientasi arah pada sisi.

  a. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graph, secara umum  graf digolongkan menjadi dua jenis :

        1. Graf sederhana (simple graph)Graf yang tidak mengandung gelung maupun sisi ganda  dinamakan graph sederhana. Jaringan komputer merupakan contoh aplikasi graf sederhana.

      2. Graf tak-sederhana (unsimple graph/multigraph)Graf tak sederhana dibagi menjadi 2,yaitu graf ganda dan graf semu. Graf ganda ialah graf yang mengandung sisi ganda. Graf semu ialah graf yang mengandung gelang.

b. Berdasarkan jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis:

       1. Graf Berhingga (Limited Graph)Graf berhingga adalah graph yang jumlah simpulnya, n, berhingga.

       2.Graf Tak-Berhingga (Unlimited Graph)Graf yang jumlah simpulnya, n, tidak berhingga             banyaknya disebut graph tak-berhingga.

 c. Berdasarkan orientasi arah pada sisi, maka secara umum graph dibedakan atas 2 jenis:

     1. Graph Tak-Berarah (Undirected Graph) Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak-berarah.

     2. Graph Berhingga (Directed Graph) Graph yang setiap sisinya diberikan orientasi arah disebut sebagai graph berarah..

 

MASALAH GRAF

1.     Tingkat kerumitan yang cukup tinggi, meskipun isi dan teorinya terlihat sederhana 

2.     Harus menemukan rute terpendek (contoh kasus dalam kehidupan sehari-hari: peta/gps)

SOLUSI PEMECAHAN MASALAH GRAF

Setelah memiliki beberapa masalah yang belum terpecahkan maka untuk menemukan solusi yang tepat maka digunakanlah metode Algoritma Greedy. Karena kemungkinan akan memperoleh hasil yang cukup baik.

* Algoritma Greedy

Algoritma Greedy adalah jenis algoritma yang menggunakan langkah pendekatan penyelesaian masalah dengan cara membuat pilihan optimasi yang memungkinkan memiliki nilai yang paling mendekati nilai maksimal

Kelebihan dan Kekurangan dari Algoritma Greedy

• Kekurangan : tidak akan mendapat nilai maksimum
• Kelebihan : dapat memberikan solusi dalam waktu yang cepat dan memiliki nilai yang mendekati nilai maksimum

 

Source : https://tugasanalgo4blog.wordpress.com/2016/10/07/graph-problems/

                https://livebook.manning.com/book/classic-computer-science-problems-in-java/chapter-4/v-4/#:~:text=A%20graph%20is%20an%20abstract,of%20the%20connections%20an%20edge.