Witam.
Daną mam krawędź grafu nieskierowanego \(\displaystyle{ G}\) która ma minimalną wagę \(\displaystyle{ e _{\min }}\). Muszę wykazać że każde minimalne drzewo rozpinające zawiera \(\displaystyle{ e _{\min }}\) . Jest to logiczne, przy Kruskalu krawędź ta zostanie wybrana jako piwerwsza, przy Primie będzie wybrana jako pierwsza przy rozpatrywaniu jej wierzchołka, tylko jak to formalnie zapisać?
[Algorytmy] Minimalne drzewo rozpinające i najtańsza krawędź
-
M Maciejewski
- Użytkownik
- Posty: 318
- Rejestracja: 14 maja 2016, o 16:25
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Pomógł: 90 razy
[Algorytmy] Minimalne drzewo rozpinające i najtańsza krawędź
Niech ta krawędź to \(\displaystyle{ ab}\) łącząca \(\displaystyle{ a}\) i \(\displaystyle{ b}\).
Niech \(\displaystyle{ w(a,b)=e_{\mathrm{min}}}\).
Jeśli istnieje więcej krawędzi o minimalnej wadze, teza twierdzenia jest nieprawdziwa. Zakładam więc, że chodzi tutaj o sytuację, w której graf ma jedyną krawędź o wadze \(\displaystyle{ e_{\mathrm{min}}}\).
Pomysł:
Rozważmy minimalne drzewo rozpinające \(\displaystyle{ T}\) i pokażemy, że \(\displaystyle{ ab\in T}\).
Załóżmy nie wprost, że \(\displaystyle{ ab\notin T}\).
Istnieje w \(\displaystyle{ T}\) ścieżka od \(\displaystyle{ a}\) do \(\displaystyle{ b}\), która nie idzie przez \(\displaystyle{ ab}\) (ponieważ ta krawędź nie jest w grafie). Oznaczmy tę ścieżkę tak: \(\displaystyle{ a,c_1,c_2,\ldots,c_k,b}\).
Zatem w szczególności \(\displaystyle{ ac_1\in T}\).
Rozważamy graf \(\displaystyle{ T'}\), który powstaje z \(\displaystyle{ T}\) przez usunięcie z \(\displaystyle{ T}\) krawędzi \(\displaystyle{ ac_1}\) i dodanie \(\displaystyle{ ab}\). Wtedy:
Niech \(\displaystyle{ w(a,b)=e_{\mathrm{min}}}\).
Jeśli istnieje więcej krawędzi o minimalnej wadze, teza twierdzenia jest nieprawdziwa. Zakładam więc, że chodzi tutaj o sytuację, w której graf ma jedyną krawędź o wadze \(\displaystyle{ e_{\mathrm{min}}}\).
Pomysł:
Rozważmy minimalne drzewo rozpinające \(\displaystyle{ T}\) i pokażemy, że \(\displaystyle{ ab\in T}\).
Załóżmy nie wprost, że \(\displaystyle{ ab\notin T}\).
Istnieje w \(\displaystyle{ T}\) ścieżka od \(\displaystyle{ a}\) do \(\displaystyle{ b}\), która nie idzie przez \(\displaystyle{ ab}\) (ponieważ ta krawędź nie jest w grafie). Oznaczmy tę ścieżkę tak: \(\displaystyle{ a,c_1,c_2,\ldots,c_k,b}\).
Zatem w szczególności \(\displaystyle{ ac_1\in T}\).
Rozważamy graf \(\displaystyle{ T'}\), który powstaje z \(\displaystyle{ T}\) przez usunięcie z \(\displaystyle{ T}\) krawędzi \(\displaystyle{ ac_1}\) i dodanie \(\displaystyle{ ab}\). Wtedy:
- \(\displaystyle{ w(T')<w(T)}\), bo \(\displaystyle{ w(a,b)<w(a,c_1)}\).
- \(\displaystyle{ T'}\) jest drzewem rozpinającym. Oczywiście \(\displaystyle{ T'}\) jest grafem rozpinającym (trzeba się chwilę zastanowić). Ponieważ ma tyle samo krawędzi, co \(\displaystyle{ T}\), czyli \(\displaystyle{ n-1}\), gdzie \(\displaystyle{ n}\) to liczba wierzchołków, to jest to drzewo.