Flashcard dasar-dasar teori graf

Question 1

Apa itu graf $G=(V,E)$?

Accepted Answer

Graf adalah pasangan berurutan $G=(V,E)$ dengan $V$ himpunan simpul (node) dan $E$ himpunan sisi, tiap sisi menghubungkan dua simpul (pada graf tak berarah, sebuah sisi adalah pasangan tak berurutan $\{u,v\}$).

Question 2

Apa perbedaan antara walk, path, dan cycle?

Accepted Answer

Walk boleh mengulang simpul/sisi. Path adalah walk tanpa simpul yang berulang. Cycle adalah path tertutup (awal = akhir) tanpa simpul berulang kecuali simpul pertama/terakhir.

Question 3

Apa arti sebuah graf planar, dan apa rumus Euler untuk graf planar terhubung?

Accepted Answer

Planar berarti dapat digambar pada bidang tanpa perpotongan sisi (kecuali di simpul). Untuk sebuah embedding planar yang terhubung, $$V-E+F=2,$$ dengan $F$ adalah banyaknya muka (termasuk muka luar).

Flashcard dasar-dasar teori graf

Kuasai Matematika dengan AI

Sumber Belajar

Dipercaya & Diakui