13Вопрос

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

Как определялось ранее, вес подграфа - это сумма весов его ребер. Ясно, что во взвешенном графе существует остов наименьшего веса.

Существует алгоритм Краскала, позволяющий найти остов минимального веса в любом взвешенном графе. Дадим его описание по шагам.

Шаг 1. Найдем в данном графе ребро минимального веса (если таких несколько, фиксируем любое). Обозначим его через ; кроме того, фиксируем подграф в данном графе , состоящий из концов ребра и самого этого ребра. Обозначим этот подграф через .

Шаг 2. Фиксируем в данном исходном графе второе ребро - обозначим его через , - вес которого минимален относительно весов всех ребер, не принадлежащих . Подграф, состоящий из ребер , и их концов обозначим через .

Шаг 3. Фиксируем в графе ребро - обозначим его через , - имеющее минимальный вес среди всех ребер графа , не принадлежащих , и не составляющих цикла с ребрами из . Подграф, состоящий из ребер , , и их концов, обозначим через .

Шаг 4. Фиксируем в графе ребро - обозначим его через , - имеющее минимальный вес среди тех ребер графа , которые не принадлежат и не образуют цикла с ребрами из . Подграф, состоящий из ребер , , , и их концов обозначим через .

Общий шаг - шаг № k. Фиксируем в графе ребро – обозначим его через , - имеющее минимальный вес среди ребер, не входящих в и не составляющих цикла с ребрами из . Подграф, состоящий из ребер , , ,..., , обозначим через .

Можно доказать, что если в исходном графе количество вершин равно , то подграф будет искомым остовом.

14Вопрос

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

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

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

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

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

1) если и , то ;

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

3) если , то ;

4) если и , то .

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

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

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

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

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

,

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

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

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