Bridge

Материал из WEGA
Версия от 14:09, 24 февраля 2011; 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<…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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].