Учебное пособие. — Казань: Изд-во Казанск. гос. архитект.-строит.
ун-та, 2013. — 87 с. — ISBN 978-5-7829-0407-4.
Учебное пособие предназначено для изучения теории графов дисциплины
«Дополнительные главы математики» студентами дневного отделения
направления подготовки 230400 «Информационные системы и
технологии».
История возникновения. Основные понятия и их пояснение на примере.
Первый способ аналитического задания графа в виде перечня
подмножеств вершин
Второй способ аналитического задания графа с помощью матрицы инцидентности. Понятия смежности и инцидентности. Принцип изоморфизма. Матрица смежности
Практическое занятие. Матрица инцидентности. Изоморфизм графов
Элементы графа. Лемма о рукопожатиях. Маршрут графа. Цепь. Цикл. Путь и контур. Связный граф. Полный граф. Турнир. Плоские и планарные графы. Задача о трёх домах и трёх колодцах. Задача о полном графе, имеющем 5 вершин. Теорема Куратовского. Формула Эйлера для многогранников
Практическое занятие. Элементы графов и орграфов: путь, длина, источники, стоки, степени вершин. Деревья. Эйлеров цикл. Плоские и планарные графы
Графы – деревья. Корень. Задача о соединении городов или построении “экономичного дерева”
Задача о кёнигсбергских мостах. Эйлеровы линия, граф и путь. Необходимые и достаточные условия существования эйлерового графа и пути
Практическое занятие. Эйлерова линия и эйлеров путь. Правило Тарри. Алгоритм Флёри. Построение “экономичного дерева”
Контрольная. Элементы графов. Изоморфизм. Построение циклов
Поиск кратчайшего пути между вершинами. Алгоритм Декстра
Практическое занятие. Поиск кратчайших путей между всеми вершинами с помощью алгоритма Декстра
Проблема коммивояжёра. Минимальный цикл Гамильтона. Эффективные и неэффективные алгоритмы
Алгоритм «самой близкой вставки»
Практическое занятие. Проблема коммивояжёра. Алгоритм «самой близкой вставки». Выдача заданий РГР1: “Поиск экономичных путей”
Список литературы
Второй способ аналитического задания графа с помощью матрицы инцидентности. Понятия смежности и инцидентности. Принцип изоморфизма. Матрица смежности
Практическое занятие. Матрица инцидентности. Изоморфизм графов
Элементы графа. Лемма о рукопожатиях. Маршрут графа. Цепь. Цикл. Путь и контур. Связный граф. Полный граф. Турнир. Плоские и планарные графы. Задача о трёх домах и трёх колодцах. Задача о полном графе, имеющем 5 вершин. Теорема Куратовского. Формула Эйлера для многогранников
Практическое занятие. Элементы графов и орграфов: путь, длина, источники, стоки, степени вершин. Деревья. Эйлеров цикл. Плоские и планарные графы
Графы – деревья. Корень. Задача о соединении городов или построении “экономичного дерева”
Задача о кёнигсбергских мостах. Эйлеровы линия, граф и путь. Необходимые и достаточные условия существования эйлерового графа и пути
Практическое занятие. Эйлерова линия и эйлеров путь. Правило Тарри. Алгоритм Флёри. Построение “экономичного дерева”
Контрольная. Элементы графов. Изоморфизм. Построение циклов
Поиск кратчайшего пути между вершинами. Алгоритм Декстра
Практическое занятие. Поиск кратчайших путей между всеми вершинами с помощью алгоритма Декстра
Проблема коммивояжёра. Минимальный цикл Гамильтона. Эффективные и неэффективные алгоритмы
Алгоритм «самой близкой вставки»
Практическое занятие. Проблема коммивояжёра. Алгоритм «самой близкой вставки». Выдача заданий РГР1: “Поиск экономичных путей”
Список литературы