-
Данный раздел посвящен обзору наиболее популярных оптимизационных задач на графах и методам их решения.
-
Вначале познакомимся с понятием экстремального числа графа.
-
Экстремальное число графа G - это оценка решения некоторой оптимизационной задачи для данного графа
-
(максимума или минимума некоторой целевой функции в этой задаче).
-
Перед вами перечень основных экстремальных чисел графа и соответствующих оптимизационных задач на графах.
-
Итак, первое число - это цикломатическое число.
-
Оно служит оценкой для решения задачи поиска максимального числа независимых циклов в графе.
-
Второе число - это число внутренней устойчивости графа.
-
Это число служит оценкой для решения задачи поиска наибольших пустых подграфов в графе.
-
Третье число - кликовое.
-
Это оценка для решения оптимизационной задачи поиска наибольшего полного подграфа в графе.
-
Четвертое число - хроматическое.
-
Это оценка минимальной раскраски графа.
-
Пятое число - число внешней устойчивости графа.
-
И это число служит оценкой решения задачи минимального вершинного покрытия графа.
-
Шестое число, с которым мы познакомимся, - это число паросочетания.
-
Это оценка задачи поиска в графе максимального количества независимых ребер.
-
И наконец, последнее экстремальное число, с которым мы познакомимся в этом разделе - это число реберного покрытия.
-
Оно служит оценкой для решения задачи минимального реберного покрытия графа.
-
Итак, начнем с первого числа - цикломатическое число графа.
-
Цикломатическое число графа указывает на количество ребер, которые надо удалить из графа, чтобы получить его остовное дерево или его остовный лес.
-
Цикломатическое число графа определяется как результат вычитания из количества ребер графа количество вершин графа n и коррекция + k, где k - количество компонент связности в графе.
-
Для связного графа k=1 и формула определения цикломатического числа графа становится чрезвычайно простой: m-n+1.
-
Разумеется у вас возникнет такой вопрос: с каким максимумом или минимумом связано это число, если оно определяется как простое арифметическое выражение на основе основных характеристик графа -
-
количества ребер, количества вершин, количества компонент связности.
-
Ответ на этот вопрос дает следующая теорема, которая вошла в теорию графов как теорема об основном свойстве цикломатического числа графа.
-
Теорема звучит следующим образом: цикломатическое число графа определяет максимальное количество независимых циклов в нем.
-
Итак, максимальное количество независимых циклов.
-
Докажем эту теорему.
-
Пусть имеется некоторый n, m - граф, обыкновенный граф.
-
Иллюстрация для такого графа приведена здесь на рисунке.
-
Удалим из него все вершины вместе с инцидентными ребрами, которые отвечают следующим условиям:
-
для неографа мы удаляем вершины, у которых локальная степень равна 1;
-
а в орграфе мы будем удалять вершины вместе с инцидентными им дугами, у которых полустепень захода равна 1 или полустепень исхода равна 1.
-
Для нашей иллюстрации такими вершинами являются вершины, у которых локальная степень равна 1.
-
Эта вершина отмеченная на рисунке и инцидентное ей ребро.
-
И еще одна вершина вместе с инцидентным ей ребром удаляется из графа.
-
Получим новый n* , m* - граф G* , причем заметим, что цикломатическое число графа G и графа G*, полученного после удаления будет одинаковым,
-
так как удаленные ребра не входят ни в один из циклов графа G.
-
Затем построим в графе G* некоторое остовное дерево.
-
В этом остовном дереве будут все вершины этого графа, а также n*-1 ребро.
-
Например, вот такое остовное дерево графа G* построим для нашей иллюстрации.
-
Известно, что цикломатическое число дерева равно 0, т.к. в этом графе нет циклов.
-
Поэтому каждое ребро в графе G*, которое не вошло в состав ребер остовного дерева, образует в нем простой цикл.
-
Это свойство деревьев №4.
-
И причем эти циклы являются независимыми, т.к. в свойстве деревьев №4 говорится о том, что добавление в дерево ребра, инцидентного двум вершинам этого дерева, приводит к образованию цикла, этот цикл единственный и проходит по вновь добавленному ребру.
-
Наличие в каждом из таких циклов оригинального ребра, отмеченного на рисунке, говорит о том, что в этом графе есть 3 независимых цикла.
-
И цикломатическое число для графа, приведенного здесь на иллюстрации и графа G* и исходного графа G будет равно 3.
-
Поэтому цикломатическое число графа является экстремальным числом, несмотря на то, что оно подсчитывается как результат арифметической операции m-n+k, указывает на максимальное количество независимых циклов в графе.
