Czy minimalne drzewa opinające wykresu ważonego mają taką samą liczbę krawędzi o danej masie?

Jeśli wykres ważony ma dwa różne minimalne drzewa i , to prawda, że dla dowolnej krawędzi w liczba krawędzi w ma taką samą wagę jak (w tym sam ) jest taki sam jak liczba krawędzi w o tej samej wadze co ? Jeśli stwierdzenie jest prawdziwe, to jak możemy to udowodnić? $G$ $T_1 = (V_1, E_1)$ $T_2 = (V_2, E_2)$ $e$ $E_1$ $E_1$ $e$ $e$ $E_2$ $e$

graph-theory spanning-trees weighted-graphs Aden Dong
źródło

Jednym trudnym, ale wykonalnym podejściem jest pokazanie 1) Algorytm Kruskala może wygenerować każde minimalne drzewo rozpinające i 2) wszystkie minimalne drzewa rozpinające znalezione przez Kruskal mają ten sam multiset o krawędzi.

Raphael

Odpowiedzi:

Twierdzenie: Tak, to stwierdzenie jest prawdziwe.

Szkic : Niech będą dwoma minimalnymi drzewami łączącymi z krawędziami . Załóżmy i ich różnicę symetryczną za pomocą . $T_1,T_2$ $W_1,W_2$ $W_1 \neq W_2$ $W = W_1 \mathop{\Delta} W_2$

Wybierz krawędź pomocą , to znaczy jest krawędzią występującą tylko w jednym z drzew i ma minimalną niezgodną wagę. Taka krawędź, która jest w szczególności zawsze istnieje: Oczywiście, nie wszystkie krawędzie masy może być zarówno drzew inaczej . Wlog wpuszcza i zakłada, że ma więcej krawędzi masy niż . $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$ $e \in T_1$ $T_1$ $\min W$ $T_2$

Teraz rozważ wszystkie krawędzie w , które również znajdują się w przekroju który jest indukowany przez w . Jeśli jest tam krawędź która ma taką samą wagę jak , zaktualizuj , używając zamiast ; zwróć uwagę, że nowe drzewo jest nadal minimalnym drzewem opinającym z takim samym multisetem krawędziowym jak . Powtarzamy ten argument, zmniejszając o dwa elementy, a tym samym usuwając jedną krawędź ze zbioru kandydatów na na każdym etapie. Dlatego po skończonych krokach dochodzimy do ustawienia, w którym wszystkie krawędzie w $T_2$ $C_{T_1}(e)$ $e$ $T_1$ $e'$ $e$ $T_1$ $e'$ $e$ $T_1$ $W$ $e$ $T_2 \cap C_{T_1}(e)$ (gdzie jest zaktualizowaną wersją) mają inne wagi niż . $T_1$ $w(e)$

Teraz zawsze możemy wybrać , abyśmy mogli zamienić i ¹, tzn. Możemy stworzyć nowe drzewo opinające $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}$

który ma mniejszą wagę niż i ; jest to sprzeczne z wyborem jako minimalnego drzewa rozpinającego. Dlatego . $T_1$ $T_2$ $T_1,T_2$ $W_1 = W_2$

Węzeł incydentu jest w połączony ścieżką ; jest unikalną krawędzią w . $e$ $T_2$ $P$ $e'$ $P \cap C_{T_1}(e)$

Raphael
źródło

Odnosząc się do komentarza Dave'a , wymyśliłem ten dowód po 0), wierząc, że mam kontrprzykład, który, jak zauważyłem, był zły po TikZingu, 1) próbowałem udowodnić stwierdzenie, ale nie, 2) próbowałem zbudować kontrprzykład na podstawie tego, gdzie dowód się nie powiódł, a potem ponownie, a na koniec 3) wykorzystując sposób, w jaki te nowe przykłady nie zadziałały w celu przedstawienia dowodu. Prawdopodobnie dlatego też nie jest tak wyrafinowany, jak mógłby być.

