Graf Pohon - Teori Graf - haimatematika

Hai sobat matematika

Suatu graf yang tidak memiliki sisi ganda dan sirkuit disebut graf pohon.

Graf pohon sudah lama digunakan dalam berbagai bidang. Matematikawan Inggris, Arthur Cayley menggunakan graf pohon untuk menghitung tipe-tipe bahan senyawa kimia. Peneliti selanjutnya juga menggunkan pemodelan graf pohon ini di dalam bidangnya masing-masing.

Secara khusus, graf pohon sangat banyak dan besar manfaatnya di bidang ilmu komputer. Misalnya, graf pohon digunakan dalam mencari efisiensi suatu algoritma. Graf pohon juga banyak digunakan dalam menyusun algoritma dalam teori permainan (games theory).

Definisi Graf Pohon

Graf pohon secara bentuknya memang mirip dengan struktur pohon.

Sebuah pohon tidak akan mempunyai cabang ganda ataupun cabang yang melingkar. Hal ini digunakan dalam pendefinisian graf pohon.

DEFINSI GRAF POHON
Graf pohon adalah graf terhuibung yang tidak memiliki sisi ganda dan tidak memuat sirkuit

Perhatikan contoh gambar di bawah ini untuk lebih jelasnya

Jelas bahwa graf \(G_{1}\) dan graf \(G_{2}\) adalah graf pohon karena tidak terdapat sisi ganda dan sirkuit.

Sedangkan graf \( G_{3} \) memuat sirkuit \( e, b, a, d, e\) sehingga tidak termasuk graf pohon.

Sama juga dengan graf \(G_{4}\) bukan graf pohon karena tidak terhubung.

Baca Juga : Pembuktian dengan Induksi Matematika

Pada gambar di atas disebutkan bahwa terdapat graf yang tidak memuat sisi ganda dan tidak memuat sirkuit juga, tapi graf tidak terhubung (graf \(G_{4}\) ).

Graf semacam ini dinamakan graf hutan (forest) . Jadi graf hutan terdiri dari berbagai macam graf pohon.

Gambar dibawah ini contoh graf hutan yang memuat tiga graf pohon

Sama juga kan dengan hutan yang Anda pahami. 😁

Selain definisi di atas suatu graf pohon bisa dikarekterisasi dengan suatu sifat tertentu.

Apa sifat itu? Silahkan baca teorema berikut

TEOREMA 1
Pernyataan di bawah ini adalah ekuialen
#1. Graf \( T \) adalah graf pohon

#2. Terdapat lintasan tunggal untuk sebarang dua titik yang berbeda.

#3. Graf \( T \) merupakan terhubung minimal, yaitu graf \( T \) terhubung akan tetapi \(T - e \) bukan graf terhubung untuk setiap sisi \( e \) di \( T \).

#4. Graf \( T \) adalah graf tak bersikuit yang maksimal, yaitu \( T \) tak memuat sirkuit namun \( T+xy \) memiliki dengan \(x , y \in T\) adalah sebarang dua titik yang bertetangga.

Teorema 1 di atas menyebutkan bahwa ada 3 ciri-ciri dimana suatu graf \( T \) dikatakan graf pohon.

Sebuah pohon pasti ada yang dinamakan akar, begitu juga dengan graf pohon ada suatu titik yang dijadikan sebagai akar.

Graf Pohon Berakar

Di berbagai penggunaan graf pohon, suatu titik di graf pohon tersebut dinamakan sebagai akar dari graf pohon.

Ketika sudah mensetting satu titik sebagai akar, maka kita bisa membuat arah dari graf pohon tersebut.

DEFINISI GRAF POHON BERAKAR
Graf pohon berakar adalah graf pohon yang satu titik dari graf pohon tersebut dijadikan sebagai akar dan setiap sisi mengarah keluar dari akar tersebut.

Perhatikan gambar graf pohon di bawah ini

Graf sebelah kiri adalah graf pohon. Dua graf pohon disebelahnya adalah graf pohon berakar yang menjadikan titik \( a \) dan titik \( c \) sebagai akarnya.

Beberapa terminologi berkaitan graf pohon berakar diantaranya adalah

TERMINOLOGI PADA GRAF POHON
Misalkan graf pohon berakar \( T \)
#1. Jika \( v \) adalah titik di graf pohon berakar \( T \) yang bukan akar. Orang tua dari titik \( v\) adalah suatu titik tunggal \( u \) sedemikian sehingga terdapat sisi berarah dari \( u \) ke \( v \).

#2. Jika \( v \) mempunyai orang tua titik \( u \) maka titik \( v \) dikatakan anak dari titik \( u \).

#3. Suatu titik yang mempunyai orang tua yang sama dikatakan saudara.

#4. Pendahulu dari suatu titik \( v \) yang bukan akar adalah titik di lintasan dari akar ke titik \( v \).

#5. Keturunan suatu titik \( v\) adalah titik titik yang mempunyai pendahulu titik \( v \).
Suatu titik dikatakan daun jika dan hanya jika titik tersebut tidak mempunyai anak.

#6. Titik yang mempunyai anak dinamakan titik internal.

#7. Jika \( a \) adalah titik di dalam graf pohon, subgraf pohon dengan akar \( a \) adalah subgraf dari graf pohon yang memuat \( a \) dan keturunannya dan semua sisi yang bersisian dengan keturunan tersebut.

Untuk memperjelas berbagai macam terminologi dari 1 - 7 pada graf pohon, perhatikan contoh gambar berikut

Pada gambar graf pohon berakar di atas, titik \( a \) adalah akar. Orang tua titik \(c \) adalah \( b \). Sedangkan anak dari titik \( g \) adalah \( h, i, j \). Saudara dari titik \(h \) adalah titik \( i, j \). Pendahulu dari titik \( e \) adalah \( c, b, a \). Keturunan dari titik \( b \) adalah \( c, d, e \). Titik internal dari graf berakar tersebut adalah \( a, b, c, g, h, j\). Yang menjadi daun adalah \( d, e, f, k, i, l, m \).

Sedangkan subgraf pohon berakar \( g\) adala graf pohon berikut

Salah satu macam graf pohon yang sering digunakan dalam banyak aplikasi adalah graf pohon yang mempunyai ciri banyak titik internal sama dengan banyak anak.

Baca Juga : Pembahasan UAS matematika diskrit

DEFINISI GRAF POHON m-ary
Graf pohon berakar dikatkan garf pohon m-ary jika untuk setiap titik internal tidak mempunyai lebih dari m anak.

Graf pohon dikatakan graf pohon m-ary lengkap jika dan hanya jika untuk setiap titik internalnya tepat mempunyai m anak.

Suatu graf pohon m-ary dengan m=2 dikatakan graf pohon binary.

Gambar berikut memberikan ilustrasi dari definisi di atas

Graf \( T_{1} \) merupakan graf pohon binary lengkap karena setiap titik internalnya mempunyai anak sebanyak 2.

Sedangkan graf \( T_{2}\) termasuk graf pohon 3-binary lengkap karena setiap titik internalnya mempunyai anak 3.

Perhatikan contoh gambar lagi di bawah

Graf \(T_{3}\) mempunyai setiap titik internal dengan 5 anak maka graf \(T_{3}\) disebut graf pohon 5-ary lengkap. Sedangkan graf \(T_{4}\) bukan graf pohon m-ary lengkap karena terdapat titik internal yang mempunyai 3 anak dan 2 anak.

Graf Pohon - Teori Graf

4/ 5

Oleh Mohammad Mahfuzh Shiddiq

Mohammad Mahfuzh Shiddiq December 22, 2018 Komentar