KEMAMPUAN KOMUNIKASI MATEMATIS

POHON (TREE)OLEH:APRIADANI HARAHAP8146171007DEWI LESTARI8146171016HADI RITONO8146171028NOVA JUNIATI8146171057YESSI JURNALA8146171089Dosen Pengampu:Yulita Moliq, Ph. D

POHONPohon adalah sebuah graf terhubung yang tidak mengandung sirkuit. Karena mengandung graf terhubung, maka pohon selalu memiliki lintasan (path) yang menghubungkan setiap dua simpul pada pohon. Lambang pohon adalah T.Berikut diberikan beberapa contoh

Pohon pohon bukan pohon bukan pohon

Teorema 3.1 : setiap pohon nontrivial memiliki paling sedikit dua simpul akhir.

Berikut diberikan beberapa contoh

Teorema 3.2 : 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 tunggalG terhubung dan memiliki m = n-1 buah sisiG tidak mengandung sirkuit dan memiliki m = n-1 buah sisiG tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuitG terhubung semua sisinya adalah jembatan (jembatan adalah sisi yang bila dihapus menyebabkan graf terpecah menjadi dua komponen)

Contoh Sebuah pohon mempunyai 2n buah simpul berderajat 1, 3n buah simpul berderajat 2, dan n buah simpul berderajat 3. Tentukan banyaknya simpul dan sisi di dalam pohon tersebut!Penyelesaian:Menurut Lemma jabat tangan, jumlah derajat semua simpul di dalam graf adalah 2 kali jumlah sisi di dalam graf tersebut. jadi,

Menurut teorema sebelumnya dimana jumlah sisi pada sebuah pohon adalh m=n-1, jadi

LanjutanDengan mensubtitusikan per 2 ke pers ke 1, maka diperoleh:

Jadi jumlah simpul pada pohon = 6n=6x2=12 dan jumlah sisi = 6n-1=11

HutanBeberapa pohon dapat membentuk hutan. Hutan (forest) adalah kumpulan pohon saling lepas. Sehingga hutan merupakan graf tak-terhubung yang tidak mengandung sirkuit, yang dalam hal ini setiap komponen di dalam graf terhubung tersebut adalah pohon.Berikut ini adalah gambar hutan yang terdiri dari 3 buah pohon

Pohon MerentangMisalkan G adalah sebuah graf. Sebuah pohon di G yang memuat semua titik G disebut pohon rentang (spanning tree) dari G. Misalkan kita mempunyai graf G seperti pada gambar di bawah ini. Terdapat 3 pohon rentang dari graf G, yaitu graph A, B, dan C. Tampak jelas bahwa graf A, B, dan C masing-masing memuat semua simpul dari graf G serta mengandung sisi-sisi dari G demikian sehingga tidak terbentuk sirkuit.

TeoremaSetiap graf terhubung mempunyai paling sedikit satu buah pohon merentang.Contoh: Graf G memuat pohon rentang T1, T2, T3

Jadi, pohon merentang:- Pohon merentang dari graf terhubung adalah subgraf merentang yang berupa pohon- Pohon merentang diperoleh dengan memutuskan sirkuit di dalam graf.

Pohon Rentang MinimunJika G adalah graf berbobot, maka bobot pohon merentang T dari G didefinisikan sebagai jumlah bobot semua sisi di T. Pohon merentang yang berbeda mempunyai bobot yang berbeda pula. Di antara semua pohon merentang di G, pohon merentang yang berbobot minimum dinamakan pohon merentang minimum (minimum spanning tree).

contohMisalkan pemerintah akan membangun jalur rel kereta api yang menghubungkan sejumlah kota seperti yang digambarkan oleh graf pada gambar 6. Membangun jalur rel kereta api biayanya mahal, karena itu pembangunan jalur ini tidak perlu menghubungkan langsung dua buah kota; tetapi cukup membangun jalur kereta seperti pohon merentang. Karena di dalam sebuah graf mungkin saja terdapat lebih dari satu pohon merentang, harus dicari pohon merentang yang mempunyai jumlah jarak terpendek, denga kata lain harus dicari pohon merentang minimum.

Algoritma Prim

Contoh:Kita akan mencari pohon merentang minimum pada graf yang ditunjukkan pada gambar dengan algoritma Prim

Algoritma kruskal

Langkah 0: sisi-sisi dari graf sudah diurut menaik berdasarkan bobotnya dari bobot kecil ke bobot besarLangkah 1: T masih kosong Langkah 2: pilih sisi (u, v) dengan bobot minimum yang tidak membentuk sirkuit di T. Tambahkan (u, v) ke dalam T.Langkah 3: ulangi langkah 2 n-2 kali

Contoh:Carilah pohon merentang minimumnya dengan algoritma kruskal.

Pohon BerakarPohon yang sebuah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar dinamakan pohon berakar (rooted tree).Akar mempunyai derajat masuk sama dengan nol dan simpul-simpul lainnya berderajat masuk sama dengan satu. Simpul yang mempunyai derajat keluar sama dengan nol disebut daun atau simpul terminal. Simpul yang mempunyai derajat keluar tidak sama dengan nol disebut simpul dalam atau simpul cabang.Setiap simpul di pohon dapat dicapai dari akar dengan sebuah lintasan tunggal (unik).