Raphael

tak, dokładnie nie rozumiem, co rozumie się przez cyt wywołany przez w Widziałem tylko cięcie takie jak cięcie

e

$e$

T_{1}

$T_1$

(S, V - S)

$(S,V-S)$

dragoboy

@dragoboy Usuwanie rozłącza ; jeden składnik tworzy , drugi uzupełnienie.

e

$e$

T_{1}

$T_1$

S

$S$

Raphael

Oto nieco prostszy argument, który działa również w przypadku innych matroidów. (Widziałem to pytanie z innego ).

Załóżmy, że ma krawędzi. Bez utraty ogólności, załóżmy, że funkcja wagi przyjmuje wartości w , więc mamy podział na zbiory dla . Można zrobić indukcję ponumerować o niepusty oraz liczba wierzchołków w ; dla i dowolnego wyrażenie jest oczywiste. $G$ $m$ $w$ $[m]$ $E$ $E_i := w^{-1}(i)$ $i\in [m]$ $j$ $E_i$ $n$ $G$ $j=1$ $n$

Standardowa fakt o matroids jest to, że za każdym MST istnieje liniowa przedłużenie wywołanego przez zamawiającego taki sposób, że algorytm zachłanny produkuje . $T$ $w$ $T$

Aby zamknąć indukcję, weź jako największą liczbę, aby nie był pusty. Ustaw . Zauważ, że każde liniowe przedłużenie stawia każdą krawędź w przed jakąkolwiek krawędzią w . Zgodnie z tym, każdy MST składa się z rozciągającego się lasu podsgrafu indukowanego przez i niektórych krawędzi z . Zgodnie z hipotezą indukcyjną każdy połączony składnik ma taką samą liczbę krawędzi od każdego dla . Ponieważ wszystkie wybory $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$ $F$ mają ten sam rozmiar, liczba krawędzi od wymaganych do uzupełnienia do drzewa opinającego jest niezależna od wyboru i gotowe. $E_t$ $F$ $F$

Louis
źródło

Czy możesz podać matroidowi problem MST? Wydaje mi się, że pamiętam, że trudno jest wymyślić coś takiego i jeszcze nie muszę tego robić (rygorystycznie). Tak, używamy chciwych algorytmów, lecz nie (kanoniczne) chciwych od teorii matroid.

Raphael

To powiedziawszy, myślę, że twój główny argument działa (i wcale nie potrzebuje matroidów): przez poprawność algorytmu Kruskala i fakt, że każdy MST można uzyskać z serii Kruskala z określoną (posortowaną) permutacją multisetu wagi ( rygorystyczny dowód w toku), roszczenie jest następujące. Piszę „dowód w toku”, ponieważ nie jest to ani trywialne, ani natychmiastowe: bez użycia samego roszczenia wcale nie jest jasne, dlaczego Kruskal powinien znaleźć wszystkie MST. Oczywiście, gdyby ktoś miał inny zestaw wagowy, Kruskal nigdy by go nie znalazł!

Raphael

1. Matroid to matroid graficzny. Gotowy!

Louis,

2. Jesteś zdezorientowany. W sposób abstrakcyjny wykonujemy optymalizację liniową w stosunku do bazowego polytopa. Jedną ze standardowych cech matroidów jest to, że chciwy algorytm działa dla każdego wyboru wag. Wszystkie -minimal Spanning drzewa są wierzchołkami obliczu tego Polytope. Teraz standardowe pomysły z LP prowadzą do standardowego faktu, o którym wspomniałem.

w

$w$

Louis,

1. Czy możesz podać referencje? Nie wiem, z graficzną matroid. 2. Teraz przeciągasz do niego także LP! Mówię tylko, że w twojej odpowiedzi nie ma matroidu i że bez matroida linia rozumowania wydaje się polegać na samym twierdzeniu. Jeśli masz na to sposób, edytuj / wyjaśnij odpowiedź.

Raphael