- •16. Типы конечных графов
- •Типы конечных графов
- •Матрицы смежности и инцидентности
- •Изоморфизм графов общего вида
- •Признаки непланарных графов
- •Алгоритм поиска в глубину
- •Реализация
- •Способы построения матрицы достижимости [править]Перемножение матриц
- •[Править]Случай нескольких путей
- •Каркас неориентированного графа
- •Формулировка
- •[Править]Оценка
- •Обозначения
- •[Править]Псевдокод
- •[Править]Описание
- •[Править]Доказательство корректности
- •Неформальное описание
- •[Править]Формальное описание
- •Основные определения
- •Классификация автоматов по логическим свойствам функций переходов и выходов
- •[Править]Автомат Мили
- •[Править]Автомат Мура
- •Форма компактного представления, применяемая во время выполнения
- •Реализация компактного представления
- •Анализ конечных автоматов.
- •Описание
- •Алгоритм симплекс-метода [править]Усиленная постановка задачи
- •[Править]Алгоритм
- •Модели вычислений
- •Описание
- •Устройство машины Тьюринга
- •[Править]Описание машины Тьюринга
- •Условия применимости
- •[Править]Принцип жадного выбора
- •[Править]Оптимальность для подзадач
Изоморфизм графов общего вида
Графы и являются изоморфными, если путем перестановки строк и столбцов матрицы смежности графа удается получить матрицу смежности графа . Однако перебор всех возможных перестановок характеризуется вычислительной сложностью (при условии, что сравнение матриц смежности производится за время, не зависящее от , что обычно несправедливо и дополнительно увеличивает приведенную оценку), что существенно ограничивает применение подобного подхода на практике. Существуют методы ограниченного перебора возможных пар предположительно-изоморфных вершин (аналог метода ветвей и границ), однако они незначительно улучшают приведенную выше асимптотику.
Инварианты
Основная статья: Инвариант графа
Существует набор числовых характеристик графов, называемых инвариантами, которые совпадают у изоморфных графов (совпадение инвариантов является необходимым, но не достаточным условием наличия изоморфизма)[5]. К ним относятся число вершин и число дуг/ребер графа G, упорядоченный по возрастанию или убыванию вектор степеней вершин , упорядоченный по возрастанию или убыванию вектор собственных чисел матрицы смежности графа (спектр графа), хроматическое число и др. Факт совпадения инвариантов обычно не несет информации о подстановке изоморфизма.
Инвариант называется полным, если совпадения инвариантов графов необходимо и достаточно для установления изоморфизма. Например, каждое из значений и (мини- и макси-код матрицы смежности) является полным инвариантом для графа с фиксированным числом вершин .
Различные инварианты имеют различную трудоемкость вычисления. В настоящее время полный инвариант графа, вычислимый за полиномиальное время, неизвестен, однако не доказано, что он не существует. Попытки его отыскания неоднократно предпринимались в 60-х — 80-х годах XX века, однако не увенчались успехом.
Модульное произведение Визинга
Модульное произведение графов , предложенное В. Г. Визингом (англ.), позволяет свести задачу проверки изоморфизма к задаче определения плотности графа , содержащего вершин. Если , , то граф содержит подграф, изоморфный графу .
Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.
Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его вершины — это точки плоскости, а ребра — линии на ней. Области, на которые граф разбивает поверхность, называются гранями. Плоский граф — граф, уложенный на плоскость. Граф называется планарным, если он изоморфен некоторому плоскому графу.
Полный граф с пятью вершинами
Лемма. Полный граф с пятью вершинами (К5) нельзя уложить на плоскость
K5, полный граф с 5 вершинами
«Домики и колодцы»
Граф «домики и колодцы» (K3,3)
Задача о трёх колодцах. Есть три дома и три колодца. Можно ли так проложить дорожки между домами и колодцами, чтобы от каждого дома к каждому колодцу вела дорожка, и никакие две дорожки не пересекались бы. Мосты строить нельзя.
Лемма. Полный двудольный граф с тремя вершинами в каждой из долей (К3,3) нельзя уложить на плоскость.