Bridge: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Bridge''' --- мост. '''1.''' A '''bridge''' of a ''cycle'' <math>C</math> is the shortest path in <math>C</math> joining nonconsecutive vertices of <math>C<…») |
(нет различий)
|
Версия от 14:09, 24 февраля 2011
Bridge --- мост.
1. A bridge of a cycle [math]\displaystyle{ C }[/math] is the shortest path in [math]\displaystyle{ C }[/math] joining nonconsecutive vertices of [math]\displaystyle{ C }[/math] which is shorter than both of the edges of [math]\displaystyle{ C }[/math] joining those vertices. Thus a chord is a bridge of length 1, and a graph is bridged iff every cycle of length at least 4 has a bridge.
2. A bridge of [math]\displaystyle{ G }[/math] is an edge whose removal disconnects [math]\displaystyle{ G }[/math].