учебное пособие - теория графов

10.1.2.			7	8		6		4
		7		8		5	11
		8	8		6		3
	W		6			3 7 4
		6	5		3		8	7
			11	3	7	8
		4			4	7
10.1.3.			2		10	5
		2		7	6
			7			3	6
	W 10		6			2		1
		5		3	2
				6				5
					1		5
10.1.4.			6	5		8		10
		6		9	7	6
		5	9		8	9		11
	W		7 8			5 6
		8	6	9	5		7	9
					6	7
	10			11		9
10.1.5.			3		6			4
		3		1			2
			1		5	6		7
	W 6		5			1 3
				6	1		4	5
			2		3	4
		4		7		5

171

10.1.6.			5		6			9
		5		3		4	5	10
			3		1	2		7
	W 6			1		8		11
			4	2			6
			5		8	6		3
		9	10	7	11		3
10.1.7.			5	8			8
		5		7	10		8
		8	7		4	7	7
	W	10		4		6 9 4
				7	6		3	5
		8	8	7	9	3		6
					4	5	6
10.1.8.			5		10			2
		5		8	9		7
			8			2	3
	W 10 9					6		4
				2	6		6
			7	3		6		11
		2			4		11
10.1.9.			3			4		7
		1		2	6			5
					9	2
	W 3 10					3 1
				1	2			3
		2	7			8
			11	4		5

172

10.1.10.			6	16	11		3
		6		3		8	9
	16		3		1			2
	W 11		1		5		8
			8		5			13
		3	9		8			7
				2		13	7

Тема 11. Укладка графов на плоскости

Задание 11.1. С помощью алгоритма укладки графа на плоскости установить, является ли граф G планарным.

11.1.1.

11.1.2.

11.1.3.

173

11.1.4.

11.1.5.

11.1.6.

11.1.7.

11.1.8.

11.1.9.

11.1.10.

174

Примерный перечень вопросов к зачету по учебной дисциплине

«Теория конечных графов и ее приложения»

для студентов направления

«Фундаментальная информатика и информационные технологии»

1.Основные понятия теории графов: граф, мультиграф, отображение инцидентности, вершины и ребра графа и их виды, порядок графа. Граф как алгебраическая система.

2.Виды графов (конечные и бесконечные графы, граф n-го порядка, ориентированные и неориентированные графы, псевдограф, тривиальный граф, простой граф, пустой граф, полный граф). Части и подграфы графа.

3.Способы задания графов (аналитический, геометрический, матричный, с помощью списка дуг, структурой смежности). Представление графов в памяти ЭВМ. Матрицы смежности и инцидентности, матрица Кирхгофа.

4.Степень (валентность) вершины графа. Изолированные и концевые (висячие) вершины.

5.Регулярный (однородный) граф. Регулярность полного графа.

6.Двудольные и полные двудольные графы. Свойства регулярных двудольных графов. Звездный граф. k-дольные графы.

7.Полустепень исхода из вершины (захода в вершину). Теорема Эйлера о рукопожатиях. Степень графа.

8.Бинарные операции над графами: пересечение, объединение, кольцевая сумма, соединение, произведение, композиция.

9.Унарные операции над графами: удаление и добавление вершин и ребер, введение вершины в ребро, отождествление вершин, расщепление вершины, дополнение графа. Определение n-мерного куба.

175

10.Гомоморфизм, изоморфизм и гомеоморфизм графов. Простейшие свойства изоморфных графов.

11.Установление изоморфизма графов с помощью матрицы смежности. Изоморфизм мультиграфов.

12.Маршруты графов и их виды (пути, контуры, цепи, циклические маршруты, циклы). Обходы графов.

