13. Ориентированный граф и его графическая интерпретация. Локальные степени. Мат-рица смежностей. Ориентированные пути и связность в ориентированном графе

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

Если и , то называется Началом, а называется Концом ребра ; как и в «неориентированном случае», вершины , называются Инцидентными ребру , а ребро называется Инцидентным вершинам , .

Орграф имеет естественную геометрическую интерпретацию: его вершины изображают-ся в виде точек на плоскости, а ребра – в виде стрелок, идущих из начала в конец ребра. Напри-мер, если орграф имеет в качестве множества вершин и в качестве множества ребер , то геометрически он выглядит так:

Если два орграфа таковы, что одновременно выполняются два условия - и , - то говорят, что - подграф орграфа При этом пишут: . Если одновременно и , то орграфы называются Равными и пишут .

Два орграфа - - называются Изоморфными, если существует отображение такое, что выполнены следующие четыре условия:

1) если и , то ;

2) для всякого существует такой , что ;

3) если , то ;

4) если и , то .

Если - орграф и , то следующие три числа имеют специальные названия: число (количество ребер, исходящих из вершины ) называется Исходящей степенью вершины ; число (количество ребер, входящих в вершину ) называется Входящей степенью Вершины ; число называется Степенью вершины .

Каждый орграф можно описать Матрицей смежностей По следующей схеме: если , то построим матрицу положив

С каждым орграфом однозначно связывается обычный граф , в котором множество вершин - то же самое (т. е. множество ), а множество ребер получается «стиранием стрелок» у ребер из множества (т. е. если , то тогда и только

Тогда, когда либо , либо ). Граф называется Ассоциированным с орграфом .

В каждом орграфе выделяется основной объект – Ориентированный путь (или кратко - Орпуть) Орпуть - это символ

,

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

Две вершины орграфа называются Связанными, если имеется орпуть из в и одновременно имеется орпуть из в . Орграф называется Связным, если в нем любые две вершины связанны. Так же, как в неориентированном случае, понятие связности приводит к понятию связной компоненты: подграф орграфа называется Связной компонентой оргра-фа , если: 1) является связным орграфом; 2) не существует связного орграфа такого, что и .

Подобно тому, как это делалось в случае обычных графов, для ориентированных графов вводятся понятия цепи, простой цепи, цикла и простого цикла. Эти объекты можно исследовать по тому же плану, что и в неориентированном случае.

< Предыдущая		Следующая >