ani blog: ringkasan pohon(tree) dan hutan(forest), matematika diskrit

A. Pohon

A.1. Pohon(tree) dan Hutan(forest)

- Definisi pohon yaitu misal G adalah graf sederhana,maka G disebut pohon jika dan hanya jika G tidak memuat sirkuit dan G terhubung.

- Pohon semu(trivial tree)adalah pohon yang hanya terdiri dari satu titik.Pohon kosong (empty tree)adalah pohon yang tidak memiliki titik. Spanning tree yaitu sebuah pohon T yang dapat dibentuk,sedemikian hingga T merupakan sub graf dari G dan T memuat semua titik dari G.

- Definisi hutan yaitu jika dan hanya jika G tidak memiliki sirkuit.Hutan merupakan Graf yang tidak terhubung yang komponen –komponennya terdiri atas pohon.

- teorema 2.7:

jika G sebuah pohon dengan n titik,maka G memiliki (n-1) garis.

-Definisi:

misal T adalah pohon,daun(leaf/terminal vertex)adalah titik dalam T yang berderajat 1. Titik cabang adalah titik dalam T yang berderajat lebih dari 1.

A.2. Pohon Berakar dan Pohon Biner

Ø Pohon Berakar :

Definisi: Pohon Berakar (rooted tree) adalah pohon dimana ada satu titik yang dikhususkan dari titik lain dan titik itu disebut akar(root)

Tingkat(level) adalah banyaknya garis antara titik tersebut dengan akar.Tinggi (Height) pohon adalah tinggi maksimum yang dimiliki oleh titik-titik pohon. Anak (children) dari titik v adalah semua titik yang berhubungan langsung dengan v,tetapi memiliki tingkat yang lebih tinggi dari v(berada dibawah v),v disebut orang tua (parent) u. Saudara (sibling) adalah dua titik atau lebih yang memiliki orang tua sama.

Ø Pohon Biner

Definisi: Pohon Biner (binary tree) adalah pohon berakar yang setiap titiknya memiliki banyak 2 anak.yang disebut anak kanan dan anak kiri.

Pohon biner penuh adalah pohon biner yang setiap titiknya memiliki tepat 2 anak.

- Maksimum jumlah titik

T adalah pohon biner penuh,maka:

pada tingkat 0(akar) ada 1(2⁰) titik, pada titik 1 ada 2(2¹),…..,pada tingkat n ada 2ⁿ titik

jadi keseluruhan jumlah titik adalah 2⁰+2¹+…+2ⁿ, dengan rasio 2,sehingga jumlahnya

a(r^k-1)/r-1=2ⁿ⁺¹-1/2-1=2ⁿ⁺¹-1 dimana k=n+1

- maksimum jumlah daun

daun adalah titik-titik pada tingkat tertinggi,yaitu n, sehingga maksimum jumlah daun=2ⁿ

- maksimum jumlah cabang

jumlah titik = jumlah daun T + jumlah titik cabang T

2ⁿ⁺¹-1 = 2ⁿ + Jumlah titik cabang T

jumlah titik cabang T =(2ⁿ⁺¹-1)-2ⁿ

= 2ⁿ-1

- maksimum jumlah garis

pohon dengan n titik memiliki (n-1)garis.sehingga pohon yang memiliki 2ⁿ-1 buah titik memiliki 2ⁿ⁺¹-1-1 = 2ⁿ⁺¹-2 buah garis.

2. a. Batas bawah dari {a,b}={c,d,e}

b. Batas bawah dari {a,c}={d,e}

c.impimum dari {a,b}={c,d}

d. Impimum dari {a,c}={e}

4. a. Jika Graf A(graf pertama) merupakan graf Hamilton,maka akanmemiliki sifat:

- B adalah sub graf yang memuat semua titik dari A ( ada 7 titik)

-jumlah garis sama dengan jumlah titik yaitu 7

- semua garis dalam B berderajat 2

namun ternyata ada titik yang berderajat 4 sebanyak 3 titik dan berderajat 6 sebanyak 1 titik,sehingga harus menghilangkan 10 garis sekaligus dalam A. Padahal jumlah garis dalam A sebanyak 12 garis,kalau dihilkangkan 10 maka sisa garis dalam A ada 2,,akibatnya graf A bukan graf Hamilton.

b. Graf C( Graf kedua) ternyata memiliki 21 titik,40 garis,dengan 10 titik berderajat 5,dan 1 titik berderajat 10. maka harus dihilangkan 38 garis agar menjadi graf Hamilton,,sementara jumlah garis dalam Graf C ada sebanyak 40 gari,jika dihilangkan 38 garis maka hanya tersisa 2 garis,akibatnya graf C bukan merupakan graf Hamilton.

5. a. Sebuah graf G = (V,E) disebut graf planar apabila graf tersebut dapat digambarkan dalam sebuah bidang datar tanpa ada sisi/edge yang saling berpotongan (kecuali sisi sisi berpotongan pada sebuah verteks).

Contoh Graf Planar