Minggu, 03 April 2011

Spanning Tree

SPANING TREE


Sebuah pohon rentang dari graf adalah himpunan bagian dari tepi yang membentuk sebuah pohon (Skiena 1990, hal 227). Misalnya, mencakup pohon dari grafik siklus , berlian grafik , dan grafik lengkap diilustrasikan di atas.
Jumlah pohon mencakup nonidentical dari grafik sama untuk setiap kofaktor dari matriks derajat dari dikurangi matriks adjacency dari (Skiena 1990, hal 235). Hasil ini dikenal sebagai teorema pohon matriks . Sebuah pohon berisi pohon rentang yang unik, sebuah grafik siklus mengandung mencakup pohon, dan sebuah grafik yang lengkap berisi mencakup pohon (Trent 1954; Skiena 1990, hal 236). Sebuah hitungan pohon rentang dari grafik dapat ditemukan dengan menggunakan perintah NumberOfSpanningTrees [ g ] pada Mathematica paketCombinatorica ` .

Contoh dari spaning tree antara lain:

Tutte polynomial
Adalah polinomial dalam dua variabel yang memainkan peran penting dalam teori graph , cabang dari matematika dan ilmu komputer teoritis . Ini didefinisikan untuk setiap graf tak berarah dan berisi informasi tentang bagaimana grafik tersambung.
Pentingnya Tutte polinomial T G berasal dari informasi yang berisi tentang G . Meskipun awalnya belajar di teori graph aljabar sebagai generalisasi dari menghitung masalah yang berkaitan dengan pewarnaan grafik dan tempat-nol aliran , terkenal mengandung beberapa spesialisasi dari ilmu-ilmu lain seperti polinomial Jones dari teori simpul dan fungsi partisi dari model Potts dari statistik fisika . Itu juga merupakan sumber dari beberapa pusat masalah komputasi dalam ilmu komputer teoritis .
Polinom Tutte memiliki beberapa definisi setara. Hal ini setara dengan Whitney polinomial pangkat , Tutte sendiri polinomial dwiwarna dan Fortuin-Kasteleyn's acak cluster model bawah transformasi sederhana. Ini pada dasarnya adalah sebuah fungsi pembangkit untuk jumlah set tepi ukuran yang diberikan dan komponen yang terhubung, dengan generalisasi segera matroids . Hal ini juga yang paling umum invarian grafikyang dapat didefinisikan oleh-kontraksi kambuh penghapusan.

Definisi dari Tutte polynomial.
Untuk graf tak berarah G = ( V , E ) orang dapat mendefinisikan polinomial Tutte sebagai

Di sini, c ( A ) menunjukkan jumlah komponen yang terhubung dari grafik ( V , A ) . Dalam definisi ini jelas bahwa T G baik-pasti dan polinomial dalam x dan y . Definisi yang sama dapat diberikan dengan menggunakan notasi berbeda sedikit dengan membiarkan r ( A ) = | V | - c ( A ) menunjukkan pada peringkat grafik ( V , A ) . Kemudian peringkat Whitney fungsi pembangkit didefinisikan sebagai

dua fungsi yang setara dengan perubahan sederhana variabel: T G ( x , y ) = R G ( x - 1, y - 1) . Tutte's dwiwarna polinomial Q G adalah hasil lain transformasi sederhana:
T G ( x , y ) = ( x - 1) - k ( G ) Q G ( x - 1, y - 1).
asli definisi's Tutte dari T G adalah setara tapi kurang mudah lain. Untuk tersambung G kita tentukan
T G ( x , y ) = Σ t i j x i y j ,
i , j
dimana t i j menunjukkan jumlah pohon rentang dari "aktivitas internal i dan kegiatan eksternal j . "
Definisi ketiga menggunakan-kontraksi kambuh penghapusan. Para tepi kontraksi G / u v dari graf G adalah graf yang diperoleh dengan menggabungkan simpul u dan v dan menghapus tepi u v .Kami menulis G - u v untuk grafik dimana tepi u v hanya dihapus. Kemudian polinomial Tutte didefinisikan oleh hubungan terulangnya
T G = T G - e + T G / e jika e bukan sebuah loop atau jembatan
dengan kasus dasar
T G ( x , y ) = x i y j jika G mengandung i jembatan dan j loop dan tidak ada sisi lainnya.
Terutama, T G = 1 jika G tidak berisi tepi.
Model cluster random dari mekanika statistik memberikan definisi lain setara. Polinom

setara dengan T G bawah transformasi
T G ( x , y ) = ( x - 1) - k ( E ) ( y - 1) - | V | Z G (( x - 1) ( y - 1), y - 1) .