Внутренняя устойчивость графа

Подмножество вершин графа называется внутренне устойчивым, если они попарно несмежны между собой. Внутренне устойчивое множество вершин называетсяпустым подграфом, если при добавлении хотя бы одной вершины свойство внутренней устойчивости пропадает.

Пример

- не является внутренне устойчивым - является внутренне устойчивым (но не является пустым подграфом)- является внутренне устойчивым (и является пустым подграфом)

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

Пусть - некоторый граф,- некоторая вершина,- окрестность вершины. Неокрестность (коокрестность) вершиныграфаобозначим- подграф графа, порожденный.

ТеоремаПустой подграф, содержащий вершинусодержит по крайней мере одну вершину из коокрестности вершины.

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

Начальный шаг:строится вершина – корень дерева, которой сопоставляется граф.Итерационный шаг:на-ом ярусе есть вершина, которой сопоставлен граф. а) Извыбирается любая вершинаи выносится наярус. б) Наярус выносятся все вершины, которые входят в. в) Каждая из вершиняруса взвешивается соответствующим графом – коокрестностью от графа.Заключительный шаг:вершина дерева будет висячей, если соответствующий ей граф – пустой граф.Замечание В пункте а) желательно выбирать ту вершину, которая имеет минимальную степень.

Пример

Полные подграфы. Плотность графа

Пусть - некоторый граф. Максимальный по включению вершин подграф графа, любые две вершины которого смежны называетсяполным подграфом. Мощность максимального полного подграфа называетсяплотностью графа.

Алгоритм нахождения полных подграфов

Начальный шаг:строится вершина – корень дерева, которой сопоставляется граф.Итерационный шаг:на-ом ярусе есть вершина, которой сопоставлен граф. а) Извыбирается любая вершинаи выносится наярус. б) Наярус выносятся все вершины, которые входят в. в) Каждая из вершиняруса взвешивается соответствующим графом – окрестностью от графа.Заключительный шаг:вершина дерева будет висячей, если соответствующий ей граф – пустой граф.Замечание В пункте а) желательно выбирать ту вершину, которая имеет максимальную степень.

Задачу нахождения полных подграфов в можно свести к задаче нахождения пустых подграфов в.

Пример

Полные подграфы графа (или пустые подграфы графа):

Пример

:

Пример

:

:

Выделяем пустые подграфы:

Реберные графы. Графы со свойством реберности

Пусть - некоторый граф. Назовем графреберным графом , если носитель графасовпадает с множеством ребер графа, и две вершины всмежны, если соответствующие ребра смежны в .

Пример

(это преобразование можно выполнить всегда)

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

Пример

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

Замечание1. Не для любого графа существует такое разложение ребер. 2. В разложении ребер каждое ребро принадлежит ровно одному подграфу.

Пример

Пример

не являются реберными

Если граф обладает свойством реберности, то как найти его образ (т.е. граф, для которого данный является реберным)?

Пример

:

:

Пример

Укладки графа. Планарность

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

Пример

:	:
Гомеоморфны. Говорят, что они имеют одну и ту же топологию.

Пусть - некоторая поверхность.Род поверхности - это максимальное число простых замкнутых кривых, не разделяющих эту поверхность.

Род плоскости: 0
Род сферы: 0
Род тора: 1

Поверхности, которые имеют род 4:

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

Пример

Граф называетсяпланарным (плоским), если.

• печатные платы – планарные графы;

• микросхемы (на уровне технологии их изготовления) – планарные графы.

Критерий планарности графа (критерий Понтрягина-Куратовского)

Граф планарен тогда и только тогда, когда в нем отсутствуют подграфы, гомеоморфные или.

Алгоритм приведения графа к планарному

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

Раскраска графов

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

Хроматическое число пустого графа равно 1. Хроматическое число . Хроматическое число.

Алгоритм нахождения раскраски (хроматического числа)

1) Выделить все пустые подграфы графа. 2) Построить таблицу покрытий вершин графа пустыми подграфами. 3) Найти минимальное покрытие вершин графа пустыми подграфами (мощность минимального покрытия – это , а само покрытие определяет раскраску).

