SPANNING TREE

SPANNING TREE

Dalam matematika bidang teori graph , sebuah pohon rentang T dari tersambung , graf tak berarah G adalah sebuah pohon yang terdiri dari semua simpul dan beberapa (atau mungkin semua) dari tepi G . Informal, pohon rentang dari G adalah pilihan tepi G yang membentuk pohon merentang setiap simpul.Artinya, setiap vertex terletak di pohon, tetapi tidak ada siklus (atau loop) terbentuk. Di sisi lain, setiap jembatan dari G harus milik T .
Sebuah pohon rentang dari graf terhubung G juga dapat didefinisikan sebagai satu set maksimal tepi G yang berisi siklus tidak ada, atau sebagai seperangkat minimal tepi yang menghubungkan semua titik.
Dalam bidang-bidang tertentu teori grafik sering berguna untuk mencari pohon rentang minimum dari sebuah graf berbobot . masalah optimasi lain di pohon mencakup juga telah dipelajari, termasuk mencakup pohon maksimum, pohon minimum yang mencakup setidaknya simpul k, pohon rentang minimum dengan di tepi k paling per titik (Gelar-Dibatasi Spanning Tree) , pohon merentang dengan jumlah daun terbesar (erat kaitannya dengan terkecil terhubung mendominasi set ), pohon merentang dengan daun paling sedikit (berkaitan erat dengan masalah jalan Hamilton ), dengan rentang diameter pohon minimal, dan dilatasi minimum spanning tree.
Sebuah hutan yang mencakup adalah jenis subgraf yang generalises konsep pohon rentang. Namun, ada dua definisi umum digunakan. Salah satunya adalah bahwa hutan membentang adalah subgraf yang terdiri dari pohon rentang pada setiap komponen terhubung dari graf. (Dengan kata lain, itu adalah siklus subgraf bebas maksimal.) Definisi ini adalah umum di ilmu komputer dan optimasi. Itu juga merupakan definisi yang digunakan ketika mendiskusikan hutan rentang minimum, generalisasi untuk grafik terputus pohon rentang minimum. Definisi lain, umum dalam teori graph , adalah bahwa hutan membentang adalah setiap subgraf yang baik hutan (tidak mengandung siklus) dan mencakup (termasuk setiap vertex).
Menghitung pohon rentang
Jumlah t (G) dari pohon rentang dari graf terhubung adalah penting invarian . Dalam beberapa kasus, mudah untuk menghitung t (G) secara langsung. Hal ini juga banyak digunakan dalam struktur data di bahasa komputer yang berbeda. [ rujukan? ] Sebagai contoh, jika G itu sendiri pohon, maka t (G) = 1 , sedangkan jika G adalah graph siklus C n dengan n simpul, maka t (G) = n . Untuk setiap graf G, nomor t (G) dapat dihitung dengan menggunakan pohon teorema's matriks-Kirchhoff (ikuti link untuk contoh eksplisit menggunakan teorema itu).
Cayley's formula ini adalah formula untuk jumlah mencakup pohon di graf lengkap K n dengan n simpul. Menyatakan formula yang t ( K n ) = n n - 2 . Cara lain untuk menyatakan's formula Cayley adalah bahwa ada persis n n - 2 pohon berlabel dengan n simpul. Cayley's formula dapat dibuktikan dengan menggunakan teorema's matriks pohon-Kirchhoff atau melalui kode Prüfer .
Jika G adalah graf bipartit lengkap K p , q , maka t ( G ) = p q - 1 q p - 1 , sedangkan jika G adalah n -dimensi hypercube grafik Q n , maka . rumus Ini juga konsekuensi dari teorema matriks-pohon.
Jika G adalah multigraph dan e adalah tepi G , maka jumlah t (G) dari pohon rentang G memenuhi penghapusan-kontraksi kambuh t (G) = t (Ge) + t (G / e) , dimana Ge adalah multigraph diperoleh dengan menghapus e dan G / e merupakan kontraksi dari G oleh e , di mana beberapa tepi yang timbul dari kontraksi ini tidak dihapus.


KELEBIHAN SPANNING TREE.
Dapat menyediakan system jalur backup & juga mencegah loop yang tidak diinginkan pada jaringan yang memiliki beberapa jalur menuju ke satu tujuan dari satu host.
Loop terjadi bila ada route/jalur alternative di antara host-host. Untuk menyiapkan jalur back up, Spanning tree membuat status jalur back up menjadi stand by atau diblock. Spanning tree hanya membolehkan satu jalur yang active (fungsi pencegahan loop) di antara dua host namun menyiapkan jalur back up bila jalur utama terputus.
Bila "cost" spanning tree berubah atau ada jalur yang terputus, algoritma spanning tree mengubah topology spanning tree dan mengaktifkan jalur yang sebelumnya stand by.
Tanpa spanning tree pun sebenarnya memungkinkan koneksi antara dua host melewati beberapa jalur sekaligus namun dapat juga membuat looping yang tidak pernah akan selesai di dalam jaringan anda. Yang pasti akan menghabiskan kapasitas jalur yang ada hanya untuk melewatkan packet data yang sama secara berulang dan berlipat ganda.