Centum w digrafie

[mol_ksiazkowy]

Połączono skończona ilość punktów strzałkami tak że dowolne dwa punkty łączy strzałka. Udowodnić, że istnieje centrum tj. punkt, z którego można dojść do każdego innego w co najwyżej dwóch ruchach; idąc zgodnie z kierunkiem strzałek

[MrCommando]

Skorzystamy z zasady indukcji matematycznej. Dla jednego czy dwóch punktów nie ma w ogóle o czym mówić. Ustalmy zatem \(\displaystyle{ n\geq 1}\) i przypuśćmy, że dla dowolnych \(\displaystyle{ n}\) punktów połączonych strzałkami jak w treści zadania istnieje centrum. Weźmy dowolny zbiór \(\displaystyle{ n+1}\) punktów, powiedzmy \(\displaystyle{ A=\{A_1,A_2,\dots,A_{n+1}\}}\). Bez straty ogólności załóżmy, że \(\displaystyle{ A_1}\) jest centrum w zbiorze punktów \(\displaystyle{ \{A_1,A_2,\dots,A_n\}}\) (istniejącym na mocy założenia indukcyjnego). Rozważmy zbiór \(\displaystyle{ X\subseteq A}\) tych punktów, do których można dojść z \(\displaystyle{ A_1}\) w jednym kroku. Jeżeli dla pewnego punktu \(\displaystyle{ A_i \in X}\) istnieje strzałka do \(\displaystyle{ A_{n+1}}\), bądź jeśli \(\displaystyle{ A_{n+1}\in X}\), to \(\displaystyle{ A_1}\) jest centrum dla zbioru \(\displaystyle{ A}\) i teza jest udowodniona. W przeciwnym razie z punktu \(\displaystyle{ A_{n+1}}\) można dojść w jednym ruchu do \(\displaystyle{ A_1}\) oraz do każdego punktu z \(\displaystyle{ X}\) (ponieważ do \(\displaystyle{ A_{n+1}}\) nie wchodzi żadna strzałka idąca od \(\displaystyle{ A_1}\) lub od jakiegoś punktu ze zbioru \(\displaystyle{ X}\)). Oczywiście z \(\displaystyle{ X}\) można w jednym ruchu dojść do tych punktów, do których z \(\displaystyle{ A_1}\) można dojść w dwóch ruchach. Oznacza to, że z \(\displaystyle{ A_{n+1}}\) możemy w maksymalnie dwóch ruchach dojść do innego, zatem jest on wtedy nowym centrum. Zatem na mocy zasady indukcji matematycznej teza została udowodniona.