Сильносвязные сети

В дальнейшем под словом сеть будем подразумевать двухполюсную сеть. Сеть называется связной, если соответствующий граф связный. Вместо слов «цепь, соединяющая полюса», будем говорить «цепь». Связная цепь называется сильносвязной, если через каждое её ребро проходит цепь.

Лемма. Пусть Г = Г (а, – произвольная сеть с полюсами а и и пусть через вершины и сети Г проходят цепи. Если вершины и можно соединить маршрутом, то существует цепь, проходящая через и .

Доказательство. Составим цепь из части первой от полюса а до маршрута - и части второй цепи от до <

Пусть в сети Г (а, выделено подмножество рёбер, которое определяет подграф. Вершина подграфа называется граничной, если она полюс сети, либо конец ребра, не принадлежащего подграфу. Подграф с единственной граничной вершиной называется отростком.

ТЕОРЕМА. Связная сеть сильносвязна не содержит отростков.

Доказательство. Пусть связная сеть сильно связна и содержит отросток. Маршрут, соединяющий полюса и проходящий через ребро отростка, должен, по крайней мере, дважды пройти через граничную вершину отростка. Такой маршрут не является цепью (по определению цепь не проходит через вершины дважды).

Пусть связная сеть Г (а, не содержит отростков и предположим, что она не сильно связна. Тогда в ней есть рёбра, через которые не проходит ни одной цепи. Пусть – максимальное связное подмножество рёбер, обладающих этим свойством. В силу связности сети имеет граничные вершины. По условию в нашей сети нет отростков, поэтому существует по крайней мере две граничные вершины и подграфа Через вершины и проходят цепи. В силу связности по лемме существует цепь, проходящая через вершины и и через рёбра Получим противоречие с условиями, которые налагались на ребра ■