W piątek kolokwium z grafów i nie wszystko mi podchodzi, ale to jedno zadanie prowadzący zasugerował jako "zadanie, które MOŻE się pojawić", co zwiększa szanse na pojawienie się tego zadania na kolokwium do 99%, dlatego bardzo proszę o pomoc (najlepiej wytłumaczenie krok po kroku):
"Udowodnij indukcyjnie, że w każdym turnieju istnieje centrum, czyli taki wierzchołek, z którego można dojść do dowolnego innego ścieżką skierowaną długości nie większej niż 2."
Szczerze, to niby trochę rozumiem zagadnienie, ale nie mam już pojęcia jak to formalnie rozwiązać i zapisać za pomocą indukcji. Z góry dziękuję za każdą pomoc.
Turniej i jego centrum
-
bakala12
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Re: Turniej i jego centrum
Dowód przeprowadzimy przez indukcję matematyczną po liczbie wierzchołków w grafie.
Dla grafu o jednym wierzchołku teza jest oczywista.
Załóżmy teraz, że teza zachodzi dla dowolnego turnieju o \(\displaystyle{ n}\) wierzchołkach.
W kroku indukcyjnym rozważmy turniej \(\displaystyle{ T}\) o \(\displaystyle{ n+1}\) wierzchołkach. Niech \(\displaystyle{ v}\) będzie dowolnym wierzchołkiem \(\displaystyle{ T}\). Rozważmy turniej \(\displaystyle{ U=T \setminus v}\) (wyrzucamy z grafu wierzchołek \(\displaystyle{ v}\). Na mocy założenia indukcyjnego \(\displaystyle{ U}\) ma centrum \(\displaystyle{ c}\). Niech \(\displaystyle{ A}\) będzie zbiorem wierzchołków \(\displaystyle{ U}\) do których da się przejść bezpośrednio od \(\displaystyle{ c}\), a \(\displaystyle{ B}\) takim, dla których nie ma krawędzi bezpośrednio z \(\displaystyle{ c}\) do nich. Możliwe są 2 przypadki:
1. Istnieje krawędz od \(\displaystyle{ c}\) do \(\displaystyle{ v}\) w \(\displaystyle{ T}\). Wówczas \(\displaystyle{ c}\) jest centrum \(\displaystyle{ T}\).
2. Istnieje krawędz od \(\displaystyle{ v}\) do \(\displaystyle{ c}\). Wykażemy, że i w tym przypadku \(\displaystyle{ T}\) ma centrum. Jeżeli istnieje taki wierzchołek \(\displaystyle{ a \in A}\), dla ktorego jest krawędź z \(\displaystyle{ a}\) do \(\displaystyle{ v}\), to \(\displaystyle{ c}\) jest centrum \(\displaystyle{ T}\). W przeciwnym przypadku, z \(\displaystyle{ v}\) można bezpośrednio przejść do każdego wierzchołka z \(\displaystyle{ A}\). Z \(\displaystyle{ v}\) do każdego wierzchołka z \(\displaystyle{ B}\) można przejść wtedy ścieżką długości 2. Zatem wówczas \(\displaystyle{ v}\) jest centrum \(\displaystyle{ T}\).
Na mocy zasady indukcji matematycznej stwierdzamy, że teza jest prawdziwa dla dowolnego turnieju \(\displaystyle{ T}\).
Dla grafu o jednym wierzchołku teza jest oczywista.
Załóżmy teraz, że teza zachodzi dla dowolnego turnieju o \(\displaystyle{ n}\) wierzchołkach.
W kroku indukcyjnym rozważmy turniej \(\displaystyle{ T}\) o \(\displaystyle{ n+1}\) wierzchołkach. Niech \(\displaystyle{ v}\) będzie dowolnym wierzchołkiem \(\displaystyle{ T}\). Rozważmy turniej \(\displaystyle{ U=T \setminus v}\) (wyrzucamy z grafu wierzchołek \(\displaystyle{ v}\). Na mocy założenia indukcyjnego \(\displaystyle{ U}\) ma centrum \(\displaystyle{ c}\). Niech \(\displaystyle{ A}\) będzie zbiorem wierzchołków \(\displaystyle{ U}\) do których da się przejść bezpośrednio od \(\displaystyle{ c}\), a \(\displaystyle{ B}\) takim, dla których nie ma krawędzi bezpośrednio z \(\displaystyle{ c}\) do nich. Możliwe są 2 przypadki:
1. Istnieje krawędz od \(\displaystyle{ c}\) do \(\displaystyle{ v}\) w \(\displaystyle{ T}\). Wówczas \(\displaystyle{ c}\) jest centrum \(\displaystyle{ T}\).
2. Istnieje krawędz od \(\displaystyle{ v}\) do \(\displaystyle{ c}\). Wykażemy, że i w tym przypadku \(\displaystyle{ T}\) ma centrum. Jeżeli istnieje taki wierzchołek \(\displaystyle{ a \in A}\), dla ktorego jest krawędź z \(\displaystyle{ a}\) do \(\displaystyle{ v}\), to \(\displaystyle{ c}\) jest centrum \(\displaystyle{ T}\). W przeciwnym przypadku, z \(\displaystyle{ v}\) można bezpośrednio przejść do każdego wierzchołka z \(\displaystyle{ A}\). Z \(\displaystyle{ v}\) do każdego wierzchołka z \(\displaystyle{ B}\) można przejść wtedy ścieżką długości 2. Zatem wówczas \(\displaystyle{ v}\) jest centrum \(\displaystyle{ T}\).
Na mocy zasady indukcji matematycznej stwierdzamy, że teza jest prawdziwa dla dowolnego turnieju \(\displaystyle{ T}\).
-
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: Turniej i jego centrum
To ja jeszcze podam rozwiązanie z zasady ekstremum, żebyś mógł zaskoczyć prowadzącego oryginalnym podejściem xD
Weźmy wierzchołek \(\displaystyle{ v}\), z którego wychodzi najwięcej krawędzi (jeżeli jest wiele takich to wybierzmy dowolny). Niech \(\displaystyle{ A}\) to zbiór wierzchołków takich, do których wchodzi pewna krawędź wychodząca z \(\displaystyle{ v}\), a \(\displaystyle{ B}\) to zbiór wierzchołków takich, że z każdego z nich wychodzi krawędź wchodząca do \(\displaystyle{ v}\). Wtedy cały zbiór wierzchołków to \(\displaystyle{ V = A \cup B \cup \left\{ v\right\}}\). Widać, że istnieje ścieżka długości \(\displaystyle{ 1}\) z \(\displaystyle{ v}\) do dowolnego wierzchołka z \(\displaystyle{ A}\).
Pokażemy, że istnieje ścieżka długości \(\displaystyle{ 2}\) z \(\displaystyle{ v}\) do dowolnego wierzchołka z \(\displaystyle{ B}\). Weźmy dowolny wierzchołek \(\displaystyle{ x \in B}\). Mamy dwa przypadki:
Jeżeli z pewnego wierzchołka z \(\displaystyle{ A}\) wychodzi krawędź do \(\displaystyle{ x}\) to wtedy jest ścieżka długości \(\displaystyle{ 2}\) i ok.
W przeciwnym przypadku z wierzchołka \(\displaystyle{ x}\) wychodzi krawędź do każdego wierzchołka w \(\displaystyle{ A}\) - to znaczy, że z \(\displaystyle{ x}\) wychodzi \(\displaystyle{ |A| + 1}\) krawędzi, bo wychodzi z niego też krawędź do \(\displaystyle{ v}\). Tak więc \(\displaystyle{ x}\) ma większy stopień wychodzący niż \(\displaystyle{ v}\), sprzeczność.
\(\displaystyle{ v}\) jest centrum cnd.
Z tego rozwiązania wynika, że dowolny wierzchołek o największym stopniu wychodzącym jest centrum w turnieju.
Jednak nie jest prawdą, że każde centrum musi mieć największy stopień wychodzący w turnieju - wystarczy wziąć turniej, w którym z \(\displaystyle{ v}\) wychodzi dokładnie jedna krawędź, jest to krawędź \(\displaystyle{ v \rightarrow w}\) oraz z \(\displaystyle{ w}\) do dowolnego innego wierzchołka (różnego od \(\displaystyle{ v}\)) też wychodzą krawędzie. Wtedy \(\displaystyle{ v}\) jest centrum, ale ma stopień wychodzący \(\displaystyle{ 1}\), który jest mniejszy niż stopień wychodzący wierzchołka \(\displaystyle{ w}\) już dla turniejów składających się z przynajmniej \(\displaystyle{ 4}\) wierzchołków.
Weźmy wierzchołek \(\displaystyle{ v}\), z którego wychodzi najwięcej krawędzi (jeżeli jest wiele takich to wybierzmy dowolny). Niech \(\displaystyle{ A}\) to zbiór wierzchołków takich, do których wchodzi pewna krawędź wychodząca z \(\displaystyle{ v}\), a \(\displaystyle{ B}\) to zbiór wierzchołków takich, że z każdego z nich wychodzi krawędź wchodząca do \(\displaystyle{ v}\). Wtedy cały zbiór wierzchołków to \(\displaystyle{ V = A \cup B \cup \left\{ v\right\}}\). Widać, że istnieje ścieżka długości \(\displaystyle{ 1}\) z \(\displaystyle{ v}\) do dowolnego wierzchołka z \(\displaystyle{ A}\).
Pokażemy, że istnieje ścieżka długości \(\displaystyle{ 2}\) z \(\displaystyle{ v}\) do dowolnego wierzchołka z \(\displaystyle{ B}\). Weźmy dowolny wierzchołek \(\displaystyle{ x \in B}\). Mamy dwa przypadki:
Jeżeli z pewnego wierzchołka z \(\displaystyle{ A}\) wychodzi krawędź do \(\displaystyle{ x}\) to wtedy jest ścieżka długości \(\displaystyle{ 2}\) i ok.
W przeciwnym przypadku z wierzchołka \(\displaystyle{ x}\) wychodzi krawędź do każdego wierzchołka w \(\displaystyle{ A}\) - to znaczy, że z \(\displaystyle{ x}\) wychodzi \(\displaystyle{ |A| + 1}\) krawędzi, bo wychodzi z niego też krawędź do \(\displaystyle{ v}\). Tak więc \(\displaystyle{ x}\) ma większy stopień wychodzący niż \(\displaystyle{ v}\), sprzeczność.
\(\displaystyle{ v}\) jest centrum cnd.
Z tego rozwiązania wynika, że dowolny wierzchołek o największym stopniu wychodzącym jest centrum w turnieju.
Jednak nie jest prawdą, że każde centrum musi mieć największy stopień wychodzący w turnieju - wystarczy wziąć turniej, w którym z \(\displaystyle{ v}\) wychodzi dokładnie jedna krawędź, jest to krawędź \(\displaystyle{ v \rightarrow w}\) oraz z \(\displaystyle{ w}\) do dowolnego innego wierzchołka (różnego od \(\displaystyle{ v}\)) też wychodzą krawędzie. Wtedy \(\displaystyle{ v}\) jest centrum, ale ma stopień wychodzący \(\displaystyle{ 1}\), który jest mniejszy niż stopień wychodzący wierzchołka \(\displaystyle{ w}\) już dla turniejów składających się z przynajmniej \(\displaystyle{ 4}\) wierzchołków.