Zadanie:
Wykaż, że graf dwudzielny regularny posiada skojarzenie doskonałe.
Wszelkie pomysły mile widziane.
Z góry dzięki.
Skojarzenie doskonałe grafu dwudzielnego
Skojarzenie doskonałe grafu dwudzielnego
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 ?
\(\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
- Użytkownik
- Posty: 4819
- Rejestracja: 10 paź 2006, o 23:03
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 43 razy
- Pomógł: 1407 razy
Skojarzenie doskonałe grafu dwudzielnego
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.
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.
Skojarzenie doskonałe grafu dwudzielnego
To jest prawda.Szemek pisze:ednakowa liczność obu klas
implikuje, że liczba wierzchołków n jest liczbą parzystą.
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 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
- Szemek
- Użytkownik
- Posty: 4819
- Rejestracja: 10 paź 2006, o 23:03
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 43 razy
- Pomógł: 1407 razy
Skojarzenie doskonałe grafu dwudzielnego
dla \(\displaystyle{ r=1}\)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}\)
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.
Skojarzenie doskonałe grafu dwudzielnego
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
- Użytkownik
- Posty: 4819
- Rejestracja: 10 paź 2006, o 23:03
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 43 razy
- Pomógł: 1407 razy
Skojarzenie doskonałe grafu dwudzielnego
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
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