Matematyka.pl

Niemalejący ciąg liczb naturalnych \(\displaystyle{ ⟨s_1,…,s_n⟩}\) jest ciągiem stopni wyjściowych wierzchołków \(\displaystyle{ n}\)-turnieju \(\displaystyle{ T}\). Udowodnij, że \(\displaystyle{ T}\) jest silnie spójny wtedy i tylko wtedy, gdy
\(\displaystyle{ \sum_{i = 1}^{k} s_i > {k \choose 2}}\) dla \(\displaystyle{ 1 \le k < n}\)

Jak takie coś się robie ? Byłabym bardzo wdzięczna za pełne rozwiązanie (to jest zadanie z listy przygotowawczych, więc było by bardzo przydatne wiedzieć tego rozwiązanie).
Jedyne co wiem to to, że że \(\displaystyle{ T}\) jest silnie spójny wtedy i tylko wtedy, gdy zawiera cykl Hamiltona, a warunek wyst na istnienie cyklu Hamiltona to tw. Orego : Jeżeli w grafie prostym \(\displaystyle{ G}\) o \(\displaystyle{ n}\) wierzchołkach (\(\displaystyle{ n>2}\)) zachodzi następująca nierówność:
\(\displaystyle{
{\displaystyle \deg(v)+\deg(u)\geqslant n}{\displaystyle \deg(v)+\deg(u)\geqslant n}}\)
dla każdej pary niepołączonych bezpośrednio krawędzią wierzchołków \(\displaystyle{ u}\) i \(\displaystyle{ v}\).

Jeśli \(\displaystyle{ T}\) nie jest silnie spójny, to istnieje silnie spójna składowa \(\displaystyle{ A}\), taka że nie ma krawędzi z \(\displaystyle{ A}\) na zewnątrz. Wtedy

\(\displaystyle{ \sum_{v \in A} \deg(v) \le \binom{|A|}{2}}\),

więc tym bardziej

\(\displaystyle{ \sum_{i=1}^{|A|} s_i \le \binom{|A|}{2}}\)

z uwagi na niemalejącość \(\displaystyle{ \left< s_1, \ldots, s_n \right>}\).

Z drugiej strony jeśli

\(\displaystyle{ \sum_{i=1}^k s_i \le \binom{k}{2}}\)

dla pewnego \(\displaystyle{ 1 \le k < n}\), to z podzbioru \(\displaystyle{ A = \{ v_1, \ldots v_k \}}\) złożonego z różnych wierzchołków \(\displaystyle{ v_i}\), takich że \(\displaystyle{ \deg(v_i) = s_i}\), nie wychodzi na zewnątrz żadna krawędź. Zatem \(\displaystyle{ T}\) nie jest silnie spójny.