1.
Ambillah selembar kertas dan gambarlah 8 simpul yang tersusun melingkar.
Kita akan menambahkan sisi-sisi pada graf ini sesuai beberapa persyaratan.
(a)
Pertama, tambahkan sesedikit mungkin sisi agar graf yang dihasilkan terhubung. Artinya, harus terdapat lintasan di antara setiap pasangan simpul (tentu saja sebuah lintasan dapat menggunakan lebih dari satu sisi).
Berapa banyak sisi pada graf yang Anda gambar?
(b)
Apakah graf yang Anda peroleh merupakan pohon?
-
Ya, karena graf terhubung dan tidak memuat siklus
-
Tidak, graf memuat siklus
-
Tidak, graf tidak terhubung
-
Tidak, graf tidak terhubung dan memuat siklus
(c)
Sekarang mulailah kembali dengan graf kosong. Kali ini, tambahkan sebanyak mungkin sisi dengan syarat graf yang dihasilkan tidak memuat siklus.
Berapa banyak sisi pada graf yang Anda gambar?
(d)
Apakah graf yang Anda peroleh merupakan pohon?
-
Ya, karena graf terhubung dan tidak memuat siklus
-
Tidak, graf memuat siklus
-
Tidak, graf tidak terhubung
-
Tidak, graf tidak terhubung dan memuat siklus