- •Составители: н.И. Житникова, г.И. Федорова, а.К. Галимов
- •Введение
- •1. Краткий перечень основных понятий теории графов
- •1.1. Общие понятия
- •1.2. Понятия смежности, инцидентности, степени
- •1.3. Маршруты и пути
- •1.4. Матрицы смежности и инцидентности
- •1.5. Связность. Компоненты связности
- •1.6. Матрицы достижимости и связности
- •1.7. Расстояния в графе
- •1.8. Образ и прообраз вершины и множества вершин
- •1.9. Нагруженные графы
- •1.10. Деревья и циклы
- •2. Решение контрольных задач
- •2.1. Компоненты сильной связности ориентированного графа
- •Алгоритм выделения компонент сильной связности
- •2.2. Расстояния в ориентированном графе
- •Алгоритм поиска минимального пути из вв ориентированном графе
- •2.3. Минимальный путь в нагруженном ориентированном графе
- •Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном ориентированном графе d из vнач в vкон.( vнач ≠ vкон)
- •2.4. Эйлеровы циклы и цепи
- •Алгоритм выделения эйлерова цикла в связном мультиграфе с четными степенями вершин
- •2.5. Минимальное остовное дерево
- •Алгоритм выделения минимального остовного дерева в неориентированном нагруженном графе g
- •2.6. Задача о коммивояжёре
- •3. Задания для самостоятельного решения
3. Задания для самостоятельного решения
1. С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D.
а) |
б) |
в) |
2. С помощью алгоритма фронта волны найти расстояния в ориентированном графе D: диаметр, радиус и центры.
а) |
б) |
в) |
Примечание: самый длинный путь в графе найти при помощи алгоритма фронта волны.
3. Найти минимальный путь в нагруженном графе по методу Форда-Беллмана.
|
|
|
а) из вершины в вершину |
б) из вершины в вершину |
в) из вершины в вершину |
4. Найти Эйлерову цепь в неориентированном графе.
а) |
б) |
в) |
5. Найти минимальное остовное дерево в неориентированном нагруженном графе.
а) |
б) |
в) |
6. Методом ветвей и границ найти оптимальный путь коммивояжёра при следующей матрице стоимости.
Ответ: 1 5 3 4 6 2 1, расстояние равно 15 |
Ответ: 1 26 5 4 3 1, расстояние равно 36 |
Ответ: 1 3 2 4 6 5 1, расстояние равно 11 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
а) |
б) |
в) |
СПИСОК ЛИТЕРАТУРЫ
1. Акимов О.Е. Дискретная математика: логика, группы, графы. М.: Лаборатория базовых знаний, 2003. - 352 с.
2. Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2001. – 304 с.
3. Романовский И.В. Дискретный анализ: Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. – 3-е изд., перераб. и доп. – СПб.: Невский Диалект, БХВ-Петербург, 2003. –320с.
4. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.- 384с.
5. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2001. - 304с.
6. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. М.: Наука, 1992. – 408 с.
7. Бронштейн Е.М., Хазанкин В.Г. Методические указания для самостоятельной работы по основам теории графов./ Уфа, 1989. - 24 с.
8. Хабиров С.В., Дворяшина Т.П. Упражнения и задачи по основам теории графов: Методические указания / Уфимск. гос. авиац. техн. ун-т. Уфа, 1994. - 36с.