Zadanie przedstawia się następująco:
Wykaż, że każdy graf o \(\displaystyle{ m}\) krawędziach zawiera podgraf dwudzielny posiadający co najmniej \(\displaystyle{ \frac{1}{2}m}\) krawędzi.
Byłbym wdzięczny za jakieś poważniejsze wskazówki.
Podgraf dwudzielny w grafie
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Podgraf dwudzielny w grafie
Znane zadanie.
Wpisz sobie treść po angielsku w Google, a otrzymasz parę rozwiązań:
Inaczej:
Kolorujemy graf dwoma kolorami jakkolwiek. Następnie odpalamy algorytm, który w każdym kroku wybiera jeden wierzchołek spośród tych, które mają więcej sąsiadów w tym samym kolorze co on niż tych co są w innym kolorze i zmieniamy mu kolor na przeciwny - w każdym kroku zwiększa się liczba krawędzi między wierzchołkami różnych kolorów. Gdy już nie możemy wykonać żadnego kroku to każdy wierzchołek jest połączony z co najmniej tyloma wierzchołkami innego koloru niż on niż tego samego koloru co on, czyli liczba krawędzi o końcach różnych kolorów jest równa co najmniej połowie wszystkich krawędzi - bierzemy te krawędzie do podgrafu dwudzielnego.
Wpisz sobie treść po angielsku w Google, a otrzymasz parę rozwiązań:
Inaczej:
Kolorujemy graf dwoma kolorami jakkolwiek. Następnie odpalamy algorytm, który w każdym kroku wybiera jeden wierzchołek spośród tych, które mają więcej sąsiadów w tym samym kolorze co on niż tych co są w innym kolorze i zmieniamy mu kolor na przeciwny - w każdym kroku zwiększa się liczba krawędzi między wierzchołkami różnych kolorów. Gdy już nie możemy wykonać żadnego kroku to każdy wierzchołek jest połączony z co najmniej tyloma wierzchołkami innego koloru niż on niż tego samego koloru co on, czyli liczba krawędzi o końcach różnych kolorów jest równa co najmniej połowie wszystkich krawędzi - bierzemy te krawędzie do podgrafu dwudzielnego.