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

Орграфы

 

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

 

 

Для полноты изложения мы начнем с определений. Орграф 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 по крайней мере одной односторонней компоненте. Более того, каждая вершина находится точно в одной сильной компоненте, а дуга либо лежит в одной сильной компоненте, либо не лежит ни в одной, в зависимости от того, принадлежит эта дуга или нет некоторому контуру.