Мостове в граф (авторска)

[krassi_holmz]

Във връзка със задача B2 от ЗИС 2008 предлагам следната задача, която ми се струва интересна:
Да се докаже, че броя на мостовете в един прост граф е равен на разликата между броя на максималните му двусвързани компоненти и броя на максималните му свързани компоненти.
(двусвързан граф е този, който остава свързан след премахване на произволно ребро)

[tex]|br(G)| = |C_2(G)| - |C(G)|[/tex]

Hint: каква е конфигурацията на двусвързаните компоненти във всяка свързана?

[Реклама]