Новинарски форум

въпрос № 14 от конспекта

въпрос № 14 от конспекта

от Минко Марков -
Number of replies: 0

Здравейте,

 

Получих запитване относно въпрос № 14.  А именно,

какво се разбира под "теорема за броя на ребрата".

Тази теорема я няма в учебника, а не лекции пропуснах

да я спомена в явен вид като отделна теорема (макар

че д-вото на МПД свойството я ползва).

 

Теоремата казва, че ако към дърво G добавим едно

ребро, получаваме граф с точно един цикъл.  Доказва

се тривиално с допускане на противното.  Забележете,

че ако G е граф изобщо (а не именно дърво), добавянето

на едно ребро може да доведе до появата на > 1 цикли,

така че теоремата има смисъл.

 

Накратко, тази теорема отпада от въпрос № 14.  Естествено,

ако някой я формулира и докаже, това ще плюс за писмената

му/и работа.

 

Поздрави,

ММ