Пример

1 1 1 1 1 1 1 1 1 1 1

Оценки хроматического числа

1. Теорема Кенига Граф бихроматичен () тогда и только тогда, когда внет циклов нечетной длины.

2.Теорема , где- плотность графа.

3.Теорема , где- степень графа.

4.Оценка Бержа , где- число внешней устойчивости графа.

5.

Теорема , где,., где,., где,., где.

Примеры

а) Графы не имеют общих вершин. По теореме выше . б) Графы имеют по одной общей вершине. Отметим для нечетного цикла следующую раскраску: одна вершина в 3-й цвет, остальные в 1-й и 2-й цвета поочередно. На нашем графе вначале раскрасим в два цвета четный цикл (вместе с общей вершиной). Теперь рассмотрим нечетный цикл. В нем общая вершина оказалась закрашена каким-то цветом. Считаем этот цвет 3-им и закрашиваем все остальные вершины поочередно в два цвета (отличные от ранее выбранных, так как имеем граф суммы). Итого использовали четыре цвета.. в) Графы имеют по две общие, не смежные между собой вершины. Так как между двумя смежными вершинами в обоих графах будет располагаться цепь длиной, по крайней мере,, соединенная с аналогичной цепью в другой части графа всеми возможными связями, то. Для четырех цветов раскраска существует всегда: сначала раскрашиваем четный цикл в два цвета, затем оставшиеся цепи нечетного цикла закрашиваем в другие два цвета..

Алгоритм приближенной раскраски графа (алгоритм Ершова)

Алгоритм основан на стягивании несмежных вершин:

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

ЗамечаниеВ первую очередь желательно стягивать те вершины, расстояние между которыми четно.

Пример

Задача Есть 3 предприятия, на которых должны выпускаться 11 изделий. Каждый тип изделий должен выпускаться только на одном предприятии. При выпуске изделий разного типа () могут использоваться общие детали и материалы. Для каждой пары изделий указан процент общих деталей и материалов. Необходимо распределить изделия по предприятиям так, чтобы на одном предприятии выпускались детали с наибольшим процентом общих деталей.Критерий: Минимум общих поставок для изделий, выпускаемых на одном предприятии был как можно больше.

	55
	60	80
	85	65	40
	45	90	35	80
	80	75	30	90	90
	50	30	70	35	65	30
	50	60	90	40	35	70	30
	60	45	40	80	30	70	20	25
	45	40	45	35	80	20	90	25	85
	80	70	85	30	35	40	25	75	75	60

Граф несовместимости изделий

	Раскраска:
	Раскраска:
	Раскраска:
	Раскраска:

Решение - Iпредп. IIпредп. IIIпредп.

Перечисление графов

Группа. Группа подстановки

Группа– алгебра с одно бинарной операцией (), которая обладает следующими свойствами:

1) замкнутость и2) ассоциативность3) наличие нейтрального элемента4) существование обратного элемента для

Группа подстановки.Пусть. Подстановкой назовем.

Операция: произведение подстановок

Пример

Пример

Группа автоморфизмов графа

Пусть - некоторый граф.Автоморфизм графа - это изоморфизм на себя (с, сохраняющая отношение смежности между вершинами графа).

Пример

- не является автоморфизмом. - автоморфизм.

Группа автоморфизмов графа -, где- множество всех автоморфизмов графа,- операция произведения.

Пример

:

Пример

Пример

Задание

Задан автоморфизм. Определить все графы, которые допускают данный автоморфизм.

Операции над группами

Пусть даны группы автоморфизмов ,.- порядок группы,- порядок группы. Группадействует на множестве. Группадействует на множестве().- степень группы.- степень группы. Рассмотрим три операции над группами:

1. Сложение (объединение) групп – «».

2. Умножение групп – «».

3. Композиция групп – «».

Рассмотрение проведем на примере:

1. Сложение групп. действует наСтепеньравна, порядокравен.Пример

2. Произведение групп действует наСтепеньравна, порядокравен.Пример

3. Композиция групп Действует на.Степеньравна, порядокравен.

63

Document from www.cyberfac.ru