Да се докаже, че графът е свързан

[DevilFighter]

Даден е графа G(V, E), |V| = n, |E| > [tex]\frac{{(n - 1)(n - 2)}}{2}[/tex]

Да се докаже, че G е свързан.

[Реклама]

[xyz]

Нещо не ми се смята, но идеята, която бих приложил е следната.
Допускаме, че графът не е свързан. Следователно ще имаме разбиване на поне 2 компоненти (т.е. две непресичащи се множества от върхове, между които нямаме ребро). Ако във всяка компонента добавим вътрешните ребра, то задачата се осилва. Така нека в първата имаме s върха, а следователно във втората ще имаме n-s върха. Трябва да докажем, че сумарният брой на ребрата в новополучения граф не удовлетворява неравенството (т.е. така ще получим противоречие). Трябва да докажем, че:
[tex] {s(s-1) \over 2}+{(n-s)((n-s)-1) \over 2}<{(n-1)(n-2) \over 2} [/tex]
Това ще е изпълнено, ако следващата функция:
[tex] f(x):= {x(x-1) \over 2}+{(n-x)((n-x)-1) \over 2}[/tex]
е растяща при x в интервала (1,n-1), което предполагам, че може да се провери, лесно с помощта на намиране на производната.

[omeganet]

Допускаме, че G не е свързан. Нека си образуваме подграфи на G, които са свързани.
G₁(V₁, E₁), ..., G_m(V_m, E_m)

V₁, ..., V_m е разбиване на V => [tex]|V| = \sum\limits_{k = 0}^m {|V_k |}[/tex]
E₁, ..., E_m е разбиване на E => [tex]|E| = \sum\limits_{k = 0}^m {|E_k |}[/tex]

За всеки свързан граф е изпълнено, че |V| = |E| + 1. За нашия граф е изпълнено, че |V| = |E| + m. (?) => |Е| = |V| - m

Получаваме следното неравенство:
[tex]n - m > \frac{{n^2 - 3n + 2}}{2} \\ m < - \frac{1}{2}n^2 + \frac{5}{2}n - 1 = f(n) \\ f(n) \le 1 \Leftrightarrow n \in [0;1] \cup [4; + \infty )[/tex]
В този случай получаваме, че m=0. Ако n=2 или n=3 лесно се вижда, че графът е свързан.

[xyz]

Това не е съвсем вярно, тъй като равенството |V| = |E| + 1 е изпълнено единствено, ако подграфът е дърво.
Трябва да отбележа, че при моята идея за решение са ограничих на 2 компоненти, защото никъде не изисквам компонените да са свързани. Така взимаме една компонента, а останалите компоненти образуват втората. След това добавям ребрата до получаване на пълни графи - както вече съм описал - и т.н.

[omeganet]

Дам, прав си. Не обмислих добре твърденията си. Всички, написано от мен е вярно, стига в подграфите да няма цикли.

[DevilFighter]

Благодаря за разсъжденията!