Graf Flashcards
Apa itu Minimum Spanning Tree (MST)?
Graf berbobot tak berarah yang menghubungkan semua titik tanpa membentuk siklus dan dengan total bobot minimum.
Sebutkan langkah-langkah dalam algoritma Kruskal!
- Bentuk dahulu graf-nya tanpa edge
- Ambil bobot edge yang terkecil
- Tambahkan edge tersebut ke graf
- Jika membentuk cycle, jangan diambil
- Lakukan sampai semua node terhubung
Apa definisi degree dalam graf?
Banyaknya edge dimana v merupakan salah satu ujung dari edge tersebut.
Apa itu Topological Sort?
Pengurutan simpul secara linier sehingga untuk setiap sisi berarah u & v, simpul u berada sebelum v dalam pengurutan tersebut di Directed Acyclic Graph (DAG).
Apa yang dimaksud dengan Shortest Path?
Permasalahan pada graf berbobot untuk mencari jalur yang meminimalkan jumlah bobot sisi pembentuk jalur.
Apa langkah awal dalam algoritma Dijkstra?
Set semua bobot node-nya menjadi infinity, kecuali bobot node a yang diset jadi 0.
Apa perbedaan antara Weighted Graph dan Unweighted Graph?
- Weighted Graph: Setiap edge memiliki bobot
- Unweighted Graph: Setiap edge tidak ada bobot
Apa itu Directed Graph?
Graf yang node-nodenya dihubungkan oleh edge yang memiliki arah.
Apa ciri-ciri dari sebuah Tree?
- Jika ada n node, maka ada (n-1) edge
- Mengunjungi node lain dari sebuah node
- Tidak terdapat cycle
Apa itu Euler Path dan Euler Circuit?
- Euler Path: Lintasan melewati setiap edge dengan node awal dan akhir berbeda
- Euler Circuit: Lintasan melewati setiap edge dengan node awal dan akhir sama
Apa yang dimaksud dengan graf dalam matematika dan ilmu komputer?
Sekumpulan objek terstruktur di mana beberapa pasangan objek mempunyai hubungan atau keterkaitan tertentu.
Jika ada 2 node dengan degree ganjil, apa yang dapat dihasilkan?
Sebuah Euler Path.
Berapa banyak jalan yang menghubungkan kota x dengan kota lainnya?
Total edge = (total degree/2)
Berapa banyak rumah teman yang bisa dicapai Kwaok dalam waktu 10 menit?
…………….
Berapa banyak konfigurasi cara teman-teman Pak Dengklek pergi ke rumahnya?
…………….
Berapa banyak node berbeda yang dapat dicapai dengan rute melalui tepat 4 edge dimulai dari node 1?
3, 4, 5, 6, 7
Di sebuah grid, jika Pak Dengklek ingin pindah ke sel, berapa banyak jalur yang dapat dilalui?
…………….
