Задача 11

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

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

[Реклама]

[Baronov]

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

[e^x]

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

[martosss]

трудно ще намериш такъв Това че пише единадесета задача не означава че е за 11-ти клас иначе теория на графите май дори из сайта я има обяснена

[ferry2]

Има я ,ето тук http://www.math10.com/forumbg/viewtopic.php?t=3370
А тук има по-изчерпателна информация!