Лекции. Теория графов и комбинаторика (стр. 4 )

3. 

4.  Если , то повторяем пункт 2.

Теорема 1.

Число операций для осуществления этого алгоритма – построения минимального остова графа из n вершин .

43

Пример.

ФУНДАМЕНТАЛЬНЫЕ ЦИКЛЫ И РАЗРЕЗЫ.

Пример.

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

Размерность пространства циклов – цикломатическое число .

Алгоритм построения фундаментальных циклов:

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

2.  Последовательно присоединять по одной хорде (при этом образуется один цикл).

3.  Если написать фундаментальную матрицу циклов , то строки матрицы будут линейно не зависимыми.

Пример.

Хорды 1, 2, 3, 4.

Утверждение 1.

Если граф связен и имеет , то его цикломатическое число .

4Остов имеет число (n – 1) рёбер. Т. о. остовные рёбра минус хорды равно числу фундаментальных циклов равно числу хорд, т. е. .3

Утверждение 2.

Если граф имеет k компонент связанности, то .

Определение 1.

Разрезом в связном графе называется множество рёбер, удаление которого делает граф несвязным.

Пример.

Разрезы графа образуют линейное пространство над полем из двух элементов .

Размерность пространства циклов – коцикломатическое число .

Алгоритм построения фундаментальных разрезов.

1.  Взять остов Т, занумеровав сначала хорды, затем рёбра остова.

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

3.  Если написать матрицу фундаментального разреза , то число фундаментальных разрезов равно числу остовов

Лекция № 5.

НЕЗАВИСИМЫЕ И ДОМИНИРУЮЩИЕ

МНОЖЕСТВА ВЕРШИН.

Определение 1.

Подмножество вершин называется независимым (внутренне устойчивым), если оно не содержит смежных вершин.

Определение 2.

Независимое множество А называется максимальным, если оно не содержится ни в одном другом независимом множестве.

Определение 3.

Независимое множество А называется наибольшим, если оно имеет наибольшее число вершин среди всех независимых множеств.

Теорема 1.

Независимое множество А наибольшее Множество А максимально

Пример.

– независимое, не максимальное

– независимое, максимальное, не наибольшее

– независимое, максимальное, наибольшее

Определение 4.

– число внутренней устойчивости графа, т. е. число вершин в наибольшем независимом множестве.

Алгоритм построения всех максимальных независимых множеств:

1.  Введём логическую переменную

2.  Запишем формулу , выражающую независимость множества:

3.  По законам булевой алгебры привести выражение к виду ДНФ, т. е. и применить все возможные законы поглощения.

4.  Каждому произведению соответствует максимальное независимое множество, состоящее из тех вершин, номера которых НЕ входят в произведение.

Пример.

– все максимальные независимые множества.

Определение 5.

Клика графа – полный подграф . Клики графа соответствуют максимальным независимым множествам дополнения графа.

Определение 6.

Подмножество вершин называется доминирующим (внешне устойчивым), если .

Определение 7.

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

Определение 8.

Доминирующее множество В называется наименьшим, если оно имеет наименьшее число вершин среди всех доминирующих множеств.

Теорема 2.

Доминирующее множество В наименьшее Множество В минимальное

Пример.

– доминирующее, минимальное

– доминирующее, минимальное, наименьшее

– доминирующее, не минимальное

Определение 9.

– число внешней устойчивости графа, т. е. число вершин в наименьшем доминирующем множестве.

Алгоритм построения всех минимальных доминирующих множеств:

1.  Введём логическую переменную

2.  Запишем формулу , выражающую доминирование множества:

3.  По законам булевой алгебры привести выражение к виду ДНФ, т. е. и применить все возможные законы поглощения.

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

Пример.

– все минимальные доминирующие множества.