6 0 1 СИСТЕМНЫЙ АНАЛИЗ ТЕМА 6. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Теория графов – раздел

математики, исследующий свойства множеств (мы ограничимся только конечными множествами), для

которых заданы отношения между элементами. С ее помощью можно описывать и исследовать технические, экономические, биологические и социальные системы и протекающие в них процессы.
Термин граф введен в 1936 г. Д.Кенигом. Однако первооткрывателем по праву считается Л.Эйлер, который за 200 лет до этого решил задачу о кенигсбергских мостах, состоящую в построении экскурсионного маршрута, проходящего по всем мостам, но только по одному разу.

Рис. 1. Пример графа

Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми

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

Цепью называется последовательность смежных вершин графа. Замкнутая цепь называется циклом.

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

Если любые две вершины графа можно соединить цепью, то граф

называется связанным. Если граф не является связанным, то его можно разбить на связанные подграфы, называемые компонентами.
Связностью графа называется минимальное число ребер, после удаления которых граф становится несвязанным. Для ориентированных графов, если любые две вершины графа можно соединить путем, то граф называется сильно связанным. Связность графа не может быть больше, чем ant[2m / n]. В сильно связанном графе через любые две вершины проходит контур.
Связанный граф, в котором существует эйлеров цикл, называется эйлеровым графом.

Плоским (планарным) называется граф, который можно изобразить на плоскости так,

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

Задача о кратчайшем пути. Пусть задан ориентированный граф, в котором

n + 1 вершина, две из которых выделены: вход (нулевая вершина) и выход (вершина с номером n). В любую вершину можно попасть из входа, а из любой вершины можно попасть на выход. Такой граф называют сетью. Для каждой дуги заданы числа, называемые длинами дуг. Длиной пути (контура) называется сумма длин входящих в него дуг (если длины дуг не заданы, то длина пути (контура) определяется как число входящих в него дуг). Задача заключается в поиске кратчайшего пути (пути минимальной длины) от входа до выхода сети.

Рис. 2. Поиск
кратчайшего пути

Аналогично задаче о кратчайшем пути формулируется и решается задача о

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

Более сложные задачи возникают, когда в графе имеются контуры. Не

просты задачи нахождения оптимальных путей, проходящих через заданные вершины. Замкнутый элементарный путь, охватывающий все вершины, называется гамильтовым путем или контуром.
Классическим примером задачи поиска гамильтонова контура является задача коммивояжера, который должен посетить n городов, побывав в каждом ровно один раз, и вернуться в исходный пункт своего путешествия. Заданы неотрицательные длины дуг, интерпретируемые как расстояние между городами или стоимости проезда. Требуется найти гамильтонов контур минимальной длины (в графе из n вершин существует n! гамильтоновых контуров).

По оси абсцисс будем последовательно откладывать номера предметов, по оси

ординат – их вес. Из каждой точки, начиная с точки (0;0), выходят две дуги – горизонтальная (соответствующая альтернативе «не брать предмет») и наклонная (соответствующая альтернативе «взять предмет»), вертикальная проекция которой равна весу предмета. Длины наклонных дуг положим равными ценности предметов, длины горизонтальных дуг – нулю. Полученная сеть (конечная вершина является фиктивной и вес любой дуги, соединяющей ее с другими вершинами, равен нулю) обладает следующими свойствами: любому решению задачи соответствует некоторый путь в этой сети; любому пути соответствует некоторое решение задачи. Таким образом, задача свелась к нахождению пути максимальной длины в полученном графе.

Номер предмета
Вес
Задача о рюкзак
для 10 вещей
одинакового веса
и одинаковой
ценности

Задача поиска контура минимальной длины решается следующим образом. Если известно,

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