lekcii_dm

Граф Н называется частью графа G, H G, если его множество вершин V H содержится в множестве вершин V G графа b, и все рёбра Н являются рёбрами G.

Нуль-граф считается частью каждого графа.

Определение.

Для любой части Н графа G существует единственная дополнительная часть (дополнение) H , состоящая из всех рёбер графа G, которые не принадлежат Н, то есть H G H .

2.04. Бинарные отношения в теории графов.

Определение.

Бинарное отношение определяется как соотношение a b, которое выполняется для некоторых пар элементов заданного множества V.

Между бинарными отношениями и графами с однократными рёбрами существует взаимно однозначное соответствие.

Так, например. Нуль — граф отвечает нулевому отношению a0b . Полный граф U отвечает универсальному отношению aUb .

Каждое отношение имеет дополнительное отношение, или отрицание , такое что a b тогда и только тогда, когда a b не выполняется.

52

Определение.

Граф G является дополнением к Графу G , то есть

G U V G R по отношению к полному графу U , определённому на V.

Определение.

Для любого отношения существует обратное отношение *, такое что b *a тогда и только тогда, когда выполняется a b.

Определение.

Отношение a b называется частичным упорядочением, если оно обладает следующими свойствами:

1.Рефлексивность a a .

2.Транзитивность. Из a b и b c , следует a c .

3.Антисимметричность. Из a b и b a следует a b .

Соответствующий граф транзитивен, имеет петли, и любые две вершины в нём соединены не более чем одним ребром.

Например:

2.05. Матрицы смежности и инцидентности.

Во многих задачах теории графов (особенно решаемых на ЭВМ) графы удобно описывать матрицами.

53

Матрица смежности (A ) для неориентированного графа (G ) всегда симметрична.

Фигурирующая в ней двойка (2) или любое другое обозначение в некоторых случаях может быть заменена на единицу(1).

В матрице инцидентности сумма единиц по столбцам указывает степень вершины vi .

55

Вобщем случае матрица смежности для ориентированного графа уже не будет симметричной.

Вматрице инцидентности ставится 1, если дуга исходит из вершины

и1, если дуга заходит в неё.

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

2.06. Маршруты, цепи и простые цепи.

Определение.

Маршрутом в графе G называется такая конечная или бесконечная

последовательность рёбер S ,E0 ,E1, ,En , , что каждые два соседних ребра Ei и Ei 1 имеют общую концевую точку. То есть

,E0 a0 ,a1 , ,E1 a1,a2 , ,En an ,an 1 , .

Замечания.

1.Одно и тоже ребро Ei может встречаться в маршруте несколько раз.

2.Если нет рёбер, предшествующих E0 , то a0 называется начальной вершиной S , а если нет рёбер, следующих за En 1, то an называется

конечной вершиной S .

3. Любая вершина ai , принадлежащая двум соседним рёбрам Ei и Ei 1, называется внутренней или промежуточной вершиной. Так как рёбра и вершины в маршруте могут повторяться, внутренняя вершина может также оказаться начальной или конечной вершиной.

Определение.

56

2.07. Транспортные сети

Транспортной сетью называется орт граф D (u,x)

U{ 1, 2 ,..., n} для которого выполняются условия:

1)одна и только одна вершина называется источником D 1( 1) 0 D 1( 1) множество дуг заходящих в точку

2)-//- верш . называется истоком т.ч. D( n ) 0

3)Каждой дуге x X сопоставляется число (целое и не отрицательное) т.ч. C(x) 0 называемое пропускной способностью дуги

4)Вершины отличные от источника и истока называются промежуточными

Определение.

Функция (x) определенная на множестве X граф D и принимающая целочисленные значения называется потоком транспортной сети D, если

( , ) ( , )

D 1( ) D( )

Сколько вышло столько и вошло.

( 1, ) ( 1, n )D( 1) D 1( n )

Определение.

x X называется насыщенным, если поток по ней равен ее пропускной способности (x) C(x)

Определение.

58

поток называется полным, если его путь из 1 в n содержит хотя бы одну насыщенную дугу

Определение.

Поток называется максимальным, если принимает максимальное значение по сравнению с другим допустимым потоком.

Замечание.

Максимальный поток является полным, но обратно не верно.

Алгоритм построения полного потока

2)из D удаляем дуги являющиеся насыщенными D D

3)ищем в D простую цепь

: 1 n , если не находим, то конец.

- искомый поток по определению

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

их пропускных способностей

2.08. Связность. Компоненты связности

Определение.

Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. (Для орграфа то же).

Определение.

Подграф называется собственным, если он отличен от самого графа.

59

Определение.

Говорят, что вершина w орграфа D (графа G) достижима из верш. v, если либо w=v, либо существует путь (маршрут) из v в w.

Определение.

Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w.

Определение.

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

Определение.

Псевдографом, ассоциированным с ориентированным псевдографом D=(V,X) наз. псевдограф G=(V,X0), в котором X0 получается из X заменой всех упорядоченных пар (v,w) на неупорядоченные {v,w}.

Определение.

Орграф наз слабо связным, если связным является ассоциированный с ним псевдограф.

Определение.

Если граф (орграф) не является связным (слабо связным), то он наз. несвязным.

60