Dalam bidang matematika dari teori graph, T pohon rentang dari, terhubung graf tak berarah G adalah pohon terdiri dari semua simpul dan beberapa (atau mungkin semua) dari tepi G. informal, pohon rentang dari G adalah pilihan tepi dari G yang membentuk pohon rentang setiap simpul. Artinya, setiap vertex terletak di pohon, tetapi tidak ada siklus (atau loop) terbentuk. Di sisi lain, setiap jembatan 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 grafik tertimbang. Masalah optimasi lain di pohon mencakup juga telah dipelajari, termasuk pohon maksimum merentang, 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), diameter pohon rentang minimum, dan dilatasi minimum spanning tree.
Fundamental siklus
Menambahkan hanya satu tepi ke pohon rentang akan menciptakan sebuah siklus, seperti siklus yang disebut siklus mendasar. Ada siklus mendasar berbeda untuk setiap sisinya, dengan demikian, ada korespondensi satu-ke-satu di antara siklus fundamental dan pinggiran tidak di pohon rentang. Untuk graf terhubung dengan simpul V, setiap pohon rentang akan memiliki V-1 tepi, dan dengan demikian, grafik tepi E akan memiliki E-V +1 siklus mendasar. Untuk setiap pohon rentang diberikan siklus ini membentuk dasar untuk ruang siklus.
Dual dengan gagasan dari siklus mendasar adalah gagasan tentang cutset mendasar. Dengan menghapus hanya pada satu sisi dari pohon rentang, simpul yang dibagi menjadi dua set beririsan. The cutset mendasar adalah didefinisikan sebagai set dari ujung yang harus dihapus dari grafik G untuk mencapai partisi yang sama. Dengan demikian, ada tepat V-1 cutsets mendasar bagi grafik, satu untuk setiap tepi spanning tree.
Dualitas antara cutsets fundamental dan siklus mendasar dibentuk dengan mencatat bahwa siklus tepi tidak di pohon rentang hanya dapat muncul dalam cutsets dari sisi lain dalam siklus, dan sebaliknya: pinggiran cutset hanya dapat muncul dalam siklus tersebut berisi tepi sesuai dengan cutset tersebut.
Spanning forests
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 terkoneksi dari grafik. (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 bersifat hutan (tidak mengandung siklus) dan mencakup (termasuk setiap vertex).
Counting spanning trees
T nomor (G) dari pohon rentang dari graf terhubung merupakan invarian penting. 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 adalah pohon itu sendiri, maka t (G) = 1, sedangkan jika G adalah graf siklus Cn dengan n simpul, maka t (G) = n. Untuk setiap graf G, t nomor (G) dapat dihitung dengan menggunakan teorema matriks-pohon Kirchhoff (ikuti link untuk contoh eksplisit menggunakan teorema itu).
Cayley formula adalah rumus untuk jumlah mencakup pohon di Kn graf lengkap dengan n simpul. Menyatakan formula yang t nn (Kn) = - 2. Cara lain untuk menyatakan formula Cayley adalah bahwa ada tepat nn - 2 pohon berlabel dengan n simpul. Rumus Cayley bisa dibuktikan dengan menggunakan teorema matriks-pohon Kirchhoff atau melalui kode Prüfer.
Jika G adalah graf bipartit komplit Kp, q, kemudian t (G) = pq - 1qp - 1, sedangkan jika G adalah graf hypercube n-dimensi Qn, maka t (G) = 2 ^ {2 ^ nn-1} \ prod_ {k = 2} ^ ^ {nk {n \ memilih k}}. Rumus Ini juga konsekuensi dari teorema matriks-pohon.
Jika G adalah multigraph dan e adalah tepi G, maka t nomor (G) dari pohon rentang dari G memenuhi t penghapusan-kontraksi kambuh (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.
Uniform spanning trees
Sebuah pohon rentang dipilih secara acak dari antara semua pohon merentang dengan probabilitas yang sama disebut pohon seragam rentang (UST). Model ini telah banyak diteliti dalam probabilitas dan fisika matematika.
Algorithms
Yang mencakup klasik pohon algoritma, depth-first search (DFS), adalah karena Robert Tarjan. Algoritma lain yang penting adalah didasarkan pada pencarian breadth-first (BFS).
Algoritma paralel biasanya mengambil pendekatan yang berbeda dari BFS atau DFS. Halperin dan Zwick dirancang suatu algoritma paralel yang optimal secara acak yang berjalan dalam O (log n) waktu dengan probabilitas tinggi pada EREW PRAM [1] Algoritma Shiloach-Vishkin, karena Yossi Shiloach dan Uzi Vishkin, adalah. dasar untuk implementasi paralel banyak. [2] Bader dan algoritma Cong ini yang ditampilkan untuk berlari cepat dalam praktek pada berbagai grafik. [3]
Algoritma terdistribusi yang paling umum adalah Spanning Tree Protocol, yang digunakan oleh perangkat link layer OSI untuk membuat pohon rentang menggunakan link yang ada sebagai sumber grafik untuk menghindari badai siaran.
Minimum spanning tree
Mengingat grafik, terhubung tak berarah, pohon rentang dari graf yang merupakan subgraf yang pohon dan menghubungkan semua simpul bersama-sama. Sebuah grafik tunggal dapat memiliki banyak pohon rentang yang berbeda. Kita juga dapat menetapkan berat untuk setiap sisi, yang merupakan angka yang mewakili bagaimana tidak menguntungkan itu, dan menggunakan ini untuk menetapkan berat untuk pohon rentang dengan menghitung jumlah dari bobot dari tepi dalam pohon rentang. Pohon rentang minimum (MST) atau pohon bobot minimum spanning kemudian pohon rentang dengan berat kurang dari atau sama dengan berat setiap pohon rentang lainnya. Secara umum, setiap grafik tak berarah (tidak harus terhubung) memiliki hutan rentang minimum, yang merupakan gabungan dari pohon rentang minimum untuk komponen tersambung nya.
Salah satu contoh akan menjadi perusahaan TV kabel peletakan kabel ke lingkungan baru. Jika dibatasi untuk mengubur kabel hanya di sepanjang jalan tertentu, maka akan ada grafik yang mewakili dimana poin dihubungkan oleh jalan tersebut. Beberapa dari mereka jalan mungkin lebih mahal, karena mereka lebih panjang, atau membutuhkan kabel yang akan dikubur lebih dalam, jalur ini akan diwakili oleh tepi dengan bobot yang lebih besar. Sebuah pohon rentang untuk grafik yang akan menjadi bagian dari orang-orang jalan yang tidak memiliki siklus tapi masih terhubung ke setiap rumah. Mungkin ada beberapa pohon merentang mungkin. Pohon rentang minimum akan menjadi satu dengan total biaya terendah.
sumber : http://en.wikipedia.org/wiki/Spanning_tree
Tidak ada komentar:
Posting Komentar