szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 lut 2016, o 20:02 
Użytkownik

Posty: 101
Lokalizacja: Wro
pokaż że dowolny graf G zawierający conajmniej jedną krawędź posiada podgraf H taki że \partial \left( H\right)   \ge   \frac{1}{2}d\left( H\right)  \ge  \frac{1}{2}d\left( G\right) gdzie \partial (G) to minimalny stopien wierzchołka w G a d\left( G\right) to średni stopień wierzchołka w G
Góra
Mężczyzna Offline
PostNapisane: 5 lip 2017, o 03:24 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Wykonujemy w pętli następujący algorytm:
1. Jeżeli każdy wierzchołek ma w G stopień nie mniejszy niż \frac{1}{2}d\left( G\right), to H := G i koniec algorytmu.
Jeżeli nie, to weźmy taki wierzchołek u \in V(G), że deg(u) < \frac{1}{2}d\left( G\right).
2. G' := G  \setminus  {u} (usuwamy wierzchołek u z G)
3. G := G'

Pokażemy, niezmiennik d(\left G' \right)   \ge d\left( G\right):
deg(u) <  \frac{d}{2}, więc po usunięciu u suma stopni zmniejszy się o 2 deg(u). Niech
S = \sum_{v \in V(G)}^{}deg(v)
\frac{S}{|V(G)|} = d(G), czyli S = d(G)  \cdot  |V(G)|.
d(G') = \frac{\sum_{v \in V(G')}deg(v)}{|V(G')|}  =  \frac{S - 2deg(u)}{|V(G)| - 1}   \ge  \frac{S - d(G)}{|V(G)| - 1} =  \frac{d(G)  \cdot  |V(G)| - d(G)}{|V(G)| - 1} = d(G)
Tak więc w każdym kroku algorytmu zachowany jest niezmiennik d\left( G'\right) \ge d\left( G\right).

Jest jasne, że po zakończeniu algorytmu wszystkie wierzchołki grafu H będą miały stopień nie mniejszy niż \frac{1}{2}d\left( H\right), czyli \partial \left( H\right)  \ge \frac{1}{2}d\left( H\right). Z powyższego niezmiennika wynika druga nierówność: \frac{1}{2}d\left( H\right) \ge \frac{1}{2}d\left( G\right).
Teraz wystarczy jeszcze pokazać, że algorytm nie usunie wszystkich wierzchołków z grafu. Dowód nie wprost. To znaczy, że algorytm musiał w ostatnim kroku usunąć ostatni wierzchołek z grafu, w tym momencie średni stopień byłby równy 0, ale na początku d\left( G\right) > 0, bo E(G) > 0 oraz w każdym kroku zachowany jest niezmiennik \frac{1}{2}d\left( G'\right) \ge \frac{1}{2}d\left( G\right) > 0, sprzeczność, cnd.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 nierownosc z 5 zmiennymi - ile rozwiazan w l. naturalnych?  Anonymous  25
 Cykle i przekroje w grafie  jpxx  0
 Nierówność z silnią  Zasados  2
 Najkrótsza droga w grafie  wojciech007  1
 Wariancja i pewna nierówność  sszbig  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl