Лекция 9. Программирование на сетях.

Вопросы: 1. Основные понятия теории графов.

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

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

4. Понятие разреза. Теорема Форда-Фалкерсона. Алгоритм решения задачи о

максимальном потоке.

5. Элементы сетевого планирования.

1. Основные понятия теории графов.

Теория графов – область дискретной математики, особенностью которой является геометрический подход к изучению объектов.

Основным объектом является граф и его обощения. Синонимами графа являются карта, диаграмма, сеть, лабиринт.

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

Формально граф определяется заданием двух (конечных) дискретных множеств: множеством вершин Х = {х₁, …, х_n} и множеством линий связи между ними

U= {u₁,…,u_m}.

Линии связи u_iназывают ребрами, если не указана их ориентация, и – дугами, если задано направление связи.

Граф с дугами называют ориентированным графом (орграфом), - с ребрами – неориентированным.

Пример. а) орграф б) неориентированный граф

Вершины х_iи х_j, связанные дугой/ребромu_k, называют концевыми вершинами этой дуги/ребра. Если концевые вершины совпадают, то дуга/ребро называется петлей. Дуги/ребра с одинаковыми концевыми вершинами называются параллельными. Граф без петель и параллельных линий связи называют простым.

Концевые вершины х_iи х_jодной дуги/ребра или дугиu_pиu_qс общей вершиной называют смежными.

Если вершина х_iявляется концевой для дуги/ребраu_k, то этиx_iиu_kинцидентны: вершина х_iинцидентна дуге/ребруu_k, а дуга/реброu_k– вершине х_i.

Т.о., смежность – отношение связанности между однородными элементами (вершинами или дугами/ребрами), а инцидентность – между разнородными (вершинами и дугами/ребрами).

Вершина, не имеющая отношений смежности, называется излированной.

Графы с одинаковым отношением инцидентности называются изоморфными.

Пример.

Изоморфные графы отличаются только геометрической конфигурацией.

Число дуг/ребер, инцидентных вершине х_i, называют степенью этой вершиныP(x_i). В орграфе различают полустепень заходаP⁺(x_i) и полустепень исходаP^-(x_i) вершины х_i, равные соответственно числу заходящих в х_iи исходящих из х_iдуг.P⁺(x_i) +P^-(x_i) =P(x_i).

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

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

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

Орграф (неориентированный граф) называют связным, если любые две его вершины можно соединить путем (цепью). В противном случае – несвязным. Связный орграф называют сильно связным, если для любых двух вершин х_iи х_jсуществуют пути из х_iв х_jи из х_jв х_i.

Пример.