szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 18 sty 2018, o 20:17 
Użytkownik

Posty: 5
Lokalizacja: Brodnica
Witam.
Mierzę się z takim zadaniem, znam rozwiązanie lecz nie mogę go sobie wyobrazić.
Oto treść:
G jest grafem G=(V,E) z liczbą wierzchołków równą |V|=23 takim, że dla każdego zbioru 5 wierzchołków istnieje co najmniej jedna krawędź pomiędzy nimi. Udowodnij, że |E| \ge 19 .
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 19 sty 2018, o 21:54 
Użytkownik

Posty: 1086
Lokalizacja: Lublin/Warszawa
Pokażę algorytm konstruujący ten graf:

Startujemy z grafu o 23 wierzchołkach bez krawędzi.
Powtarzamy następujący krok 19 razy:
Bierzemy dowolne 5 wierzchołków. Między nimi nie ma krawędzi, to znaczy że musi być przynajmniej jedna krawędź między tymi wierzchołkami, przyjmujemy, że w G te dwa wierzchołki będą połączone krawędzią i usuwamy jeden z nich.
Po wykonaniu tych kroków przywracamy usunięte wierzchołki i wybrane krawędzie do grafu, graf ma 19 krawędzi.

Wyjaśnić trzeba jeszcze dwie rzeczy:
Rzeczywiście możemy wykonać 19 kroków, bo po każdym kroku usuwamy jeden wierzchołek, czyli w ostatnim kroku zostaje 5 wierzchołków i możemy go wykonać.
W każdym kroku między pozostałymi wierzchołkami nie ma jeszcze krawędzi, bo zawsze usuwaliśmy jeden koniec nowo dodanej krawędzi.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Grafy-Ilość wierzchołków stopnia nieparzystego jest parzysta  blade  1
 [Teoria grafów] skojarzenie, graf dwudzielny  matinf  11
 Ilość możliwości wylosowania odpowiednich sztuk towaru  trissmerigold  2
 ilość wariacji z nietypowym warunkiem  kryszak  1
 Ilość liczb 3-cyfrowych  Ania221  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl