Teori Grafik - Pohon
Pohon adalah grafik yang tidak mengandung satu siklus pun. Mereka mewakili struktur hierarki dalam bentuk grafik. Pohon termasuk dalam kelas grafik yang paling sederhana. Terlepas dari kesederhanaannya, mereka memiliki struktur yang kaya.
Pohon menyediakan berbagai aplikasi berguna, mulai dari pohon keluarga hingga serumit pohon dalam struktur data ilmu komputer.
Pohon
SEBUAH connected acyclic graphdisebut pohon. Dengan kata lain, graf terhubung tanpa siklus disebut pohon.
Tepi pohon dikenal sebagai branches. Elemen pohon disebut simpul mereka. Node tanpa node turunan disebutleaf nodes.
Sebuah pohon dengan simpul 'n' memiliki tepi 'n-1'. Jika ia memiliki satu tepi lebih banyak dari 'n-1', maka tepi ekstra tersebut jelas harus berpasangan dengan dua simpul yang mengarah untuk membentuk sebuah siklus. Kemudian menjadi grafik siklik yang merupakan pelanggaran bagi grafik pohon.
Example 1
Grafik yang ditampilkan di sini adalah pohon karena tidak memiliki siklus dan terhubung. Ia memiliki empat simpul dan tiga sisi, yaitu, untuk tepi 'n' simpul 'n-1' seperti yang disebutkan dalam definisi.
Note - Setiap pohon memiliki setidaknya dua simpul berderajat satu.
Example 2
Dalam contoh di atas, simpul 'a' dan 'd' memiliki derajat satu. Dan dua simpul lainnya 'b' dan 'c' memiliki derajat dua. Hal ini dimungkinkan karena untuk tidak membentuk siklus, harus ada setidaknya dua sisi tunggal di manapun dalam grafik. Itu tidak lain adalah dua sisi dengan satu derajat.
Hutan
SEBUAH disconnected acyclic graphdisebut hutan. Dengan kata lain, kumpulan pohon yang terputus-putus disebut hutan.
Example
Grafik berikut terlihat seperti dua sub-grafik; tetapi ini adalah grafik tunggal yang tidak terhubung. Tidak ada siklus dalam grafik ini. Karenanya, jelas itu adalah hutan.
Merentang Pohon
Misalkan G adalah graf terhubung, maka sub-graf H dari G disebut pohon rentang dari G jika -
- H adalah pohon
- H berisi semua simpul G.
Pohon rentang T dari graf tak berarah G adalah subgrafik yang mencakup semua simpul G.
Example
Dalam contoh di atas, G adalah graf terhubung dan H adalah sub-graf dari G.
Jelas, grafik H tidak memiliki siklus, ini adalah pohon dengan enam sisi yang kurang satu dari jumlah total simpul. Oleh karena itu H adalah pohon Rentang dari G.
Peringkat Sirkuit
Misalkan 'G' adalah graf terhubung dengan ujung 'n' dan tepi 'm'. Pohon rentang 'T' dari G berisi (n-1) tepi.
Oleh karena itu, jumlah tepi yang perlu Anda hapus dari 'G' untuk mendapatkan pohon rentang = m- (n-1), yang disebut peringkat sirkuit G.
Rumus ini benar, karena dalam pohon bentang Anda harus memiliki tepi 'n-1'. Dari tepi 'm', Anda perlu mempertahankan tepi 'n – 1' pada grafik.
Oleh karena itu, menghapus tepi 'n – 1' dari 'm' memberikan tepi yang akan dihilangkan dari grafik untuk mendapatkan pohon rentang, yang seharusnya tidak membentuk siklus.
Example
Perhatikan grafik berikut -
Untuk grafik yang diberikan pada contoh di atas, Anda memiliki m = 7 sisi dan n = 5 simpul.
Maka peringkat sirkuitnya adalah -
Example
Misalkan 'G' adalah graf terhubung dengan enam simpul dan derajat dari setiap simpul adalah tiga. Temukan peringkat sirkuit 'G'.
Dengan jumlah teorema derajat simpul,
Teorema Kirchoff
Teorema Kirchoff berguna untuk mencari jumlah pohon merentang yang dapat dibentuk dari graf terhubung.
Example
Matriks 'A' diisi seperti, jika ada tepi antara dua simpul, maka itu harus diberikan sebagai '1', jika tidak '0'.
$$ A = \ begin {vmatrix} 0 & a & b & c & d \\ a & 0 & 1 & 1 & 1 \\ b & 1 & 0 & 0 & 1 \\ c & 1 & 0 & 0 & 1 \\ d & 1 & 1 & 1 & 0 \ end {vmatrix} = \ begin {vmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \ end {vmatrix} $$Dengan menggunakan teorema kirchoff, itu harus diubah dengan mengganti nilai diagonal prinsip dengan derajat simpul dan semua elemen lainnya dengan -1.
$$ = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = M $$ $$ M = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = 8 $$ $$ Co \: \: factor \: \: of \: \: m1 \: \: = \ begin {vmatrix } 2 & 0 & -1 \\ 0 & 2 & -1 \\ - 1 & -1 & 3 \ end {vmatrix} $$Jadi, jumlah pohon merentang = 8.