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

Задача 11


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


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Fri Sep 05, 2008 11:20 am    Заглавие: Задача 11

Задача 11. (К Георгиев) Да се докаже, че броя на мостовете в един прост граф е равен на разликата между броя на максималните му двусвързани компоненти и броя на максималните му свързани компоненти. (двусвързан граф е този, който остава свързан след премахване на произволно ребро)
[tex]|br(G)| = |C_2(G)| - |C_1(G)|[/tex]
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







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

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


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Fri Sep 05, 2008 2:59 pm    Заглавие:

Достатъчно е да докажем твърдението за всяка компонента на графа. Т.е. трябва да докажем, че за свързан граф G, е изпълнено br(G) = c(G)-1, където br(G) е броят на мостовете, а c(G) е броят на двъ-свързаните компоненти. Да разбием G на дву-свързани компоненти. Между някои двойки от тези компоненти има мостове. Между всяка двойка има най много един мост. Да разгледаме граф с върхове компонентите и ребра мостовете. Този граф е свързан, защото G е свързан. В този граф няма цикли, защото в противен случай бихме получили по-голяма дву-свързана компонента. Следователно този граф е дърво и ребрата му са с едно по-малко от върховете му.
Тоест br(G) = c(G)-1, което трябваше да се докаже.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
e^x
Начинаещ


Регистриран на: 22 Jan 2008
Мнения: 25

Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3Репутация: 8.3
гласове: 1

МнениеПуснато на: Tue Sep 23, 2008 6:17 pm    Заглавие: Чуденка

В кой учебник за 11 клас има подобна задача? Понеже в профилираната подготовка за 11 клас няма графи дори не знам какво точно е, интересно ми е за какво се използват и къде мога да намеря литература.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Tue Sep 23, 2008 6:25 pm    Заглавие:

трудно ще намериш такъв Very Happy Това че пише единадесета задача не означава че е за 11-ти клас Wink иначе теория на графите май дори из сайта я има обяснена Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
ferry2
Напреднал


Регистриран на: 10 Dec 2007
Мнения: 442
Местожителство: гр.Пловдив
Репутация: 55.9
гласове: 24

МнениеПуснато на: Tue Sep 23, 2008 6:29 pm    Заглавие:

Има я ,ето тук http://www.math10.com/forumbg/viewtopic.php?t=3370
А тук има по-изчерпателна информация!
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Задача на седмицата Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

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