Задача о вершинном покрытии.

Определение 4.24. Множество вершин образует вершинное покрытие графа , если каждое ребро инцидентно хотя бы одной вершине из множества . Покрытие с минимальным числом вершин называется минимальным (оптимальным).

На рис. 4.5 множество вершин (3, 4) не образует покрытие, так как ни одно из ребер множества (1, 4) не инцидентно какой-либо из вершин множества (3, 4). Множество вершин (1, 3, 4) образует покрытие.

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

Тогда целевая функция имеет вид

,

условия инцидентности для всех ребер запишутся в виде

В задаче о взвешенном вершинном покрытии каждой вершине отнесен вес . В этом случае целевая функция имеет вид

,

ограничения – те же.

4.1.4. Задача об изоморфизме графов.

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

Рассмотрим простой пример (рис. 4.6). Способ перенумерации задается подстановкой

,

причем в первой строке указаны вершины графа , а во второй ‑ соответствующие им вершины графа , при этом соответствие ребер имеет вид

Рис. 4.6. Изоморфные графы.

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

, (4.2)

в которой вершине графа соответствует вершина графа таким образом, чтобы выполнялось соответствие ребер.

Сформулируем задачу об изоморфизме графов в терминах целочисленного программирования. Пусть и ‑ матрицы смежности графов и соответственно. Как известно [Kristof], для изоморфизма этих графов необходимо и достаточно существование такой невырожденной матрицы , имеющей одну единицу в каждой строке и каждом столбце, чтобы выполнялось условие

[7] (4.3)

Условие (4.3) перепишем в виде

, (4.4)

что равносильно следующим условиям:

.

Задача о поиске матрицы сводится к минимизации функции

при условиях

Если графы и изоморфны, то минимальное значение функции равно нулю и матрица определяется через подстановку (4.2) следующим образом:

а все остальные ее элементы равны нулю. В нашем примере , если вершина в графе имеет номер в графе :

Рассмотрим другие целевые функции в задаче об изоморфизме графов:

.

Эта целевая функция, в отличие от , не является дифференцируемой.

Обратим внимание на то, что каждая из сумм

может принимать лишь значения 0 или 1. Поэтому сумма может принимать значения 0, 1, -1.

Целевую функцию рассмотрим в виде

.

Очевидно, что может лишь принимать значения 0 или 1.

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

4.2. Экстремальные задачи на графовых структурах.