Основные классы графов

31 января 2024 г.

Это краткий конспект части об основных классах графов в книге Гид по Computer Science, Вильям Спрингер.

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

Запрещенные подграфы

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

Запрещенные подструктуры могут быть определены несколькими способами:

1. Графы - Граф не содержит подграфа из (возможно, бесконечного) множества. Например, двудольные графы — не содержат нечетных циклов.
2. Индуцированные графы - то же что и в предыдущем случае, только которые не содержат индуцированных подграфов (некоторое подмножество вершин графа вместе со всеми ребрами между этими вершинами). Например, хордальные графы — не содержат индуцированного бесхордового цикла длиной не менее четырех.
3. Гомеоморфные графы - один граф можно получить из другого, удалив вершины второй степени (те, которые имеют ровно два ребра) и свернув два ребра в одно.
4. Минор графа - подграф, который получают через стягивание ребер (Выбираем две смежные вершины и объединяем в одну).

Класс графов может иметь несколько характеризаций запрещенными подграфами разных типов.

Планарные графы

Класс графов, представляющих карты на плоскости (или сфере). Он может быть нарисован так, что все его ребра пересекаются только в вершинах графа.

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

Теорема Понтрягина — Куратовского - граф планарен тогда и только тогда, когда он не содержит подразделений полного графа с пятью вершинами и полного двудольного графа с тремя вершинами в каждой доле (K3,3). То есть она классифицирует планарные графы в терминах запрещенных подграфов.

Теорема Вагнера - планарные графы не содержат те же подграфы в качестве миноров. Тесно связана с теоремой Понтрягина — Куратовского.

Допустим, есть не планарный граф K5 — нет возможности нарисовать его на плоскости хотя бы без одного пересечения ребер. Если добавить вершину в середину только одного ребра, это не устранит пересечение, поэтому новый граф также не будет планарным. Именно поэтому запрещенным является любой подграф, гомеоморфный K5 или K3,3.

Формула Эйлера - если конечный связный граф из v вершин, e ребер и f граней можно представить на плоскости без пересечений ребер, то v − e + f = 2.

Теорема Фари - фактически каждый такой граф можно нарисовать так, чтобы все ребра были отрезками прямых линий.

Планарные графы можно разбить на более мелкие части, удалив O(√ n ) вершин, - помогает в разработке алгоритмов типа «разделяй и властвуй» и при динамическом программировании на планарных графах.

Совершенные графы

В совершенном графе его хроматическое число строго равно размеру полного подграфа. Это строгое равенство должно выполняться для всех его порожденных подграфов.

Хроматическое число графа - минимальное количество цветов для его правильной раскраски. Для графа, который содержит полный подграф размером k - хроматическое число должно быть не менее k.

Если граф совершенен, то и все его порожденные подграфы совершенны.

Сильная теорема о совершенных графах описывает их как графы без нечетных отверстий (порожденных бесхордовых циклов нечетной длины) или антиотверстий (дополнений этих циклов).

Слабая теорема описывает их как дополнения к совершенным графам (дополнение каждого совершенного графа само по себе совершенно). Она из доказательства сильной теоремы

Также в совершенном графе произведение размера наибольшей клики (полный подграф) и наибольшего независимого множества >= число вершин графа. Также верно для всех порожденных подграфов.

Задачи, которые решаются за полиномиальное время на совершенных графах:

1. Раскраска графа
2. определение максимальной клики
3. определение максимального независимого множества.

Подклассы совершенных графов:

1. Двудольные графы - хроматическое число равно 2.
2. Хордальные графы - нет хордовых циклов длиной больше 3.
3. Графы сравнимости - отражают частично упорядоченное множество
4. Подмножества этих классов, один из которых - интервальные классы.

Двудольные графы

Графы, для которых хроматическое число равно 2.

Как распознать двудольный граф:

1. Выбрать одну вершину графа из каждого связного компонента, присвоить ей первый цвет и добавить ее в очередь.
2. Далее рассматриваем ее соседей, удаляя вершину из очереди. Если какая то из соседних вершин не раскрашена, присваиваем ей противоположный цвет и добавляем в очередь.

Граф не двудольный если соседняя вершина уже раскрашена в такой же цвет, в противном случае - двудольный.

Применяются:

1. В сетях Петри
2. Другие задачи, включая задачу об устойчивом браке и задачу назначения

Интервальные графы

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

Две вершины смежные - соответствующие сегменты линии пересекаются.

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

Применение:

1. В генетическом анализе (субэлементы гена с высокой вероятностью связаны друг с другом, образуя линейную структуру)
2. Задачи выделения ресурсов. Интервал - запрос ресурса, раскраска графа - выделение ресурсов. Хроматическое число графа в этом случае - минимальное количество необходимого ресурса.

Графы дуг окружности

Являются надмножеством интервальных графов. Каждый интервальный граф также и граф пересечения дуг окружности, но не все графы пересечения дуг окружности - интервальные.

Можно изобразить в виде набора пересекающихся дуг окружности.
Две вершины смежные когда их дуги пересекаются.

Интервальное представление - разорвать круг в незамкнутой части и растянуть в линию.

Помимо интервальных графов, содержит в себе несовершенные классы - нечетные бесхордовые циклы.