Kondisi yang diperlukan dan memadai untuk pohon spanning minimum yang unik

Ini adalah masalah latihan (Kel.3) dari catatan kuliah yang sangat baik oleh Jeff Erickson Kuliah 20: Pohon-pohon Spanning Minimum [Fa'13] .

Buktikan bahwa grafik edge-weighted $G$ memiliki pohon rentang minimum yang unik jika dan hanya jika kondisi berikut ini berlaku

Untuk setiap partisi simpul $G$ menjadi dua himpunan bagian, tepi bobot minimum dengan satu titik akhir di setiap subset adalah unik.

Batas berat maksimum dalam setiap siklus adalah unik. $G$

Pertimbangkan " $\Rightarrow$ "Arah dan grafik berikut $G$ .

mst

$G$ memiliki MST yang unik. Namun, untuk partisi $\{A\}$ dan $\{B,C\}$ , batas persimpangan minimum-berat tidak unik.

Apakah saya salah paham beberapa poin? Atau jika ada kekurangan dalam teorema, bagaimana kita dapat memperbaikinya?

graph-theory spanning-trees Hengxin
sumber

Ya, ini sepertinya sebuah kesalahan. Cobalah mencari tahu versi latihan apa yang benar. Misalnya, tampaknya syarat kedua memang perlu.

Yuval Filmus

Kecuali saya salah paham, kondisi kedua juga tidak perlu. Pertimbangkan grafik {(A, B, 1), (A, C, 1), (A, D, 1), (B, D, 10), (D, C, 10)}. Ini juga memiliki pohon spanning minimum yang terdiri dari tepi yang terhubung ke A. Tapi ada siklus dengan 2 tepi berat maksimum (dan kondisi pertama tidak terpenuhi juga). CC @YuvalFilmus

babou

@ Jeff, bagaimana menurutmu? ;)

Luke Mathieson pada

Saya pikir yang kedua harus dalam "dalam siklus chordless " (jadi siklus minimal dalam arti bahwa itu tidak termasuk yang lebih kecil sebagai subgraph yang diinduksi). Kondisi pertama tampaknya sangat salah. Misalnya ambil

G

$G$ menjadi pohon apa pun di mana semua bobot tepi berada

1

$1$ , kemudian

G

$G$ memiliki MST unik (sendiri), tetapi setiap partisi dengan lebih dari satu sisi yang menyilang memiliki beberapa sisi berat minimum.

Luke Mathieson pada

Ups! Ya, ini adalah bug. (Catatan untuk diri sendiri: Ubah setiap instance dari "Buktikan" menjadi "Buktikan atau

bantah

Kondisi yang diperlukan dan memadai untuk pohon spanning minimum yang unik

Jawaban: