Bridge: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''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].