Регистрирайте сеРегистрирайте се

Графи


 
   Форум за математика Форуми -> Дискретната математика
Предишната тема :: Следващата тема  
Автор Съобщение
2sxy4u
Начинаещ


Регистриран на: 17 May 2008
Мнения: 57

Репутация: 10.8
гласове: 3

МнениеПуснато на: Tue Jan 13, 2009 2:51 am    Заглавие: Графи

Зад 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 Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
nikko1
Напреднал


Регистриран на: 23 Nov 2008
Мнения: 422

Репутация: 61.8
гласове: 36

МнениеПуснато на: Tue Jan 13, 2009 3:34 am    Заглавие:

n над k се пише елементарно: n\choose k
Smile
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
2sxy4u
Начинаещ


Регистриран на: 17 May 2008
Мнения: 57

Репутация: 10.8
гласове: 3

МнениеПуснато на: Tue Jan 13, 2009 3:41 am    Заглавие:

Мерси
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nikko1
Напреднал


Регистриран на: 23 Nov 2008
Мнения: 422

Репутация: 61.8
гласове: 36

МнениеПуснато на: Tue Jan 13, 2009 3:46 am    Заглавие:

Офф, хайде стана 3:45 am zzzzzzzzzzz. Днес следобед, ако имам време ще ги видя тия графи.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Saposto_MM
Напреднал


Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
Репутация: 124.4
гласове: 67

МнениеПуснато на: Tue Jan 13, 2009 6:46 pm    Заглавие:

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

Какво означава компонента. Чел съм на няколко места, но не ми става много ясно.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nikko1
Напреднал


Регистриран на: 23 Nov 2008
Мнения: 422

Репутация: 61.8
гласове: 36

МнениеПуснато на: Tue Jan 13, 2009 7:45 pm    Заглавие:

MM написа:
2 a)
Разглеждаме всички тройки върхове, такива че сред тях има два несъседни и два съседни.

Как става това, в една тройка върхове има 3 двойки, така че може да има следните четири възможности:
а) 3 несъседни двойки върхове;
б) 1 съседна и 2 несъседни;
в) 2 съседни и 1 несъседна;
в) 3 съседни двойки.



dwoiki.PNG
 Description:
 Големина на файла:  4.42 KB
 Видяна:  2032 пъти(s)

dwoiki.PNG


Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Saposto_MM
Напреднал


Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
Репутация: 124.4
гласове: 67

МнениеПуснато на: Tue Jan 13, 2009 9:28 pm    Заглавие:

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


Регистриран на: 23 Nov 2008
Мнения: 422

Репутация: 61.8
гласове: 36

МнениеПуснато на: Tue Jan 13, 2009 10:00 pm    Заглавие:

MM написа:
Разглеждам всеки връх поотделно. Сред всяка тройка има два несъседни върха и два съседни.
...

Предполагам, имал си предвид или, а не и.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Saposto_MM
Напреднал


Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
Репутация: 124.4
гласове: 67

МнениеПуснато на: Wed Jan 14, 2009 3:33 pm    Заглавие:

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

2 б)
Нека за всеки връх vi на G означаваме с mi степента му. Посредством разсъждения аналогични на тези в а) установяваме, че броя на триъгълниците е [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
Фен на форума


Регистриран на: 01 May 2009
Мнения: 697

Репутация: 51.8
гласове: 44

МнениеПуснато на: Fri Jul 10, 2009 8:51 pm    Заглавие:

MM написа:

Какво означава компонента. Чел съм на няколко места, но не ми става много ясно.
Компонента на графа G е всеки максимален свързан подграф на G.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Дискретната математика Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2021 math10.com.