Witam.
Mierzę się z takim zadaniem, znam rozwiązanie lecz nie mogę go sobie wyobrazić.
Oto treść:
\(\displaystyle{ G}\) jest grafem \(\displaystyle{ G=(V,E)}\) z liczbą wierzchołków równą \(\displaystyle{ |V|=23}\) takim, że dla każdego zbioru \(\displaystyle{ 5}\) wierzchołków istnieje co najmniej jedna krawędź pomiędzy nimi. Udowodnij, że \(\displaystyle{ |E| \ge 19}\) .
Teoria grafów, ilość krawędzi
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: Teoria grafów, ilość krawędzi
Pokażę algorytm konstruujący ten graf:
Startujemy z grafu o \(\displaystyle{ 23}\) wierzchołkach bez krawędzi.
Powtarzamy następujący krok \(\displaystyle{ 19}\) razy:
Bierzemy dowolne \(\displaystyle{ 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 \(\displaystyle{ 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 \(\displaystyle{ 19}\) krawędzi.
Wyjaśnić trzeba jeszcze dwie rzeczy:
Rzeczywiście możemy wykonać \(\displaystyle{ 19}\) kroków, bo po każdym kroku usuwamy jeden wierzchołek, czyli w ostatnim kroku zostaje \(\displaystyle{ 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.
Startujemy z grafu o \(\displaystyle{ 23}\) wierzchołkach bez krawędzi.
Powtarzamy następujący krok \(\displaystyle{ 19}\) razy:
Bierzemy dowolne \(\displaystyle{ 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 \(\displaystyle{ 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 \(\displaystyle{ 19}\) krawędzi.
Wyjaśnić trzeba jeszcze dwie rzeczy:
Rzeczywiście możemy wykonać \(\displaystyle{ 19}\) kroków, bo po każdym kroku usuwamy jeden wierzchołek, czyli w ostatnim kroku zostaje \(\displaystyle{ 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.