Skojarzenie doskonałe grafu dwudzielnego

Szemek · Post autor: **Szemek** » 13 cze 2009, o 15:27

Zadanie:
Wykaż, że graf dwudzielny regularny posiada skojarzenie doskonałe.

Wszelkie pomysły mile widziane.
Z góry dzięki.

miodzio1988 · Post autor: **miodzio1988** » 13 cze 2009, o 15:38

Coś postaram się pomóc. Graf jest dwudzielny zatem można podzielić jego zbiór wierzchołkow na dwie klasy X i Y (o odpowiednich wlasnościach).
$\displaystyle{ \left|X \right|}$-liczność klasy X
$\displaystyle{ \left| Y\right|}$ - liczność klasy Y
Skoro graf jest r-regularny($\displaystyle{ r \in N}$) to prawdziwa jest równość:
$\displaystyle{ r\left|X \right| = r \left|Y \right|}$ - tego chyba nie muszę dowodzić, nie?

Zatem :
$\displaystyle{ \left|X \right| = \left|Y \right|}$
Teraz trzeba pokazać,że graf spełnia założenia tw. Tutte'a.

Trochę nie wiem co to jest to doskonałe skojarzenie, ale kojarzy mi się to z 1-faktoryzacją

Możę tw. Halla się przydać przy dowodzie też. Rzuciłem kilka pomysłów. Pomogły ?

Szemek · Post autor: **Szemek** » 13 cze 2009, o 16:57

Trochę mi to pomogło, ale muszę się wgryźć w te grafy.

Niech pomyślę...
Doszedłem do takich wniosków, choć nie wiem czy prawdziwych (?)
Jednakowa liczność obu klas implikuje, że liczba wierzchołków $\displaystyle{ n}$ jest liczbą parzystą.
Dla tego grafu dwudzielnego r-regularnego musi istnieć $\displaystyle{ \frac{n}{2}}$ krawędzi łączących wierzchołki należące do dwóch różnych klas i każdy wierzchołek jest użyty dokładnie jeden raz.

miodzio1988 · Post autor: **miodzio1988** » 13 cze 2009, o 17:09

Szemek pisze:ednakowa liczność obu klas
implikuje, że liczba wierzchołków n jest liczbą parzystą.

To jest prawda.

Szemek pisze:Dla tego grafu dwudzielnego r-regularnego musi istnieć $\displaystyle{ \frac{n}{2}}$ krawędzi łączących wierzchołki należące do dwóch różnych klas

A z czego to wynika? Musisz podać powód czemu tak jest. Tutaj chyba pomocne okażę się twierdzenie Halla. Musisz pokazać zatem, że graf Twoj będzie spełniał załozenia tw. Halla. To dam nam odpowiednią ilość niezależnych krawędzi. A stąd już tylko kroczek do doskonałego skojarzenia.

Szemek · Post autor: **Szemek** » 13 cze 2009, o 19:47

Pełne skojarzenie $\displaystyle{ X}$ z $\displaystyle{ Y}$ istnieje wtedy i tylko wtedy, gdy zachodzi $\displaystyle{ |A| \le |N_G(A)|}$ dla każdego podzbioru $\displaystyle{ A}$ zbioru $\displaystyle{ X}$
$\displaystyle{ N_G(A)}$ oznacza zbiór wierzchołków ze zbioru $\displaystyle{ Y}$ sąsiadujących z wierzchołkami ze zbioru $\displaystyle{ X}$

dla $\displaystyle{ r=1}$
mamy sytuację $\displaystyle{ $
\psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture}(0.0,0.0)(4.0,4.0)
\psline(1.00,3.5)(2.00,3.5)
\psdots[linecolor=blue](1.00,3.5)
\psdots[linecolor=blue](2.00,3.5)
\end{pspicture}
$}$ i ta jedyna krawędź jest skojarzeniem doskonałym
dla $\displaystyle{ r=2}$ i większych
Na początku: $\displaystyle{ A = X}$ oraz $\displaystyle{ Y = N_G(A)}$

Spostrzeżenia:

Wyrzucamy $\displaystyle{ r}$ wierzchołków ze zbioru $\displaystyle{ A}$ sąsiadujących z pewnym wierzchołkiem z $\displaystyle{ N_G(A)}$ - zatem tracimy więcej wierzchołków ze zbioru $\displaystyle{ A}$ niż ze zbioru $\displaystyle{ N_G(A)}$
Gdy $\displaystyle{ |A|=1}$, wtedy $\displaystyle{ |N_G(A)|=r}$.

Nie-wprost:
Weźmy sytuację, że wierzchołków w zbiorze $\displaystyle{ N_G(A)}$ jest mniej niż w zbiorze $\displaystyle{ A}$.
Mamy zależność w ilości krawędzi "wchodząco-wychodzących" $\displaystyle{ r|A|=x|N_G(A)|}$
$\displaystyle{ x = \frac{|A|}{|N_G(A)|}\cdot r}$
$\displaystyle{ x>r}$, czyli średnio na jeden wierzchołek ze zbioru $\displaystyle{ N_G(A)}$ przypada więcej krawędzi, niż wynosi maksymalny dopuszczalny stopień wierzchołka. Otrzymujemy sprzeczność.

Na to wygląda, że nierówność $\displaystyle{ |A|\le |N_G(A)|}$ jest spełniona dla każdego podzbioru $\displaystyle{ A}$ zbioru $\displaystyle{ X}$.
Zatem graf dwudzielny regularny posiada skojarzenie doskonałe.

To, co napisałem wydaje się nawet logiczne
Mimo wszystko będę wdzięczny za sprawdzenie.

miodzio1988 · Post autor: **miodzio1988** » 13 cze 2009, o 23:49

Myślę nad tym zadaniem no i ....sam lepiej bym tego nie zrobił Jednak sprowadziło się to do sprawdzenia, że graf spełnia warunek Halla

Szemek · Post autor: **Szemek** » 13 cze 2009, o 23:59

Dzięki miodzio1988 za odpowiednie nakierowanie podczas rozwiązywania zadania.

Z tego, co już dawno zdążyłem zauważyć to muszę poćwiczyć dowodzenie nie-wprost

PS: Znalazłem tw. Halla w notatkach, ale właściwie nie korzystałem nigdy w żadnym zadaniu z tego twierdzenia, więc sobie go nie przyswoiłem