Udowodnić, że spójny dwudzielny graf ma dokładnie jeden rozkład na dwa zbiory niezależne
(tzn. takie zbiory, w których żadne dwa wierzchołki nie są połączone krawędzią)
Wydaje mi się, że to wynika z definicji grafu dwudzielnego, ale mam problem z formalnym udowodnieniem...
graf spójny dwudzielny
-
Dasio11
- Moderator
- Posty: 10227
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: graf spójny dwudzielny
Z samej definicji grafu dwudzielnego wynika jedynie to, że istnieje przynajmniej jeden rozkład na dwa zbiory niezależne. Nie wyklucza to jednak możliwości, że takich rozkładów jest więcej - należy więc wykazać, że taki rozkład jest najwyżej jeden.
Weźmy zatem dowolne dwa rozkłady zbioru wierzchołków na dwa zbiory niezależne: \(\displaystyle{ V = A \cup A^c = B \cup B^c}\). Wtedy każda krawędź łączy albo wierzchołek zbioru \(\displaystyle{ A \cap B}\) z wierzchołkiem zbioru \(\displaystyle{ A^c \cap B^c}\), albo wierzchołek zbioru \(\displaystyle{ A^c \cap B}\) z wierzchołkiem zbioru \(\displaystyle{ A \cap B^c}\). Nie istnieje więc krawędź łącząca wierzchołek zbioru \(\displaystyle{ (A \cap B) \cup (A^c \cap B^c)}\) z wierzchołkiem zbioru \(\displaystyle{ (A^c \cap B) \cup (A \cap B^c)}\). Skoro jednak graf jest spójny, to jeden z tych zbiorów musi być pusty. Łatwo sprawdzić, że wtedy \(\displaystyle{ A = B}\) lub \(\displaystyle{ A = B^c}\).
Weźmy zatem dowolne dwa rozkłady zbioru wierzchołków na dwa zbiory niezależne: \(\displaystyle{ V = A \cup A^c = B \cup B^c}\). Wtedy każda krawędź łączy albo wierzchołek zbioru \(\displaystyle{ A \cap B}\) z wierzchołkiem zbioru \(\displaystyle{ A^c \cap B^c}\), albo wierzchołek zbioru \(\displaystyle{ A^c \cap B}\) z wierzchołkiem zbioru \(\displaystyle{ A \cap B^c}\). Nie istnieje więc krawędź łącząca wierzchołek zbioru \(\displaystyle{ (A \cap B) \cup (A^c \cap B^c)}\) z wierzchołkiem zbioru \(\displaystyle{ (A^c \cap B) \cup (A \cap B^c)}\). Skoro jednak graf jest spójny, to jeden z tych zbiorów musi być pusty. Łatwo sprawdzić, że wtedy \(\displaystyle{ A = B}\) lub \(\displaystyle{ A = B^c}\).