BAGUS SEPTIAWAN

Pohon berakar adalah pohon yang sebuah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar. Akar mempunyai derajat masuk nol dan simpul-simpul lainnya berderajat masuk sama dengan satu. Daun atau simpul terminal adalah simpul yang mempunyai derajat keluar sama dengan nol. Simpul dalam atau simpul cabang adalah simpul yang mempunyai derajat keluar tidak sama dengan nol. Terminologi pada Pohon Berakar Child atau children (Anak) dan parent (orangtua) Path (lintasan) Descendant (Keturunan) dan ancestor (leluhur) Sibling (saudara kandung) Subtree (subpohon) Degree (derajat) Leaf (daun) Internal nodes (simpul dalam) Level (tingkat) Height (tinggi) atau depth (kedalaman) Child atau children (Anak) dan parent (orangtua) Simpul y dikatakan  anak  simpul x jika   ada sisi dari simpul x ke y   dan  Orangtua  dari simpul y adalah simpul x. Pada gambar G1 :   Simpul b, c dan d --> anak dar...

Definisi Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit Sifat-sifat Pohon : + 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. Pohon Merentang (spanning tree) •  Pohon merentang dari graf terhubung adalah upag...