Matematika Diskrit: Definisi dan Sifat Pohon (Tree)

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:

  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.

Sumber : Buku Matematika Diskrit (Rinaldi Munir)


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Pohon, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up