Основные определения из теории графов

Ориентированным конечным графом называется пара множеств , где - множество вершин, а - множество дуг, каждая из которых соединяет некоторую пару вершин графа. Дуга обозначается также парой вершин, которые она соединяет, например .

Ориентация дуги необходима, например, для изображения работы, так как она имеет начало и конец. Если ориентации нет или ее можно не учитывать, то говорят, что пара вершин соединена ребром (на рисунке изображается без стрелки). Так, если вершины графа есть станции АТС в городе, то телефонный кабель между двумя станциями можно представить ребром.

Ребро ориентированного графа называется дугой.

Сеть – ориентированный граф, в котором есть одна вершина - источник и одна вершина – сток.

Остов графа – минимальное количество ребер, необходимое для того чтобы между каждыми 2 вершинами существовала цепь (подграф данного графа, содержащий все его вершины и являющийся деревом). Алгоритм нахождения остова - 1) выписываются ребра в порядке возрастания весов; 2) задаются 2 множества: N – множество непомеченных дуг (изначально содержит все дуги), M – множество помеченных дуг (изначально Ø); 3)

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

Граф называется смешанным, если его вершины соединяются и ребрами и дугами.

Далее, если не оговорено особо, - ориентированный конечный граф.

Путь - это конечная последовательность дуг, в которой начало каждой следующей дуги совпадает с концом предыдущей.

Замкнутый путь называется контуром.

В неориентированном графе путь называется цепью, а контур - циклом.

Обозначим - граф, который получается из заменой дуг на ребра.

Граф называется связным, если между всякой парой вершин в графе существует по крайней мере одна цепь.

Граф называется сильно связным, если между всякой парой его вершин существует по крайней мере один путь.

Говорят, что граф антисимметричен, если из того, что следует, что обратной дуги нет, то есть .

Утверждение 1. Всякий граф без контура антисимметричен. Обратное утверждение не верно.

Если дугам ориентированного графа не приписаны веса, то длина пути есть количество дуг в этом пути.

Дуги вида называются предшествующими дуге .

Говорят, что вершина предшествует вершине (краткая запись ), если существует путь ненулевой длины от к . Отношение обладает следующими свойствами:

1) асимметричность: из следует, что не выполняется ;

2) транзитивность: из и следует, что ;

3) иррефлексивность: любая вершина не находится в отношении с вершиной (т.е. сама с собой).

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

Полный путь - путь из исходной вершины в завершающую.

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

Пропускная способность пути – минимальная из пропускных способностей дуг, в него входящих

Разрез – разбиение множества вершин V ориентированного графа на 2 непересекающихся подмножества

База дуг разреза – множество дуг, у которых начало лежит в множестве М, а конец в множестве N

Пропускная способность базы дуг разреза – сумма пропускных способностей дуг, в нее входящих