Вопросы для самоконтроля

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

2. Приведите определение произвольного, покрывающего и кратчайшего покрывающего деревьев в графе.

3. Что в теории графов подразумевается под терминами “корень”, “ветвь”, “лес”?

4. Каким образом определяется число покрывающих деревьев в произвольном полном графе?

5. Сформулируйте задачу о лабиринте.

6. Приведите теорему для определения дерева.

7. Запишите теорему Кэли и следствие из нее.

8. Приведите теорему о каркасе минимального веса в графе.

9. В чем заключаются алгоритмы Краскала и Прима?

10. Приведите леммы о деревьях Штейнера.

Задания для самостоятельной работы

1. Постройте все покрывающие деревья для полного графа на 4 вершины.

2. Для произвольного взвешенного графа G = (X, U) постройте кратчайшее покрывающее дерево, используя алгоритм Краскала.

3. Для произвольного взвешенного графа G = (X, U) постройте кратчайшее покрывающее дерево, используя алгоритм Прима.

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

5. Постройте структурную схему алгоритма Краскала для построения кратчайшего покрывающего дерева в произвольном неориентированном взвешенном графе.

6. Постройте словесный алгоритм Краскала.

7. Постройте словесный алгоритм Прима.

8. Постройте структурную схему алгоритма Ханаана.

9. Записать структурную схему алгоритма Штейнера построения кратчайшего покрывающего дерева.

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

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

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

Д. Люкк

Глава 17. Графовые инварианты

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

Цели

Освоив эту главу, студенты должны:

• уметь определять цикломатическое число графа;

• уметь строить матрицу фундаментальных циклов;

• знать каким образом граф отображается в координатную решетку;

• уметь определять хроматическое число графа;

• уметь строить раскраску вершин графа;

• уметь определять число внутренней и внешней устойчивости;

• знать определения планарного и плоского графа;

• уметь определять планарность графа, исходя из приведенных критериев и эвристик;

• знать как определяется число пересечений графа;

• уметь определять минимальное число пересечений графа;

• уметь строить графы с минимальным числом пересечений.