Мосты в графе.

Ребро AB называется мостом графа, если при удалении этого ребра вершины А и В становятся несвязными.

Признаки моста:

1. Ребро АВ графа является мостом тогда и только тогда, когда оно является единственным путём, связывающим вершины А и В.

2. Ребро АВ является мостом тогда и только тогда, когда АВ не принадлежит ни одному циклу.

Доказательство:

1. допустим, что АВ принадлежит циклу, но тогда существует два пути, а это противоречит определению моста.

2. если АВ не принадлежит ни одному циклу, то АВ есть мост.

Удалим ребро АВ из графа, тогда А и В станут несвязными, а значит АВ является мостом.

3. Ребро АВ является мостом тогда и только тогда, когда существуют такие две вершины графа С₁ и С₂, что любой путь, идущий из С₁ в С₂ проходит по ребру АВ.