📋 Daftar Isi
Definisi
Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit.
Sedangkan Hutan (forest) adalah kumpulan pohon yang saling lepas atau graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung adalah pohon.
Sifat-Sifat Pohon
Misalkan G = (V, E) adalah graf tak-berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan di bawah ini adalah ekuivalen:
- G adalah pohon.
- Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal.
- G terhubung dan memiliki m = n – 1 buah sisi.
- G tidak mengandung sirkuit dan memiliki m = n – 1 buah sisi.
- G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya
satu sirkuit. - G terhubung dan semua sisinya adalah jembatan.
Sumber : Buku Matematika Diskrit (Rinaldi Munir)
Materi Lengkap
Silakan baca juga beberapa artikel menarik kami tentang Pohon, daftar lengkapnya adalah sebagai berikut.
