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

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

6.6. Устойчивость графов

6.6.1. Внутренняя устойчивость

Внутренне-устойчивое множество вершин – множество вер-

шин графа, никакие две вершины которого не инцидентны. Пустой подграф – внутренне-устойчивое множество вершин,

такое, что: при добавлении к нему хотя бы одной вершины образуется хотя бы одно ребро.

Пустой подграф – максимальное по включению внутреннеустойчивое множество вершин. В данном определении «максимальность» означает «нерасширяемость»; в общем случае граф может иметь несколько пустых подграфов различной мощности.

Вершинное число независимости графа (или число внутрен-

ней устойчивости графа) – мощность наибольшего пустого подграфа, обозначение – ε0(G).

Независимое множество ребер (или паросочетание) – множе-

ство ребер графа, никакие два ребра которого не инцидентны.

Реберное число независимости (или число паросочетания) –

мощность наибольшего паросочетания (независимого множества ребер), обозначение – ε1(G).

В общем случае число вершинной внутренней устойчивости изменяется от n (у пустых графов на n вершинах) до 1 (у полных графов на n вершинах).

173

Для нахождения числа внутренней устойчивости надо определить мощность максимального пустого подграфа. Существует ал-

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

Пошаговое описание алгоритма:

1)строим фиктивную вершину, ее пометка – множество всех

вершин графа {v1, v2,…,vn} (или ребер – если ищется реберное число внутренней устойчивости, тогда далее во всем алгоритме вместо вершин говорим о ребрах);

2)выбираем любую вершину из указанного в пометке множества, рисуем ее на уровень ниже (это потомок);

3)рядом с ней на этом же уровне рисуем все смежные с ней вершины из множества, указанного в пометке вершины – родителя;

4)в качестве пометки каждой полученной вершины vi указываем множества вершин, входящих в ее неокрестность (т.е. несмежных с vi);

5)повтор шагов 2-4 для всех получающихся веток дерева до тех пор, пока все пометки не будут пустые.

Задача 6.8. Для заданного графа (рис. 6.27) найти все пустые подграфы и число вершинной внутренней устойчивости.

		1	Решение. В соответствии с ал-
			горитмом получим дерево (рис.
	2	3	6.28).
			В этом дереве все пути от фик-
		5	тивной вершины до каждого листа
	4		есть пустые подграфы или макси-
		6	мальные	внутренне	устойчивые
		7	множества (в данном случае –
		Рис. 6.27	вершины). Повторные пути указы-
			ваются	единократно.	Например,

пути 1-4-6, 1-6-4 и 4-1-6 задаются единственный раз множеством

{1,4,6}.

Выбираем из них самое длинное (с максимальной мощностью), это, например, {1,4,6}, его мощность равна 3. Значит, ε0=3.

Пустые подграфы: {2,6}, {2,7}, {1,5,7}, {1,4,6}, {3,2,7}, {3,4}. ε0=3.

174

{1,2,3,…,7}

{6,7}

2

{4,5,6,7}

1

{2,4,7}

3

{1,7}

5

{1,3,6}

4

6	7	5	4	6	2	4	1	1	3
		{7}	{6}	{4}	{7}		{7}	{6}
		7	6	4	7		7	6

Рис. 6.28

6.6.1. Внешняя устойчивость

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

Любая вершина покрывает:

саму себя;

смежные вершины;

инцидентные ребра. Любое ребро покрывает:

само себя;

смежные ребра;

инцидентные вершины.

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

Реберное число внешней устойчивости – минимальная мощ-

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

175

Основная идея алгоритма поиска минимального покрытия

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

Пошаговое описание алгоритма:

1)построить матрицу смежности и заполнить все клетки главной диагонали единичками;

2)составить логическое выражение в виде произведения сумм логических переменных, соответствующих вершинам графа (или ребрам – если ищется реберное число внешней устойчивости). Каждая сумма представляет собой сложение переменных, которые в данной строке содержат «1». Логическое сложение обозначается

как «+», логическое умножение – как « »;

3)привести это выражение к ДНФ (дизъюнктивной нормальной форме), т.е. к сумме произведений переменных;

4)мощность максимального слагаемого и есть искомое число внешней устойчивости.

Задача 6.9. Для заданного графа (рис. 6.29) с достаточным обоснованием найти число внешней вершинной устойчивости.

1

23

4

5

6

Рис. 6.29

Решение. Получим матрицу:

				1			2			3			4			5			6
	1			1			1			1
	2			1			1			1			1			1
	3			1			1			1						1			1
	4						1						1			1
	5						1			1			1			1			1
	6									1						1			1

176