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

Граф


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


Регистриран на: 06 Oct 2009
Мнения: 32

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

МнениеПуснато на: Mon Nov 23, 2009 6:41 pm    Заглавие: Граф

Да се докаже, че ако в един граф G(V,E),|V|=n и за всяко [tex]v_{i} \in V[/tex] е изпълнено [tex]d(v_{i}) \ge \frac{n-1}{2}[/tex], то графът е свързан.
Rolling Eyes
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







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

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


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

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

МнениеПуснато на: Tue Nov 24, 2009 11:05 am    Заглавие:

Лесно става. Допускаш, че всеки връх е свързан с поне [tex]\frac{n-1}{2}[/tex] ребра, но съществуват 2 върха [tex]v_1[/tex] и [tex]v_2[/tex], които не са свързани с път. Разглеждаш множествата [tex]V_i,\ i=1,2[/tex] от всички върхове, които са свързани с реброто [tex]v_i[/tex]. Според нашето допускане няма път между [tex]v_1[/tex] и [tex]v_2[/tex], следователно [tex]V_1\cap V_2=\emptyset[/tex].
Обаче двете множества имат мощности [tex]|V_i|\geq\frac{n-1}{2}[/tex] и след като имат празно сечение, то тяхното обединение има мощност [tex]|V_1\cup V_2|\geq \frac{n-1}{2}+\frac{n-1}{2}\geq n-1[/tex]. Обаче всички върхове са n, т.е. имаме максимум n-2 върха в [tex]V_1\cup V_2[/tex](след като изключим v_1 и v_2). Това е противоречие, което се дължи на допускането, че графът не е свързан. Следователно той е свързан.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martin123456
Фен на форума


Регистриран на: 23 Oct 2009
Мнения: 533

Репутация: 33.9Репутация: 33.9Репутация: 33.9
гласове: 15

МнениеПуснато на: Tue Nov 24, 2009 11:12 am    Заглавие: Re: Граф

asdf написа:
Да се докаже, че ако в един граф G(V,E),|V|=n и за всяко [tex]v_{i} \in V[/tex] е изпълнено [tex]d(v_{i}) \ge \frac{n-1}{2}[/tex], то графът е свързан.
Rolling Eyes


разглеждаме точки а,б между които няма път => не са директно свързани. няма точка в, че а директно свързано с в и б - в. нека а е свъзано с x точки директно. между а и б има n-2 точки. значи б е свързано с <= n-2-x.
x>=(n-1)/2
n-2-x<=(n-1)/2
=>против
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
asdf
Начинаещ


Регистриран на: 06 Oct 2009
Мнения: 32

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

МнениеПуснато на: Sat Nov 28, 2009 8:40 pm    Заглавие:

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

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