Алгоритмы на графах и их приложения. Дорофеева В.И. - 7 стр.

UptoLike

ВУЗ: 

ОГУ | Орел

Составители: 

Рубрика: 

7
Рисунок 2
Два графа на рисунке 2 изоморфны.
Цепью называется последовательность дуг, в которой каждая промежу-
точная дуга соединена с предшествующим концом или началом. Например, на
рисунке 1 последовательность (n
1
, n
4
), (n
2
, n
4
), (n
3
, n
2
) – цепь из n
1
в n
3
. Двигаясь
вдоль цепи, можно пройти дугу в направлении, противоположном ее ориента-
ции. Дуги, проходимые в направлении ориентации, называются прямыми
дугами цепи, остальные – обратными дугами.
Граф называется вырожденным, если он не имеет ребер. Параллельными
ребрами графа называются такие, которые имеют общие узлы начала и конца.
Неориентированный граф G=(N, A) называется связанным, если для любых
двух узлов n
i
, n
j
принадлежащих N существует последовательность ребер из на-
бора A, соединяющий n
i
и. n
j
.
Пусть задан граф G=(N,A). Говорят, что на дугах графа реализуется чи-
словая функция, если каждой дуге (n
i
, n
j
) ∈G ставиться в соответствие число
µ
ij
=f(n
i
, n
j
) из некоторого множества M.
2 Оптимизация потока в сети
2.1 Формулировка задачи нахождения максимального потока в сети в
терминах теории графов
Изучение сетевых моделей началось еще в 40-х годах в связи с транс-
портными задачами, то есть задачами о прикреплении поставщиков к потреби-
                                     Рисунок 2

      Два графа на рисунке 2 изоморфны.
      Цепью называется последовательность дуг, в которой каждая промежу-
точная дуга соединена с предшествующим концом или началом. Например, на
рисунке 1 последовательность (n1, n4), (n2, n4), (n3, n2) – цепь из n1 в n3. Двигаясь
вдоль цепи, можно пройти дугу в направлении, противоположном ее ориента-
ции. Дуги, проходимые в направлении ориентации, называются прямыми
дугами цепи, остальные – обратными дугами.
      Граф называется вырожденным, если он не имеет ребер. Параллельными
ребрами графа называются такие, которые имеют общие узлы начала и конца.
Неориентированный граф G=(N, A) называется связанным, если для любых
двух узлов ni, nj принадлежащих N существует последовательность ребер из на-
бора A, соединяющий ni и. nj.
      Пусть задан граф G=(N,A). Говорят, что на дугах графа реализуется чи-
словая функция, если каждой дуге (ni, nj) ∈G ставиться в соответствие число
µij=f(ni, nj) из некоторого множества M.


    2 Оптимизация потока в сети
    2.1 Формулировка задачи нахождения максимального потока в сети в
терминах теории графов
      Изучение сетевых моделей началось еще в 40-х годах в связи с транс-
портными задачами, то есть задачами о прикреплении поставщиков к потреби-

                                             7

Страницы