Drzewa rozpinające w griafie

[Zordon]

Dane są dwa MST (min. d. rozpinające) grafu \(\displaystyle{ G}\): \(\displaystyle{ T_1, T_2}\). Udowodnić, że jeśli \(\displaystyle{ (a_1,a_2,...,a_n)}\), \(\displaystyle{ (b_1,b_2,...,b_n)}\) to (posortowane) ciągi długości krawędzi odpowiednio \(\displaystyle{ T_1, T_2}\) to \(\displaystyle{ (a_1,a_2,...,a_n)=(b_1,b_2,...,b_n)}\).

Nie jestem pewien czy to twierdzenie jest prawdziwe, ale wszystko wskazuje na to, że tak

[Inkwizytor]

Co dokładnie oznacza w tej notacji równość na końcu? Identyczny skład jakościowy krawędzi?

[Zordon]

równość ciągów (można też myśleć o równości multizbiorów, bo długosci mogą sie powtarzać).

[Inkwizytor]

Obserwacja i wniosek "na szybko"

1) W zasadzie wystarczy rozpatrzeć podgraf H grafu G tylko tych wierzchołków które mają stopień \(\displaystyle{ \ge 2}\) dlatego że każdy wierzchołek stopnia 1 jest koincydentny z jedną krawędzią stąd ZAWSZE ta krawędź należy do min. drzewa rozpinającego, stąd jej waga pojawi się w każdym ciągu wag krawędzi.

2) Zatem szukamy min. drzewa rozpinającego podgrafu H o stopniach wierzchołków minimum 2.

[Dumel]

niech \(\displaystyle{ m}\) będzie najmniejszą wagą krawędzi w grafie G.
weźmy dowolną krawędź (u,v) o wadze m i T - dowolne MST.
jeśli krawędź (u,v) nie należy do T to dodając ją tworzymy cykl, a ponieważ T jest minimalne więc wszystkie krawędzie tego cyklu mają wagę m, więc możemy przekształcić T do nowego MST - T' zawierającego (u,v) nie naruszając przy tym liczebności krawędzi o wadze m.
teraz zgniatając nasz graf wzdłuż krawędzi (u,v) mamy nowy graf G', w którym z założenia indukcyjnego (powiedzmy że indukujemy po liczbie wierzchołków) ten ciąg jest jednoznacznie wyznaczony, więc jest jednoznacznie wyznaczony w grafie pierwotnym.
wykorzystałem łatwy do wykazania fakcik że dowolne MST grafu G' jest po rozsunięciu krawędzi (u,v) MST grafu G i na odwrót- dowolne MST grafu G zawierające (u,v) po zgnieceniu jest MST grafu G'