5.1 Независимые множества и клики
5.1.1 Независимые множества и покрытия
5.1.1.1 Во многих прикладных задачах требуется найти в конечном множестве объектов максимальную систему объектов, попарно не связанных друг с другом, или же выбрать минимальную систему объектов, связанных со всеми другими. Формулировки подобных задач на языке теории графов приводят к понятиям независимости и покрытия.
Множество вершин графа называется независимым ( или внутреннеустойчивым), если никакие две вершины из этого множества не смежны. Иными словами, если SÍVG и S независимо в графе G, то порождённый подграф G(S) является пустым. Очевидно, что если при этом S'ÍS, то S' – также независимое множество.
Независимое множество называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества. Наибольшее по мощности независимое множество называется наибольшим.
Одна из чисто житейских интерпретаций понятия независимости состоит в следующем. Определённый человек желает устроить юбилей с максимальным числом гостей из своих знакомых. Стремясь сделать юбилейный вечер приятным, он должен организовать всё так, чтобы на этом вечере присутствовали люди, симпатизирующие друг другу. Так как отношение «симпатии» не является транзитивным, то ему для достижения цели придётся находить число независимости графа своих знакомых. Этот граф устроен следующим образом. Вершины его – знакомые юбиляра. Две вершины смежны, если соответствующие знакомые друг другу не симпатизируют. Нетрудно понять, что число независимости этого графа и представляет тот самый максимальный контингент приглашенных, который может себе позволить юбиляр.
К отысканию наибольшего независимого множества вершин в графе сводится, например, известная задача о восьми ферзях, которую связывают с именем К. Гаусса.
Задача о восьми ферзях: требуется так расставить на шахматной доске наибольшее число ферзей, чтобы они не атаковали друг друга. Таких ферзей, очевидно, может быть не более восьми, так как никакие два из них не должны находиться на одной вертикали или горизонтали. Одно из решений задачи о восьми ферзях показано на рисунке 5.1.
Число вершин в наибольшем независимом множестве графа G называется числомнезависимости (числомвнутреннейустойчивости, неплотностью или числомвершиннойупаковки) этого графа и обозначается через α0(G).
Например, для графа G, изображённого на рисунке 5.2, α0(G)=4, множества вершин {1, 2, 3, 7}, {1, 2, 3, 8}, {2, 3, 5, 7} и {2, 3, 5, 8} являются наибольшими независимыми, а {4, 7} – максимально независимое множество, не являющееся наибольшим.
 |
Содержанием большинства задач, связанных с понятием независимости, являются определение числа независимости и отыскание наибольшего независимого множества. Эти задачи, как правило, очень трудны, и потому для их решения оказываются полезными оценки числа независимости.
Теорема. Для любого графа G верно неравенство
,
причём равенство наблюдается, если граф G – полный (напомним, граф является полным, если любые две его вершины смежны).
Независимое множество вершин графа имеет естественную матричную интерпретацию. Пусть X={v1, v2,..., vk} – независимое множество вершин графа G, A=A(G) – матрица смежности. Множеству X в матрице А соответствует подматрица, элементы которой, расположенные в строках и столбцах (соответствующих элементам множества X), равны нулю.
5.1.1.2 С понятием независимости в графе связано понятие доминирования. Подмножество V' вершин графа G называется доминирующим (или внешнеустойчивым), если каждая вершина из VG\V' смежна с некоторой вершиной из V'. Иначе говоря, каждая вершина графа находится на расстоянии не более 1 от доминирующего множества. Доминирующее множество называется минимальным, если никакое его собственное подмножество не является доминирующим. Доминирующее множество, имеющее наименьшую мощность, называется наименьшим.
 |
