Предположим, что на улицах некоторого города требуется ввести одностороннее движение. При этом необходимо так ориентировать движение на каждой улице города, чтобы, не нарушая правил уличного движения, можно было проехать из любого участка города в любой другой участок. На языке теории графов эту задачу можно сформулировать следующим образом. Найти условия, при которых ребра неориентированного графа могут быть ориентированы так, чтобы получившийся орграф был сильно связен. Неориентированные графы, допускающие подобную ориентацию ребер, будем называть.
ориентируемыми графами. Ясно, что необходимым признаком ориентируемости графов является их связность. Достаточный признак ориентируемости графов можно сформулировать следующим образом:
Теорема 29. Связный граф G является
ориентируемым тогда и только тогда, когда он не содержит перешейков (т.е. каждое его ребро входит по крайней мере в один цикл, или, что-то же самое, граф является 2-связным).
Доказательство. Сначала отметим, что если теорема верна для элементарного графа, то она верна и для любых других графов. Поэтому будем предполагать граф G элементарным.
Очевидно, что если граф G имеет перешеек а с граничными вершинами А и В, то при ориентации перешейка а связь между вершинами А и В будет осуществляться лишь в одном направлении, и ориентированный граф не будет сильно связным.
Чтобы доказать обратное, опишем процесс ориентации ребер графа G, приводящий к появлению сильно связного орграфа. Возьмем некоторый простой цикл а, , а2,…, ап, проходящий через вершины А,, Л2,…, Ап. Если мы ориентируем этот цикл в любом направлении, то получим сильно связный подграф, состоящий из п дуг и п вершин.
Если все вершины графа G вошли в цикл А, А2,…, Ап, то искомый процесс ориентации можно считать завершенным. Предположим, что в графе G существуют вершины, отличные от А1, А2,…, Ап. Тогда, в силу связности графа G, существует вершина В, смежная некоторой вершине Л, выделенного цикла. Пусть b — ребро с граничными вершинами В и Л,. Тогда это ребро содержится в некотором цикле С. Ориентируем все ребра цикла С, не имеющие до сих пор направления. Припишем им ориентацию, соответствующую обходу С в любом направлении. Полученный в результате расширенный ориентированный граф является также сильно связным и содержит по крайней мере одну новую вершину, а именно В. Продолжая этот процесс до тех пор, пока все вершины графа G не войдут в расширенный граф, мы придем к сильно связному орграфу, включающему в себя все вершины графа G. Ориентируя наконец произвольным образом все пока не ориентированные ребра, закончим искомый процесс ориентации.
В заключении отметим, что если граф улиц города имеет перешейки, то, в силу теоремы 29, одностороннее движение по улицам установить не удастся и на перешейках придется разрешить движение в двух направлениях.