13.Нахождение в графах маршрутов с заданным количеством ребер (с помощью матрицы маршрутов длины k.

14.Отношение достижимости на множестве вершин графа и его свойства. Матрицы достижимости и контрдостижимости.

15.Связные неорграфы, связные и сильно связные орграфы. Полностью несвязный (пустой) граф. Связная (сильно связная) компонента графа. Матрица сильных компонент графа.

16.Критерий связности графа.

17.Теоремы о разложении графа на связные компоненты.

18.Оценка числа ребер графа через число вершин и число связных компонент графа.

19.Эйлеровы цепи, циклы, графы. Критерий эйлеровости графа.

20.Гамильтоновы цепи, графы. Признаки гамильтоновости графа (теорема Дирака, теорема Оре, Хватала).

21.Вершинно-непересекающиеся и реберно-непересекающиеся цепи. Теорема Менгера о разделяющем множестве вершин.

22.Метрические характеристики связных графов: расстояние между вершинами графа, эксцентриситет вершины, радиус и диаметр графа, центральные и периферийные вершины, матрица расстояний графа.

23.Взвешенные связные неорграфы и их метрические характеристики: взвешенное расстояние между вершинами, матрица весов, взвешенный эксцентриситет вершины, взвешенные радиус и диаметр графа.

24.Взвешенные орграфы (сети). Определение сети Петри.

25.Потоки в сетях: понятие источника, стока; пропускная способность дуги, поток, условие сохранения потока, остаточная пропускная спо-

176

собность дуги, пропускная способность (величина) разреза. Теорема Форда-Фалкерсона о величине максимального потока в сети.

26.Определение неориентированного дерева, леса. Простейшие свойства деревьев.

27.Характеризационная теорема для деревьев. Теорема Кэли о числе деревьев n-го порядка.

28.Понятие ориентированного дерева. Упорядоченные деревья. Понятие бинарного дерева.

29.Остовы (каркасы) графа. Циклический и коциклический ранги графа. Матричная теорема Кирхгофа о числе остовных деревьев связного графа.

30.Фундаментальные циклы графа, матрица фундаментальных циклов.

31.Разрезающие (разделяющие) множества и разрезы графов. Фундаментальные разрезы, матрица фундаментальных разрезов.

32.Независимое (внутренне устойчивое) множество вершин графа. Доминирующее (внешне устойчивое) множество вершин. Полностью зависимое множество.

33.Покрывающие множества вершин и ребер. Числа вершинного и реберного покрытия. Связь чисел независимости и покрытий.

34.Определение клики графа. Максимальная и наибольшая клики графа. Кликовое число (плотность) графа и его свойства. Алгоритм выделения клик в графе.

35.Независимое множество ребер (паросочетание). Максимальное, полное, совершенное паросочетания. Теорема Холла о паросочетаниях в двудольном графе.

36.Плоские и планарные графы. Понятие укладки графа на плоскости, на

поверхности, в пространстве. Непланарность графов K5 и K3,3. Признаки планарности графа.

37.Грани плоского графа. Теорема Эйлера о гранях плоского графа и ее следствия.

38.Число планарности (искаженность) графа и его оценка. Толщина непланарного графа и ее оценка.

177

39.Понятие вершинной и реберной раскраски графа. Правильная раскраска. Хроматическое число графа. Оценки для хроматического числа. Хроматический многочлен графа и его свойства.

40.Теорема Кенига о бихроматическом графе. Теорема о пяти красках. Гипотеза четырех красок.

178

Литература

1.Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов. – М.: Издательский отдел ф-та ВМиК МГУ им. М. В. Ломоно-

сова, 2000.

2.Андерсон Д.А. Дискретная математика и комбинаторика. – М. – СПб. – Киев: Вильямс, 2004.

3.Берж К. Теория графов и ее применения. М., ИЛ, 1962.

4.Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: Наука, 1992.

5.Галушкина Ю.И., Марьямов А.Н. Конспект лекций по дискретной математике. – М.: Айрис Пресс, 2008.

6.Данилов В.Г., Дубнов В.Л., Лакерник А.Р., Райцин А.М. Дискретная математика. – М.: Горячая линия – Телеком, 2008.

7.Дистель Р. Теория графов. – Новосибирск: Изд-во Ин-та математики,

2002.

8.Ерусалимский Я.М. Дискретная математика. – М.: Вузовская книга,

2001.

9.Зыков А.А. Теория конечных графов, I. Новосибирск, Наука, 1969.

10.Иванов Б.Н. Дискретная математика. Алгоритмы и программы. – М.: Лаборатория Базовых Знаний, 2003.

11.Капитонова Ю.В., Кривой С.Л., Летичевский А.А., Луцкий Г.М. Лекции по дискретной математике. – СПб.: БВХ-Петербург, 2004.

12.Кристофидес К. Теория графов (алгоритмический подход). М., Мир,

1978.

13.Кузнецов О.П. Дискретная математика для инженера. – М. - СПб. - Краснодар: Лань, 2009.

14.Куликов В.В. Дискретная математика. – М.: РИОР, 2010.

15.Новиков Ф.А. Дискретная математика для программистов. – СПб:

Питер, 2000.

16.Оре О. Теория графов. – М.: URSS, 2009 (М., Наука, 1968).

17.Пономарев В.Ф. Дискретная математика для инженеров. – М.: Горячая линия – Телеком, 2009.

18.Редькин Н.П. Дискретная математика. – М.: Физматлит, 2009.

179

19.Спирина М.С., Спирин П.А. Дискретная математика. – М.: Акаде-

мия, 2009.

20.Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. – Москва – Новосибирск, 2002.

21.Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БВХ-Петербург, 2008.

22.Харари Ф. Теория графов. – М.: URSS, 2009 (М., Мир, 1973).

23.Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. – СПб.: БВХ-Петербург, 2007.

24.Яблонский С.В. Введение в дискретную математику. – М.: Наука,

2002.

180