Иллюстрацией к только что введённым понятиям может служить следующая занимательная задача о пяти ферзях: требуется расставить на шахматной доске наименьшее число ферзей так, чтобы каждая клетка доски была под боем. Очевидно, что всякой такой расстановке ферзей соответствует наименьшее доминирующее множество в графе, введённом выше в связи с задачей о восьми ферзях. Одно из решений задачи о пяти ферзях приведено на рисунке 5.3.
Подмножество вершин графа, являющееся как независимым, так и доминирующим, называется ядром.
Очевидно, что независимое множество является максимальным (не обязательно наибольшим) тогда и только тогда, когда оно доминирующее. Таким образом, ядра графа – это максимальные независимые множества вершин. С другой стороны, доминирующее множество не обязательно независимо. Например, множества вершин {1, 2, 3, 7}, (1, 2, 3, 8}, {2, 3, 5, 7}, {2, 3, 5, 8}, {4, 7} являются ядрами графа, изображённого на рисунке 5.2. Понятия доминирующего множества и ядра естественным образом переносятся и на случай ориентированных графов. Получаемые при этом результаты более интересны, чем в случае неориентированных графов.
Отыскание в графе наименьшего доминирующего множества является содержанием многих прикладных задач. Типичная ситуация, в которой возникает подобная задача, такова. Имеется множество населённых пунктов, связанных дорожной сетью. В некоторых из них надо расположить предприятия обслуживания так, чтобы расстояние от каждого из населённых пунктов до какого-либо из предприятий не превосходило заданной величины. Размещение следует выполнить так, чтобы обойтись минимальным количеством предприятий. Если поставить в соответствие населённым пунктам вершины графа, в котором две вершины смежны тогда и только тогда, когда расстояние между соответствующими пунктами не превышает заданной величины, то задача, очевидно, сводится к построению в графе наименьшего доминирующего множества.
5.1.1.3 Введём еще одно понятие, связанное с понятием независимости. Будем говорить, что вершинаиребрографапокрываютдругдруга, если они инцидентны. Таким образом, ребро е= uv покрывает вершины u и v, а каждая из этих вершин покрывает ребро е. Подмножество V'ÍVG называется покрытием (вершиннымпокрытием, опорой) графа G, если каждое ребро из EG инцидентно хотя бы одной вершине из V'. Другими словами, для всякого ребра {u, v} графа G хотя бы один из его концов u или v содержится в V′. Покрытие графа G называется минимальным, если оно не содержит покрытия с мéньшим числом вершин, и наименьшим, если число вершин в нём наименьшее среди всех покрытий графа G. Число вершин в наименьшем покрытии графа G называется числомпокрытия (или числомвершинногопокрытия) графа G и обозначается через β0(G).
Например, на рисунке 5.2 каждое из множеств Х1={4, 5, 6, 7}, Х2={4, 5, 6, 8}, Х3={1, 2, 3, 5, 6, 7}, Х4={1, 2, 3, 5, 6, 8} является покрытием, причем Х1 и Х2 – наименьшие покрытия, а X3 и X4 – минимальные покрытия.
Следующая теорема указывает на тесную связь между покрытиями и независимыми множествами графа.
Теорема. Множество U вершин графа G является (наименьшим, минимальным) покрытием тогда и только тогда, когда 
=VG\U – (наибольшее, максимальное) независимое множество. Следовательно,
.
Рёбернымпокрытием графа G называется такое подмножество рёбер Е'ÍEG, которое покрывает все вершины графа, т.е. такое, что каждая вершина в G инцидентна по крайней мере одному ребру из Е'. Из этого определения следует, что лишь графы с изолированными вершинами не имеют рёберных покрытий. Рёберное покрытие графа называетс я минимальным, если в нём не содержится покрытий с мéньшим числом рёбер, и наименъшим, если число рёбер в нём наименьшее среди всех покрытий. Число рёбер в наименьшем рёберном покрытии графа G называется числомрёберногопокрытия и обозначается через β1(G).
Очевидно, что β1(G)≥|G|/2. Например, в графе, изображенном на рисунке 5.4, множество из пяти рёбер {{1, 9}, {2, 8}, {3, 7}, {4, 5}, {5, 6}} является рёберным покрытием, а поскольку β1(G)≥9/2=4,5, то оно наименьшее.
 |
5.1.2 Клика
 |