Pohonpohon berakar

Terminologi Pada Pohon BerakarAnak (child atau children) dan Orangtua (parent)Pada Gambar dibawah ini b,c,dan d adalah anak-anak simpul a, dan a adalah orang tua dari anak-anak itu. e dan f adalah anak-anak simpul b, dan b adalah orangtua dari e dan f. g adalah anak simpul d, dan d adalah orangtua dari g. Simpul h,i,j,l dan m tidak mempunyai anak Gambar 1

Lintasan (path)Lintasan dari simpul ke simpul adalah runtutan simpul sedemikian sehingga adalah orangtua dari untuk Dari pohon pada Gambar 1, lintasan dari a ke j adalah a, b, e, j. Panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan, yaitu k-1. Panjang lintasan dari a ke j adalah 3.

Keturunan (descendant) dan Leluhur (ancestor)Jika terdapat lintasan dari simpul x ke simpul y di dalam pohon, maka x adalah leluhur dari simpul y, dan y adalah keturunan dari simpul x.

Upa PohonMisalkan x adalah simpul di dalam pohon T. Yang dimaksud dengan upapohon dengan x sebagai akarnya ialah upagraf sedemikian sehingga V mengandung x dan semua keturunannya dan E mengandung sisi-sisi dalam semua lintasan yang berasal dari x. Sebagai contoh, adalah upapohon dari pohon pada gambar 7 dengan V={b,e,f,h,i,j} dan E={(b,e),(b,f),(e,h),(e,i),(e,j)} dan b adalah simpl akarnya. Terdapat banyak upapohon T. Dengan pengertian di atas, jika x adalah simpul, maka akar tiap-tiap upapohon dari x disebut anak, dan x adalah orangtua setiap akar pohon.

Gambar 7 Upapohon dengan b sebagai akarnya.

Saudara Kandung (Sibling)Simpul yang berorangtua sama adalah saudara kandung. Tetapi, g bukan saudara kandung e, karena orangtua mereka berbeda.

Derajat (Degree)Derajat sebuah simpul pada pohon berakar adalah jumlah upa pohon (atau jumlah anak) pada simpul tersebut. Pada gambar 6, derajat a adalah 3, derajat b adalah 2, derajat d adalah 1 dan derajat c adalah 0. Jadi, derajat yang dimaksudkan di sini adalah derajat-keluar.

Daun (Leaf)Simpul yang berderajat nol (atau tidak mempunyai anak) disebut daun. Simpul h, i, j, f, c, l, dan m adalah daun.

Simpul Dalam (internal nodes)Simpul yang mempunyai anak disebut simpul dalam. Simpul d, e, g, dan k pada gambar 1 adalah simpul dalam.Aras (level) atau TingkatAkar mempunyai aras = 0, sedangkan aras simpul lainnya = 1 + panjang lintasan dari akar ke simpul tersebut. Beberapa literature memulai nomor aras dari 0, literature lainnya dari 1. Sebagai konvensi, kita memulai penomoran aras dari 0. Perhatikan gambar berikut:

Tinggi (height) atau kedalaman (depth)Aras maksimum dari suatu pohon disebut tinggi atau kedalaman pohon tersebut. Atau, dapat juga dikatakan, tinggi pohon adalah panjangmaksimum lintasan dari akar ke daun. Pohon pada gambar di atas mempunyai tinggi 4.

Pohon Berakar TerurutPohon berakar yang urutan anak-anak panahnya penting disebut pohon terurut (ordered tree)

Pohon n-aryPohon n-ary adalah pohon berakar yang setiap simpul cabangnya mempunyai paling banyak n buah anak.Contoh :Pohon n-ary digunakan untuk merepresentasikan struktur kalimat dalam bahasa alam (natural language) maupun dalam bahasa pemrograman. Pohon penurunan kalimat disebut pohon parsing. Gambar 11 memperlihatkan cara penurunan kalimat dalam bahasa inggris yang berbunyiA tall boy wears a red hat

Jumlah Daun Pada Pohon N-Ary PenuhPohon n-ary penuh adalah pohon yang setiap simpulnya tepat mempunyai n buah anak. Pada pohon n ary penuh dengan tingkat h, jumlah daun adalah nh.Berikut adalah contoh pohon 3-ary penuh dengan jumlah daun 9.

Pohon BinerPohon n-ary yang paling penting adalah pohon biner. Pohon biner adalah pohon n-ary jika n=2. Pohon biner adalah pohon yang setiap simpul cabangnya mempunyai paling banyak 2 buah anak

Pohon biner penuh adalah pohon biner yang setiap simpulnya mempunyai tepat dua buah anak, kiri dan kanan, kecuali simpul pada aras bawah

Pohon Biner SeimbangPohon biner seimbang adalah pohon biner dengan perbedaan tinggi antara upapohon kiri dengan upapohon kanan maksimal 1. Pada pohon biner seimbang dengan tinggi h, semua daun berada pada aras h atau . Pohon T1 dan Pohon T2 pada gambar berikut adalah pohon seimbang, sedangkan pohon T3 bukan pohon seimbang karena perbedaan upapohon kiri dan upapohon kanan tidak maksimal satu.

TERIMA KASIH