Орграфы и соединимость

Для полноты изложения мы начнем с определений. ОрграфD состоит из конечного множества Vвершини набораупорядоченных парразличных вершин. Любая такая пара (и, v) называетсядугой, илиориентированным ребром, и обычно обозначаетсяuv. Дуга uv идет из вершиныuв вершину v и называетсяинцидентнойuи v. Будем также говорить, чтоuсмежна к v, a v смежна изu.Полустепенью исходаod(v) вершины v называется число вершин, смежных из v, аполустепенью захода id (v)3 — число вершин, смежных к v.

В орграфе (ориентированным) маршрутомназывается чередующаяся последовательность вершин и дуг и v0,x1,v1,..., хn, vn в которой каждая дуга xi есть vi-1vi,. Длина такого маршрута равна числуnвходящих в него дуг. Взамкнутом маршрутепервая и последняя вершины совпадают;остовный маршрутсодержит все вершины.Путь- это маршрут, в котором все вершины различны, контур - нетривиальный замкнутый маршрут, у которого все вершины различны (за исключением первой и последней). Если существует путь из вершиныuв вершину v, то будем говорить, чтоv достижима из u; расстоянием d(u, v)отuдо v называется длина такого кратчайшего пути.

Каждый маршрут ориентирован от первой вершины v0 к последней vn. Нам также понадобится понятие, которое не обладает этим свойством ориентации и аналогично маршруту в графе.Полумаршрут— это опять таки чередующаяся последовательность v0,x1v1,..., хn, vn вершин и дуг, но дугой хi, 1<i<n, может быть как Vi-1Vi, так и vivi-1.Полупуть, полуконтури другие понятия определяются аналогично.

Поскольку граф может быть либо связным, либо нет, то существуют три различных способа определения связности орграфа, и каждый из них имеет свою собственную идиосинкразию. Орграф называется сильно связным, илисильным, если любые две его вершины взаимно достижимы;односторонне связным, илиодносторонним, если для любых двух вершин, по крайней мере, одна достижима из другой;слабо связным, илислабым, если любые две вершины соединены полупутем. Ясно, что каждый сильный орграф - односторонний, а каждый односторонний орграф - слабый, но обратные утверждения не верны. Орграф называетсянесвязным, если он даже не слабый. Заметим, чтотривиальный орграф, состоящий только из одной вершины, является (по определению) сильным, поскольку в нем нет двух различных вершин.

Сформулируем теперь необходимые и достаточные условия, обеспечивающие орграфу одну из этих трех типов соединимосги.

Теорема.Орграф сильный тогда и только тогда, когда он имеет остовный замкнутый маршрут; односторонний тогда и только тогда, когда он имеет остовный маршрут; слабый тогда и только тогда, когда он имеет остовный полупуть.

Для орграфа определены три типа компонент (связности). Сильной компонентойорграфа называется сильный максимальный подграф,односторонней компонентой- односторонний максимальный подграф ислабой компонентой- слабый максимальный подграф. Легко проверить, что любая вершина и любая дуга орграфа D принадлежат точно одной слабой компонентеuпо крайней мере одной односторонней компоненте. Более того, каждая вершина находится точно в одной сильной компоненте, а дуга либо лежит в одной сильной компоненте, либо не лежит ни в одной, в зависимости от того, принадлежит эта дуга или нет некоторому контуру.