Twierdzenie Gallai

Grupy, pierścienie, ciała, rozkładalność, klasyczne struktury algebraiczne...
paulina9612
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 31 sie 2009, o 09:11
Płeć: Kobieta

Twierdzenie Gallai

Post autor: paulina9612 » 29 sie 2011, o 16:58

Potrzebuję dowodu Twierdzenia Gallai dla grafów. Czyli: Dla dowolnego Grafu \(\displaystyle{ G=(V,E)}\) bez wierzchołków izolowanych mamy \(\displaystyle{ \alpha(G) + \tau(G) = |V|= \nu(G) +\rho(G)}\).
Ostatnio zmieniony 29 sie 2011, o 17:00 przez ares41, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznać się z instrukcją: http://matematyka.pl/latex.htm .

King James
Użytkownik
Użytkownik
Posty: 150
Rejestracja: 19 kwie 2007, o 22:52
Płeć: Mężczyzna
Lokalizacja: Biłgoraj/Kraków
Pomógł: 39 razy

Twierdzenie Gallai

Post autor: King James » 30 sie 2011, o 22:51

\(\displaystyle{ \nu(G)+\rho(G) = |V|}\)

Weźmy dowolne skojarzenie \(\displaystyle{ M}\) realizujące \(\displaystyle{ \nu(G)}\), w celu otrzymania pokrycia krawędziowego dołóżmy do niego po jednej krawędzi sąsiedniej z każdym wierzchołkiem \(\displaystyle{ V-V(M)}\) (nie ma wierzchołków izolowanych). Skonstruowane pokrycie jest wielkości \(\displaystyle{ |M|+(|V|-2|M|) = |V|-|M| \geq \rho(G)}\), zatem \(\displaystyle{ |V| \geq \nu(G)+\rho(G)}\).

Weźmy dowolne pokrycie krawędziowe \(\displaystyle{ F}\) realizujące \(\displaystyle{ \rho(G)}\), jest to las gwiazd, gdyż z dowolnego cyklu lub dowonej ścieżki długości co najmniej \(\displaystyle{ 3}\) moglibyśmy usunąć krawędź. W celu otrzymania skojarzenia, z każdej gwiazdy weźmy dowolnie wybraną krawędź, jest to równoważne usunięciu \(\displaystyle{ \text{deg}_F(v)-1}\) krawędzi w \(\displaystyle{ |F|}\) , dla każdego \(\displaystyle{ v \in V}\), zatem otrzymujemy skojarzenie wielkości \(\displaystyle{ |F|-\sum_{v \in V} (\text{deg}_F(v)-1) = |F|-(2|F|-|V|) = |V|-|F| \leq \nu(G)}\), zatem \(\displaystyle{ |V| \leq \nu(G)+\rho(G)}\).

\(\displaystyle{ \alpha(G)+\tau(G) = |V|}\)

Dla dowodu zauważ, że \(\displaystyle{ I}\) jest zbiorem niezależnym wtw \(\displaystyle{ V-I}\) jest pokryciem wierzchołkowym.

ODPOWIEDZ