Kapan pohon rentang minimum untuk grafik tidak unik

Diberikan grafik berbobot dan tidak terarah G: Kondisi mana yang harus benar sehingga ada beberapa pohon rentang minimum untuk G?

Saya tahu bahwa MST itu unik ketika semua bobotnya berbeda, tetapi Anda tidak bisa membalikkan pernyataan ini. Jika ada tepi muliple dengan bobot yang sama dalam grafik, mungkin ada beberapa MST tetapi mungkin juga hanya ada satu:

Dalam contoh ini, grafik di sebelah kiri memiliki MST yang unik tetapi yang kanan tidak.

Yang paling dekat yang bisa saya temukan untuk menemukan kondisi untuk keunikan MST adalah sebagai berikut:

Pertimbangkan semua siklus tanpa tali (siklus yang tidak mengandung siklus lain) dalam grafik G. Jika dalam salah satu siklus ini, tepi tertimbang maksimum ada beberapa kali, maka grafik tidak memiliki pohon rentang minimum yang unik.

Ide saya adalah untuk siklus seperti ini

dengan n simpul, Anda dapat meninggalkan persis salah satu ujung dan masih memiliki semua simpul yang terhubung. Oleh karena itu, Anda memiliki banyak pilihan untuk menghilangkan ujung dengan bobot tertinggi untuk mendapatkan MST, sehingga MST tidak unik.

Namun, saya kemudian datang dengan contoh ini:

Anda dapat melihat bahwa grafik ini memang memiliki siklus yang sesuai dengan kondisi saya: (E, F, G, H) tetapi sejauh yang saya lihat, pohon rentang minimum adalah unik:

Jadi sepertinya kondisi saya tidak benar (atau mungkin tidak sepenuhnya benar). Saya sangat menghargai bantuan apa pun dalam menemukan kondisi yang diperlukan dan cukup untuk ketidakunikan pohon spanning minimum.

pada gambar pertama: grafik kanan memiliki MST yang unik, dengan mengambil sisi dan dengan berat total 2.( F , G $(F,H)$$(F,G)$

Mengingat grafik dan biarkan menjadi minimum spanning tree (MST) di .M = ( V , F ) $G=(V,E)$$M=(V,F)$$G$

Jika ada tepi dengan bobot sehingga menambahkan ke MST kami menghasilkan siklus , dan biarkan juga menjadi tepi-bobot terendah. dari , maka kita dapat membuat MST kedua dengan menukar tepi dari dengan bobot tepi dengan . Dengan demikian kita tidak memiliki keunikan.w ( e ) = m e C m F ∩ C F ∩ C m $e=\{v,w\}\in E \setminus F$$w(e)=m$$e$$C$$m$$F\cap C$$F\cap C$$m$$e$

Jawaban sebelumnya menunjukkan algoritma untuk menentukan apakah ada beberapa MST, yang, untuk setiap sisi tidak dalam G , menemukan siklus yang dibuat dengan menambahkan e ke MST yang dikomputasi dan memeriksa apakah e bukan tepi terberat unik dalam siklus itu. Algoritma itu kemungkinan akan berjalan dalam waktu O ( | E | | V | ) .$e$$G$$e$$e$$O(|E||V|)$

Algoritma yang lebih sederhana untuk menentukan apakah ada beberapa MST G- kompleksitas waktu$O(|E|\log(|V|))$ .

$\ $1. Jalankan algoritma Kruskal pada untuk menemukan MST m .$G$$m$

$\ $2. Coba jalankan algoritma Kruskal di lagi. Dalam menjalankan ini, setiap kali kita memiliki pilihan di antara tepi bobot yang sama, pertama-tama kita akan mencoba tepi yang tidak dalam m , setelah itu kita akan mencoba tepi di m . Setiap kali kami menemukan tepi yang tidak dalam m menghubungkan dua pohon yang berbeda, kami mengklaim bahwa ada beberapa MST, yang mengakhiri algoritme.$G$$m$$m$$m$

$\ $3. Jika kami telah sampai di sini, maka kami mengklaim bahwa memiliki MST yang unik.$G$

Proses algoritma Kruskal yang biasa membutuhkan waktu . Pilihan tambahan tepi yang tidak dalam m dapat dilakukan dalam waktu O ( | E | ) . Jadi algoritma ini mencapai kompleksitas waktu O ( | E | log ( | V | ) ) .$O(|E|\log(|V|))$$m$$O(|E|)$$O(|E|\log(|V|))$

Mengapa algoritma ini dapat menentukan apakah ada beberapa MST?

Misalkan kita memiliki MST yang tidak sama dengan m . Cukup untuk menunjukkan bahwa algoritma yang berjalan pada G tidak akan mencapai langkah 3, karena tepi ditemukan pada akhir langkah 2, yang tidak dalam m dan menghubungkan dua pohon yang berbeda akan dimasukkan dalam MST yang dihasilkan seandainya kami menjalankan Kruskal's algoritma untuk penyelesaian. Misalkan w menjadi bobot terbesar sedemikian rupa sehingga untuk setiap tepi yang beratnya kurang dari w , ia berada di m jika dan hanya jika berada di m ′ . Karena m dan m ′ memiliki jumlah sisi berat yang sama dengan w , maka terdapat tepi sisi berat$m'$$m$$G$$m$$w$$w$$m$$m'$$m$$m'$$w$ yang ada di m ′ tetapi tidak di m . Jika algoritme telah keluar sebelum memproses tepi dari tepi tersebut, kami selesai. Kalau tidak, anggap algoritma akan memproses tepi pertama e ′ di antara tepi itu sekarang. Misalkan S adalah himpunan semua tepi yang telah dipertahankan sejauh ini untuk dimasukkan dalam MST yang dihasilkan. S ⊂ m . Karena algoritme belum selesai memproses tepi bobot w tidak dalam m seperti e ′ ,algoritmatersebut harus belum mulai memproses tepi bobot w dalam m . Jadi tepi di$w$$m'$$m$$e'$$S$$S\subset m$$w$$m$$e'$$w$$m$$S$beratnya kurang dari . Itu berarti S ⊂ m ′ . Ingatlah bahwa e ′ ada di m ′ . Karena { e ′ } ∪ S ⊂ m ′ , di mana m ′ adalah pohon, e ′ harus menghubungkan dua pohon yang berbeda dalam S dan algoritme keluar pada titik ini.$w$$S\subset m'.$$e'$$m'$$\{e'\}\cup S\subset m'$$m'$$e'$$S$

Catatan tentang pengembangan lebih lanjut
Langkah 1 dan langkah 2 dapat disisipkan sehingga kita dapat menghentikan algoritme sesegera mungkin tanpa memproses tepi bobot yang lebih besar.
Jika Anda ingin menghitung jumlah MST, Anda dapat memeriksa jawaban tentang cara menghitung jumlah MST .

Biarkan menjadi grafik terhubung tanpa batas (berhingga sederhana) berbobot tidak berarah dengan setidaknya dua simpul. Biarkan ST berarti spanning tree dan MST berarti spanning tree minimum. Biarkan saya mendefinisikan beberapa istilah yang kurang umum dulu.$G$

• Tepi adalah siklus-terberat unik jika merupakan tepi terberat unik dalam beberapa siklus.
• Edge adalah non-cycle-terberat jika itu tidak pernah menjadi edge terberat dalam siklus apa pun.
• Sebuah tepi adalah unik-potong-paling ringan jika itu adalah tepi paling ringan unik untuk memotong beberapa.
• Tepi adalah non-cut-lightest jika itu tidak pernah menjadi tepi yang paling ringan untuk memotong apapun.
• Dua STs bersebelahan jika setiap ST memiliki tepat satu sisi yang tidak di ST lainnya.
• MST adalah MST yang terisolasi jika tidak berdekatan dengan MST lain (ketika kedua MST dianggap sebagai ST).

Kapan ada lebih dari satu pohon spanning minimum?

$G$

• Ada dua MST yang berdekatan.
• Tidak ada MST yang terisolasi.
• Ada ST yang seringan atau lebih ringan dari semua ST yang berdekatan dan yang seringan satu ST yang berdekatan.
• Ada keunggulan yang bukan merupakan siklus terberat maupun non-siklus terunik.
• Ada sisi yang tidak unik-potong-ringan atau non-potong-ringan

Kebaruan dari jawaban ini sebagian besar adalah dua penokohan terakhir. Yang kedua dari karakterisasi terakhir dapat dianggap sebagai langkah selanjutnya dari pendekatan OP . Tiga penokohan pertama bersama-sama dapat dianggap sebagai versi sedikit lebih baik dari jawaban dtt .

$G$

Kapan pohon spanning minimum unik?

$G$

• Keunikan MST : Ada MST yang unik.
• Tidak ada MST yang berdekatan : tidak ada MST yang berdekatan.
• Satu MST yang terisolasi : ada MST yang terisolasi.
• Satu minimum ST lokal : ada ST yang lebih ringan dari semua ST yang berdekatan.
• Extreme cycle edge : setiap edge adalah unik-siklus-terberat atau non-siklus-terberat.
• Extreme cut edge : setiap tepi unik-potong-ringan-atau non-potong-ringan

Inilah buktiku.

"Keunikan MST" => "Tidak ada MST yang berdekatan": jelas.

"Tidak ada MST yang berdekatan" => "Satu MST yang terisolasi": jelas.

"Satu MST yang terisolasi" => "Satu ST minimum lokal": MST yang terisolasi lebih ringan daripada semua ST yang berdekatan.

$m$

• $m$$l$$m$$l$$l$$c$$l$$m$$m$$m_1$$m_2$$m_1$$m_2$$l$$c$$m_1$$m_2$$l'$$m'$$m_1$$m_2$$l'$$G$$m$$m'$$m$$m'$$l$$l'$$l$
• $m$$h'$$m$$h'$$m$$c$$h$$c$$h'$$m'$$m$$h$$h'$$m$$m'$$m$$m'$$h$$h'$$h'$$c$$h'$

"ST minimum lokal" => "Extreme cut edge": Bukti dibiarkan sebagai latihan.

$m$$e$$e$$m$$e$$m$$m$

"Extreme cut edge" => "Keunikan MST": Bukti dibiarkan sebagai latihan.

Rantai implikasi di atas membuktikan teorema tersebut.

Sekali lagi, kebaruan dari jawaban ini sebagian besar adalah properti "edge cycle edge" dan properti "edge cut edge", yang menggunakan konsep, non-cycle-terberat dan non-cut-lightest. Saya belum melihat konsep-konsep itu di tempat lain, walaupun mereka cukup alami.

Berikut adalah dua pengamatan menarik terkait.

• $e$$e$$\Leftrightarrow$ $e$$\Leftrightarrow$ $e$
• $e$$e$$\Leftrightarrow$ $e$$\Leftrightarrow$ $e$

Dua kondisi yang cukup tetapi tidak perlu untuk MST unik

$ab\rightarrow 1, bc\rightarrow 1, cd\rightarrow 1, da\rightarrow 2, ac\rightarrow 2$

$1,1,2$