szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 kwi 2017, o 18:25 
Użytkownik

Posty: 7
Lokalizacja: Warszawa
Zadanie przedstawia się następująco:

Wykaż, że każdy graf o m krawędziach zawiera podgraf dwudzielny posiadający co najmniej \frac{1}{2}m krawędzi.

Byłbym wdzięczny za jakieś poważniejsze wskazówki. :wink:
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 12 kwi 2017, o 22:08 
Użytkownik

Posty: 1086
Lokalizacja: Lublin/Warszawa
Znane zadanie.
Wpisz sobie treść po angielsku w Google, a otrzymasz parę rozwiązań:

http://sma.epfl.ch/~moric/gt2013/sol11.pdf
http://math.stackexchange.com/questions/289537/show-that-every-graph-g-has-a-bipartite-subgraph-with-at-least-half-of-the-edg

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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 stwierdzenie o grafie dwudzielnym  mike_btls  1
 trojkaty w grafie  buzzek90  0
 Wspólne krawędzie cyklu i rozcięcia w grafie  TrzyRazyCztery  0
 Cykl Hamiltona w grafie Petersena  Sage!  1
 Skojarzenia w grafie, minimalizacja sumy długości karawędzi.  e715489  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl