2.Матричное задание графа. Упорядочение вершин.

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

1. Граф без петель, имеющий nвершин иmдуг/ребер можно задатьматрицей инциденций, строки которой соответствуют вершинам, а столбцы – дугам. Элементы матрицы, размерностиnm, определяются по формуле

Для неориентированного графа вместо ”-1” ставится 1.

Пример.

2. Граф можно матрицей смежности вершин, строки и столбцы которой соответствуют вершинам графа. Элементы матрицыS_ijравны числу дуг/ребер, идущих из х_iв х_j. Матрица смежности для неориентированного графа будет симметричной.

Пример.

Аналогично может быть задана матрица смежности дуг/ребер.

Расчеты в задачах, связанных с графами, заметно упрощаются, если их элементы упорядочены.

Если существует путь из х_iв х_j, то вершина х_iназывается предшествующей вершине х_j, а х_j– последующей х_i.

Упорядочение вершин связного графа без контуров означает разбиение его вершин на группы так, чтобы:

1) вершины 1-й группы не имели предшествующих, а вершины последней – последующих;

2) вершины любой другой группы не имели предшествующих в следующей группе;

3) вершины одной и той же группы не соединялись с дугами.

Графический способ упорядочения вершин (алгоритм Фалкерсона).

1. Находятся вершины графа, в которые не входит ни одна дуга. Такие вершины образуют

1-ю группу.

2. Вершины и выходящие из них дуги установленной группы исключаются из дальней-

шего рассмотрения.

3. Устанавливается следующая группа вершин, в которые не входит ни одна дуга.

4. Если процесс упорядочения не окончен, то переход п. 2.

5. В полученном графе, изоморфном исходному, перенумеровываются вершины.

Пример.

3.Сети и потоки на сетях. Постановка задачи о максимальном потоке.

Сеть – конечный взвешенный связный орграф без контуров и петель, ориентированный в одном общем направлении от вершины I(исток, вход) к вершинеS(сток, выход).

Для наглядности представим, что по ребрам от истока к стоку направляется некоторое вещество (груз, ресурс, информация и т.п.).

Максимальное количество r_ijвещества, которое может пропустить за единицу времени ребро (i,j), называется его пропускной способностью. В общем случаеr_ij≠r_ji. Если вершины не соединены,r_ij= 0. Т.к. нет петель, тоr_ii= 0. Пропускную способность можно задать квадратной матрицей.

Количество х_ijвещества, проходящего по ребру (i,j) в единицу времени, называется потоком по ребру (i,j). Предполагается, что если из х_iв х_jнаправляется поток х_ij, то изx_jвx_iнаправляется поток (-х_ij)

x_ij= -x_ji. (1)

Поток по каждому ребру не превышает его пропускную способность

x_ij r_ij(i= ;j= ) . (2)

Количество вещества, притекающее в вершину, равно количеству вещества, вытекающего из неё

(i I,S). (3)

Совокупность Х = потоков по всем рёбрам сети называют потоком по сети. Общее количество вещества вытекающего из истокаI, совпадает с общим количеством вещества, поступающего в стокS, т.е.

F= x_Ij= x_iS. (4)

Функцию Fназывают мощностью потока.

Если на сети задан поток Х = , то ребро (i,j) называется насыщенным, если потокx_ijпо нему совпадает с его пропускной способностьюr_ij(x_ij=r_ij) , и ненасыщенным, еслиx_ij<rij.

Задачу о максимальном потоке можно сформулировать следующим образом: найти совокупность Х* = {x*_ij} потоковx*_ijпо всем рёбрам сети, которая удовлетворяет условиям (1) – (3) и максимизирует линейную функцию (4) . Это типичная ЗЛП.

Замечание. Не всякие n²чисел могут задавать поток по сети. Только такиеn²чиселx_ijзадают поток, которые удовлетворяют условиям (1) – (3) .

Пример.