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 2019
Góra
Mężczyzna Offline
PostNapisane: 19 sty 2018, o 21:54 
Użytkownik

Posty: 1094
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 
 Ilość wymiernych składników w rozwinięciu dwumianu  help_me;)  0
 Ilość rozwiązań równania, nierozróżnialne ulotki do 10 przeg  kondzixd  1
 Ilość kombinacji ubrań.  spiker910  4
 Grafy-Ilość wierzchołków stopnia nieparzystego jest parzysta  blade  1
 teoria grafów - zadanie 4  dusia17  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl