szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 6 wrz 2015, o 13:42 
Użytkownik

Posty: 3
Lokalizacja: Warschau
Witam.

Próbuje rozwiązać następujące zadanie, przygotowując się do egzaminu:

Cytuj:
Niech G będzie grafem dwudzielnym o klasach X i Y, w którym \left| X\right| = \left| Y\right| = 4k oraz \delta(G)  \ge k.

Załóżmy, że istnieją takie zbiory A  \subseteq X, B \subseteq Y, że \left| A\right|  \ge 2k, \left| B\right|  \ge 2k i każdy wierzchołek ze zbiorów A i B ma stopień co najmniej 3k w grafie G. Pokazać, że G ma skojarzenie doskonałe.


Nie do końca mam pomysł, jak to ruszyć. Znaczy, pomysły mam dwa: Twierdzenie Halla oraz Kolorowanie Krawędzi.

Nie mam pomysłu jak ruszyć twierdzenie Halla (zakładam, że nie-wprost?), coś mi świta jedynie, że po udowodnieniu, że dla jednej z klas zachodzi "zauważyć", że obie klasy są równej liczności, więc analogicznie można dowieść, że twierdzenie działa również dla drugiej klasy. Nie byłbym pewien, czy powołując się na takie stwierdzenie można już skończyć zadanie, czy istnienie doskonałego skojarzenia jeszcze (tudzież w ogóle) by z tego nie wynikało.

Co do kolorowania krawędzi - sądzę, że trzeba wymyślić jakiś sposób, algorytm, kolorowania owych krawędzi. Rozważałem w głowie \Delta-kolorowanie takie, że zaczynamy od kolorowania krawędzi przy wierzchołku o największym (najmniejszym?) stopniu w grafie, następnie poruszamy się po wierzchołkach sąsiednich kolorując dostępnymi kolorami niepokolorowane krawędzie; ponieważ dobre kolorowanie to podział wierzchołków na skojarzenia, skojarzenie o największej liczności będzie doskonałe... albo nie, bo właśnie nie wiem jak to pokazać.
Góra
Mężczyzna Offline
PostNapisane: 7 wrz 2015, o 10:14 
Użytkownik

Posty: 3
Lokalizacja: Warszawa
Tutaj akurat idzie z tw. Halla.
Góra
Mężczyzna Offline
PostNapisane: 7 wrz 2015, o 12:01 
Użytkownik

Posty: 3
Lokalizacja: Warschau
Z twierdzenia Halla zatem; pewnie dowodzę tego zupełnie źle, ale oto co wyprodukowałem:

(Nie wprost)
Niech G będzie grafem spójnym spełniającym dla ustalonego k założenia, o minimalnej możliwej liczbie krawędzi, nie spełniającym twierdzenia Halla i nie mającym skojarzenia doskonałego.
Zatem:
\left| A\right| = \left| B\right| = \left| X - A\right| = \left| Y - B\right| = 2k.

(skupmy się na klasie X; dla klasy Y analogicznie)

Ponieważ najmniejszy stopień wierzchołka w A lub B jest równy 3k, zatem istnieją krawędzie zaczynające się w A i kończące w Y - B. Wierzchołek z A jest zatem połączony z 2k wierzchołkami z B, oraz k wierzchołkami Y - B (wynika z minimalności krawędzi).

Ponieważ założyliśmy, że twierdzenie Halla nie jest spełnione, zatem \exists_{H\inX} \left| \Gamma_{G} (H)\right| < \left| H\right|. Intuicyjnie, wierzchołki takie, że \in X - A i tworzą krawędzie z B nie nadają się do takiego zbioru, ponieważ jest ich k, każdy o co najmniej 2k sąsiadach. Weźmy zatem podzbiór H klasy X o liczności k złożony z wierzchołków mających dokładnie \delta(G)=k (z minimalności) sąsiadów należących do Y-B i dodajmy do niego wierzchołek x \in X - A taki, który jest sąsiadem z sąsiadami H. Tak zdefiniowany podzbiór jest najmniejszy, przeczy spełnieniu warunku Halla oraz jest składową G - SPRZECZNOŚĆ, bo G z założenia jest spójny. Zatem istnieje dokładnie jedna krawędź \in e(H) łącząca H z jednym z pozostałych wierzchołków Y nienależących do H;

SRZECZNOŚĆ, ponieważ powiększa to nam zbiór sąsiadów H w taki sposób, że \left| \Gamma_{G} (H)\right| = \left| H\right|= k+1.
Zatem tw. Halla zachodzi w G i istnieje skojarzenie pokrywające wierzchołki z klasy X.

Analogicznie dowodzimy istnienia skojarzenia pokrywającego klasę Y.

Zatem graf G ma skojarzenie doskonałe.


(prosiłbym o kontrolę i wytknięcie idiotyzmów, jeśli występują)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Pokaż że graf prosty...  magdalenka88  4
 czy istnieje graf o stopniach wierzchołków  anilahcim  2
 graf półeulerowski, graf hamiltonowski, skoczek  owen1011  0
 graf krytyczny  mol_ksiazkowy  1
 Jaki warunek powinien być spełniony, aby graf dwudzielny  Marien  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl