Apakah pohon rentang minimum dari grafik berbobot memiliki jumlah sisi yang sama dengan bobot yang diberikan?

Jika grafik berbobot memiliki dua pohon rentang minimum yang berbeda dan , maka apakah benar bahwa untuk setiap tepi dalam , jumlah tepi dalam dengan jumlah tepi pada dengan bobot yang sama dengan (termasuk sendiri) sama dengan jumlah tepi dalam dengan bobot yang sama dengan ? Jika pernyataan itu benar, lalu bagaimana kita bisa membuktikannya?$G$T 2 = ( V 2 , E 2 ) e E 1 E 1 e e E 2$T_1 = (V_1, E_1)$$T_2 = (V_2, E_2)$$e$$E_1$$E_1$$e$$e$$E_2$$e$

Klaim: Ya, pernyataan itu benar.

Sketsa Bukti: Misalkan menjadi dua pohon rentang minimum dengan multiset tepi-berat . Asumsikan dan tunjukkan perbedaan simetrisnya dengan .$T_1,T_2$$W_1,W_2$$W_1 \neq W_2$ W = W 1 Δ W 2$W = W_1 \mathop{\Delta} W_2$

Pilih tepi dengan , yaitu e adalah tepi yang hanya terjadi di salah satu pohon dan memiliki bobot minimum yang tidak disetujui. Keunggulan seperti itu, khususnya e \ di T_1 \ mathop {\ Delta} T_2 , selalu ada: jelas, tidak semua tepi bobot \ min W dapat berada di kedua pohon, jika tidak$e \in T_1 \mathop{\Delta} T_2$$w(e) = \min W$$e$$e \in T_1 \mathop{\Delta} T_2$$\min W$$\min W \notin W$ . Wlog, biarkan$e \in T_1$ dan anggap$T_1$ memiliki lebih banyak tepi bobot$\min W$ daripada$T_2$ .

Sekarang perhatikan semua tepi di $T_2$ yang juga ada di cut $C_{T_1}(e)$ yang diinduksi oleh $e$ di $T_1$ . Jika ada tepi $e'$ di sana yang memiliki bobot sama dengan $e$ , perbarui $T_1$ dengan menggunakan $e'$ alih-alih ; perhatikan bahwa pohon baru masih merupakan pohon spanning minimal dengan multiset tepi-berat yang sama dengan . Kami mengulangi argumen ini, mengecilkan oleh dua elemen dan dengan demikian menghilangkan satu sisi dari set kandidat untuk dalam setiap langkah. Oleh karena itu, kami mendapatkan setelah banyak langkah ke pengaturan di mana semua tepi di$e$$T_1$$W$$e$$T_2 \cap C_{T_1}(e)$T 1 w ( e )(di mana adalah versi yang diperbarui) memiliki bobot selain .$T_1$$w(e)$

Sekarang kita selalu dapat memilih sehingga kita dapat menukar dan ¹, yaitu kita dapat membuat pohon spanning baru$e' \in C_{T_1}(e) \cap T_2$$e$$e'$

$\qquad \displaystyle T_3 = \begin{cases} (T_1 \setminus \{e\}) \cup \{e'\}, &w(e') \lt w(e) \\[.5em] (T_2 \setminus \{e'\}) \cup \{e\}, &w(e') \gt w(e) \end{cases}$

yang memiliki bobot lebih kecil dari dan$T_1$$T_2$ ; ini bertentangan dengan pilihan sebagai pohon spanning minimal. Karenanya, .$T_1,T_2$$W_1 = W_2$

1. Insiden node berada di terhubung oleh jalur ;$e$$T_2$$P$$e'$ adalah keunggulan unik dalam .$P \cap C_{T_1}(e)$

Berikut adalah argumen yang sedikit lebih sederhana yang juga berfungsi untuk matroid lainnya. (Saya melihat pertanyaan ini dari yang lain .)

Misalkan memiliki tepi . Tanpa kehilangan generalitas, asumsikan bahwa fungsi bobot mengambil nilai dalam , jadi kami memiliki partisi ke dalam set untuk . Kita dapat melakukan induksi pada jumlah dari kosong dan jumlah simpul dalam ; untuk dan apa sajam w [ m ] E E i : = w - 1 ( i ) i ∈ [ m ] j E i n G j = 1 $G$$m$$w$$[m]$$E$$E_i := w^{-1}(i)$$i\in [m]$$j$$E_i$$n$$G$$j=1$$n$ , pernyataannya jelas.

Fakta standar tentang matroid adalah bahwa untuk setiap MST ada ekstensi linear dari urutan yang disebabkan oleh sehingga algoritma serakah menghasilkanw $T$$w$$T$ .

Untuk menutup induksi, ambil menjadi angka terbesar sehingga tidak kosong. Set . Perhatikan bahwa setiap ekstensi linier dari menempatkan setiap sisi dalam sebelum sisi apa pun dalam . Menurut fakta, setiap MST terdiri dari hutan spanning dari subgraph yang diinduksi oleh dan beberapa tepi dari . Dengan hipotesis induktif, setiap komponen yang terhubung dari memiliki jumlah tepi yang sama dari setiap untukE t E ′ = E 1 ∪ ⋯ ∪ E t - 1 w E ′ E t F E ′ E t F E i i < t F E t F $t$$E_t$$E' = E_1 \cup \cdots \cup E_{t-1}$$w$$E'$$E_t$$F$$E'$$E_t$$F$$E_i$$i < t$ . Karena semua pilihan$F$memiliki ukuran yang sama, jumlah tepi dari diperlukan untuk menyelesaikan ke spanning tree tidak tergantung pada pilihan dan kita selesai.$E_t$$F$$F$