Задача с граф.

[zhivo_zad]

Как ще се реши тази задачка?


Даден е граф G с 10 върха и 26 ребра.Да се докаже,че G съдържа поне 4 триъгълника.

[Реклама]

[Мирослав Стоенчев]

Теорема на Радемахер. Ако граф [tex] G [/tex] с [tex]n[/tex] върха има повече от [tex]\frac{n^{2}}{4}[/tex] ръба, то [tex]G [/tex] съдържа поне [tex]\left\[\frac{n}{2}\right\][/tex] триъгълника.

Задача 1. Р-е: [tex]n=10,\ 26>\frac{10^2}{4}=25\Rightarrow G[/tex] съдържа поне [tex]\left\[\frac{10}{2}\right\]=5[/tex] триъгълника.

[krassi_holmz]

Някакво доказателство? (...или линк)?

[krassi_holmz]

Другия вариант е с броене, но се получава не толкова остро (но достатъчно за задачата):
Нека G(x) е множеството от върховете, съседни на х.
Тогава броят на триъгълниците може да се ограничи по следния начин:
[tex]3t=\sum_{xy\in E}|G(x)\cap G(y)| = \sum_{xy \in E}d(x)+d(y)-|G(x) \cup G(y)| \geq \sum_{xy \in E}(d(x)+d(y) - n) = \sum_{xy \in E}(d(x)+d(y)) - n m = \sum_{x \in V}d^2(x) - n m \geq \frac{\(\sum_{x \in V} d(x)\)^2}{n} - m n = \frac{4m^2}{n}-m n[/tex]
[tex]t \geq \frac{4m^2}{3n}-\frac{m}{3n}[/tex]
За нашия случай n=10, m=26 и следователно:
[tex]t \geq \frac{52}{15}[/tex]
[tex]t \geq 4[/tex]