· Teorema. Misalkan G = (V, E) adalah graf tak-berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan di bawah ini adalah ekivalen:

1. G adalah pohon.

2. Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal.

3. G terhubung dan memiliki m = n – 1 buah sisi.

4. G tidak mengandung sirkuit dan memiliki m = n – 1 buah sisi.

5. G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit.

6. G terhubung dan semua sisinya adalah jembatan.

· Teorema di atas dapat dikatakan sebagai definisi lain dari pohon.

Poskan Komentar

[+] Komentar membangun lebih disukai
[+] Admin akan menghapus komentar yang melecehkan, kasar, dan bertendensi SARA.
[+] Selain Admin, link aktif dalam komentar akan dihapus

 
Top