Графи

[2sxy4u]

Зад 1. Граф G(V,E), има n - върха и k - свързани компоненти. Докажете , че максималния брой ребра в G е равен на [tex]\frac{(n-k)(n-k+1)}{2 } [/tex].

Зад 2. В граф G(V,E), |V|=n . Докажете , че броя на триъгълниците в G и [tex]\overline{G} [/tex] е:
а) [tex]n\choose 3[/tex] - [tex]\frac{nk(n-k-1)}{2 } [/tex] в регулярен граф
б) [tex]\ge [/tex][tex]\frac{n(n-1)(n-5)}{24 } [/tex]

Регулярен граф - граф , в който всички върхове имат равна степен.
И моля ви някой да ми каже как да напиша n над k

[Реклама]

[nikko1]

n над k се пише елементарно: n\choose k

[2sxy4u]

Мерси

[nikko1]

Офф, хайде стана 3:45 am zzzzzzzzzzz. Днес следобед, ако имам време ще ги видя тия графи.

[Saposto_MM]

2 a)
Разглеждаме всички тройки върхове, такива че сред тях има два несъседни и два съседни. Ще докажем, че техния брой е [tex]\frac{nk\left(n-k-1\right)}{2} [/tex].
Разглеждаме връх v₁. Той има k съседни върха и n-k-1 несъседни. Нека v_i е съседен на v₁. Тогава за всеки несъседен на v₁ връх v_j, тези три върха образуват тройка дефинирана в началото. Всички такива тройки за v_i и v₁ са n-k-1. И понеже всички несъседни на v₁ е k, то броят на тези тройки, в който участва v₁ е k(n-k-1). И понеже броят на върховете на G е n, то броят на всички такива тройки е nk(n-k-1). Но забеляваме, че една тройка се брой два пъти. Това броене може да стане по два начина. Ако за връх v₁, v_j не е свързан със v₁ и v_i, то тази тройка се брой веднъж от v₁ и още веднъж от v_i. Ако v_i и v_j са съседни, то тази тройка се брой от, v₁ и v_j (това, че не се брой от v_i, следва от начина за броене, който използваме). С това задачата е решена.

Какво означава компонента. Чел съм на няколко места, но не ми става много ясно.

[nikko1]

[Saposto_MM]

Разглеждам всеки връх поотделно. Сред всяка тройка има два несъседни върха и два съседни.
Броя колко са тройките от вида б) и в) и като извадим техния брой от [tex]n\choose 3[/tex] получаваме броя на тройките от вида а) и г).

[nikko1]

[Saposto_MM]

И имам предвид. Всяка тройка има два свързани с ребро върхове и два несвързазни. Например тройката в), която си показал.

2 б)
Нека за всеки връх v_i на G означаваме с m_i степента му. Посредством разсъждения аналогични на тези в а) установяваме, че броя на триъгълниците е [tex]{n\choose 3}-\sum_{i=1}^{n}\frac{m_{i}\left(n-m_{i}-1\right)}{2}[/tex]. Използвайки неравенството между средно квадратично и средно аритметично и чрез преобразувания получаваме
[tex]{n\choose 3}-\sum_{i=1}^{n}\frac{m_{i}\left(n-m_{i}-1\right)}{2}={n\choose 3}+\sum_{i=1}^{n}\frac{m_{i}^{2}-\left(n-1\right)m_{i}}{2}\ge {n\choose 3}+\frac{\left(\sum_{i=1}^{n}m_{i}\right)^{2}}{2n}-\left(n-1\right)\frac{\sum_{i=1}^{n}m_{i}}{2}=\frac{1}{2n}\left(2n{n\choose 3}+\left(\sum_{i=1}^{n}m_{i}\right)^{2}-2\frac{n\left(n-1\right)}{2}\sum_{i=1}^{n}m_{i}+\left(\frac{n\left(n-1\right)}{2}\right)^{2}-\left(\frac{n\left(n-1\right)}{2}\right)^{2}\right)=\\=\frac{1}{2n}\left(\left(\sum_{i=1}^{n}m_{i}-\frac{n\left(n-1\right)}{2}\right)^{2}+2n\frac{n\left(n-1\right)\left(n-2\right)}{6}-\left(\frac{n\left(n-1\right)}{2}\right)^{2}\right)\ge \frac{n^{3}-6n^{2}+5n}{24}=\frac{n\left(n-1\right)\left(n-5\right)}{24}[/tex].

[krainik]