Антиподом понятия независимого множества является понятие клики. Подмножество V' вершин графа G называется кликой, если любые две входящие в него вершины смежны, т. е. если порождённый подграф G(V') является полным. Иными словами, это множество вершин полного подграфа первоначального графа. Размер клики определяется как число вершин в ней. Клика называется максимальной, если она не содержится в клике с бóльшим числом вершин, и наибольшей, если число вершин в ней наибольшее среди всех клик. Число вершин в наибольшей клике графа G называется его плотностью (густотой или кликовымчислом) и обозначается через φ(G). Как и в случае независимых множеств, максимальная клика графа может оказаться не наибольшей, и это обстоятельство делает задачи нахождения числа φ(G) и наибольшей клики для произвольного графа G крайне трудными. Очевидно следующее утверждение. Подмножество вершин графа G является кликой тогда и только тогда, когда оно независимо в дополнительном графе
. Следовательно, φ(G)=α0(). На рисунке 5.5 приведен пример графа G с кликой размера 3.
Рисунок 5.5 – Граф G с кликой {1, 2, 5} размера 3
Кстати, граф на рисунке 5.5 имеет минимальное вершинное покрытие {1, 3, 5, 6} размером 4. Однако оно не является наименьшим вершинным покрытием, поскольку существуют вершинные покрытия меньшего размера, такие как {2, 4, 5} и {1, 2, 4}, т.е. β0(G)=3.
5.2 Задача о вершинном покрытии (отыскание наименьшего вершинного покрытия)
5.2.1 Определение числа β0(G) и, тем более, построение наименьшего вершинного покрытия для произвольного графа G – сложные алгоритмические задачи. Эффективных алгоритмов для их решения, видимо, не существует.
Задачаовершинномпокрытии состоит в нахождении вершинного покрытия минимального размера, т.е. в отыскании наименьшего вершинного покрытия размером β0(G) для заданного графа G. Рассмотрим практическую задачу, которая сводится к задаче о вершинном покрытии. Имеется некоторая сеть дорог, соединяющая города. В городах необходимо разместить ремонтные службы, каждая из которых будет обслуживать все дороги, ведущие в данный город. Необходимо разместить дорожные службы так, чтобы их количество было минимальным, но при этом обслуживанием были охвачены все дороги.
В качестве примера рассмотрим простой приближённый алгоритм решения задачи о вершинном покрытии, который решает её с ошибкой не более, чем в два раза:
APPROX-VERTEX_COVER (G)
1. С=ø
2. E ’= EG
3. while E `≠ ø do
4. берём произвольное ребро {u, v}ÎE ’
5. С=СU{u, v}
6. удалим из E ’ все покрытые рёбра, т.е. рёбра, инцидентные вершине u или v (см. подпункт 5.1.1.3)
7. end
8. return С
В рассматриваемом алгоритме приняты следующие обозначения: G – исходный неориентированный граф; Е’ – граф, содержащий все оставшиеся (не исключённые в процессе выполнения итераций цикла) рёбра; С – построенное в процессе алгоритма покрытие.
Для доказательства того, что этот алгоритм не более чем вдвое хуже точного, достаточно заметить, что никакие два ребра из выбираемых алгоритмом не имеют общих вершин, а значит число вершин в Cвдвое больше числа этих рёбер. Оптимальное же покрытие содержит хотя бы одну вершину каждого из них и все эти вершины разные.
Данный алгоритм нуждается в доработке на случай, если в графе Е’ на каком-либо шаге будет выбрано ребро, одна из вершин которого несмежна ни с одной из остальных вершин исходного графа G; в этом случае в покрытие С необходимо включать только ту вершину, которая смежна другим вершинам исходного графа.
Рассмотрим работу приведенного алгоритма пошагово (без оговоренной выше доработки) на примере графа на рисунке 5.6, а.
Выбираем ребро {b, c} и покрытые вершинами b и c рёбра {a, b}, {c, e} и {c, d} удаляем (рисунок 5.6, б). Множество С={b, c}.
Далее выбираем ребро {e, f} и покрытые вершинами e и f рёбра {e, d} и {d, f} удаляем (см. рисунок 5.6, в). Множество С={b, c, e, f}.
И, наконец, выбираем ребро {d, g} и получаем покрытие {b, c, d, e, f, g} (см. рисунок 5.6, г). Если же учесть требуемое дополнение, то покрытие будет меньшего размера: {b, c, d, e, f}.
Как мы видим, данное покрытие не является оптимальным (наименьшим), следовательно, алгоритм следует повторить, выбрав в качестве начального другое ребро. Наименьшим же покрытием является покрытие {b, d, e}.
5.2.2 Связь наименьшего покрытия с наибольшим независимым множеством даёт теорема Кёнига, имеющая отношение к теории бинарных матриц. Под линиейматрицы будем понимать её строку или столбец. Два элемента матрицы назовём независимыми, если они не лежат на одной линии.
Теорема Кёнига (D.Konig) (1931г.). Максимальное число попарно независимых единиц бинарной матрицы равно минимальному числу её линий, содержащих все единицы матрицы.
Проинтерпретируем теорему Кёнига на конкретном примере (рисунок 5.7) для нахождения наименьшего покрытия и наибольшего независимого множества вершин. Строим матрицу инцидентности B. Тогда наименьшее покрытие С составят вершины, соответствующие минимальной комбинации строк матрицы инцидентности, дизъюнкция которых даст единичную строку. Наибольшее же независимое множество (вершин) составит оставшееся множество вершин, не вошедшее в наименьшее покрытие, т.е. VG\C.
Матрица инцидентности графа на рисунке 5.7 имеет следующий вид:
.
Очевидно, что наименьшее покрытие составит множество вершин b, d, e, т.е. C={b, d, e} и β0(G)=3,так как единичную строку даст минимальная по количеству строк комбинация bv dv e. Тогда наибольшее независимое множество для данного графа будет VG\C={a, c, f, g} и α0(G)=4.
5.3 Задача о клике (отыскание наибольшей клики)
5.3.1 Задачаоклике впервые была сформулирована в 1972 году Ричардом Карпом. Задача о клике существует в двух вариантах: в задаче распознавания требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера.
Эффективного алгоритма для поиска клики заданного размера не существует. Полный перебор всех возможных подграфов размера k с проверкой того, является ли хотя бы один из них полным, – неэффективен, поскольку полное число таких подграфов в графе с v вершинами равно 
.
5.3.2 Алгоритм Брона-Кербоша (разработан голландскими математиками Броном и Кербошем в 1973г.) является одним из самых эффективных алгоритмов поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа. Начиная с одиночной вершины (образующей полный подграф с размером клики 1), алгоритм на каждом шаге пытается увеличить уже построенный полный подграф, добавляя в него вершины из множества кандидатов. Высокая скорость обеспечивается отсечением при переборе вариантов, которые заведомо не приведут к построению клики, для чего используется дополнительное множество, в которое помещаются вершины, которые уже были использованы для увеличения полного подграфа.
Алгоритм оперирует тремя множествами вершин графа:
– множество compsub – множество, содержащее на каждом шаге рекурсии полный подграф для данного шага. Строится рекурсивно;
– множество candidates – множество вершин, которые могут увеличить множество compsub;
– множество not – множество вершин, которые уже использовались для расширения compsub на предыдущих шагах алгоритма.
Алгоритм является рекурсивной процедурой, применяемой к этим трём множествам, и заключается в выполнении следующих действий, пока множество candidates не пусто и множество not не содержит вершины, соединённой со всеми вершинами из множества candidates:
а) выбираем вершину v из candidates и добавляем её в compsub;
б) формируем new_candidates и new_not, удаляя из candidates и not вершины, не соединённые с v;
в) если new_candidates и new_not пусты, то множество compsub – клика и переходим к пункту г, иначе переходим к пункту а;
г) удаляем вершину v из множеств compsub и candidates и помещаем её в множество not.
5.3.3 Рассмотрим два простых алгоритма, позволяющих найти клику в графе. В обоих случаях задана матрица смежности А размерности n×n графа G.
Первый алгоритм заключается в следующем: находим строку с наибольшим количеством нулей и вычёркиваем её вместе с соответствующим столбцом. Если полученная матрица не клика, то аналогичные действия проводим в ней и так далее до тех пор, пока не получим клику.
Второй алгоритм заключается в рекурсивном выполнении следующей процедуры.
Основная процедура clickue(A, n):
Если это клика размером n – выходим, выводя полученную клику (в этом случае все элементы матрицы смежности, за исключением нулевых диагональных, будут единичными), т.е. в клику войдут все вершины графа G.
Иначе выбираем произвольную вершину v и рассматриваем два случая:
а) клики, включающие эту вершину – из матрицы А удаляются m -строк и m -столбцов, соответствующих m -вершинам, несмежных с вершиной v, получая матрицу A' размерностью n-m. Далее выполняем основную процедуру над полученной матрицей, т.е. clickue(A', n-m);
б) клики, не включающие эту вершину – из матрицы А удаляются строка и столбец, соответствующие вершине v, получая матрицу A". Далее clickue(A", n-1).
Конец основной процедуры.
Варианты заданий
Задание №1
Найти все клики неориентированного графа G, представленного на рисунке 5.8 с матрицей смежности А.
Рисунок 5.8
Задание №2
Выбор переводчиков
Предположим, что организации нужно нанять переводчиков французского, немецкого, греческого, итальянского, испанского, русского и китайского языков на английский и что имеется пять кандидатур – А, В, С, D и Е. Каждая кандидатура владеет только некоторым собственным подмножеством из указанного выше множества языков и требует вполне определённую зарплату. Считаем, что требования на оплату труда у всех претендентов одинаковые, а группы языков, которыми они владеют (кроме, разумеется, английского, которым они владеют все), приведены в таблице 5.1. Необходимо решить, каких переводчиков (с указанных выше языков на английский) надо нанять, чтобы суммарные затраты на зарплату были наименьшими. Очевидно, что это задача о наименьшем (вершинном) покрытии.
Таблица 5.1
| Язык | Переводчик | ||||
| A | B | C | D | E | |
| Французский | |||||
| Немецкий | |||||
| Греческий | |||||
| Итальянский | |||||
| Испанский | |||||
| Русский | |||||
| Китайский |
Дать графическую интерпретацию данной задачи.