- •Часть 1. Курс лекций
- •Введение.
- •Цели освоения дисциплины
- •Место дисциплины в структуре ооп впо
- •Компетенции обучающегося, формируемые в результате освоения дисциплины (модуля)
- •Тема 1. Алгоритмы на графах (6 часов).
- •Лекция 1. Начальные понятия теории графов.
- •Определение графа
- •Графы и бинарные отношения
- •Откуда берутся графы
- •Число графов
- •Смежность, инцидентность, степени
- •Некоторые специальные графы
- •Графы и матрицы
- •Взвешенные графы
- •Изоморфизм
- •Инварианты
- •Операции над графами
- •Локальные операции
- •Подграфы
- •Алгебраические операции
- •Лекция 2. Поиск в глубину и ширину. Поиск в ширину
- •Процедура поиска в ширину
- •Процедура поиска в глубину
- •Глубинная нумерация
- •Построение каркаса
- •Шарниры
- •Маршруты, пути, циклы
- •Связность и компоненты
- •Метрические характеристики графов
- •Маршруты и связность в орграфах
- •Эйлеровы пути и циклы
- •Построение эйлерова цикла
- •Гамильтоновы пути и циклы
- •Тема 2. Алгоритмы комбинаторного перебора (6 часов).
- •Размещения с повторениями
- •Перестановки
- •Подмножества
- •Разбиения
- •Лекция 5. Коды Грея. Коды Грея и аналогичные задачи
- •Лекция 6. Применение методов комбинаторного перебора.
- •Подсчет количеств
- •Тема 3. Общие методы разработки алгоритмов (6 часов).
- •Ферзи, не бьющие друг друга: обход дерева позиций
- •Лекция 8. Рекурсия. Примеры рекурсивных программ
- •Рекурсивная обработка деревьев
- •Лекция 9. Построение итеративных алгоритмов по рекурсивным.
- •Стек отложенных заданий
- •Более сложные случаи рекурсии
- •Библиографический список
- •Содержание
- •Тема 1. Алгоритмы на графах. 6
- •Тема 2. Алгоритмы комбинаторного перебора. 48
- •Тема 3. Общие методы разработки алгоритмов. 66
- •Шутов Антон Владимирович Медведев Юрий Алексеевич
- •600014, Г. Владимир, ул. Университетская, 2, тел. 33-87-40
Метрические характеристики графов
Расстоянием между двумя вершинами графа называется наименьшая длина пути, соединяющего эти вершины. Расстояние между вершинами и обозначается через . Если в графе нет пути, соединяющего и , то есть эти вершины принадлежат разным компонентам связности, то расстояние между ними считается бесконечным.
Функция обладает следующими свойствами:
, причем тогда и только тогда, когда ;
;
(неравенство треугольника).
В математике функцию двух переменных, определенную на некотором множестве и удовлетворяющую условиям 1 - 3, называют метрикой, а множество, на котором задана метрика, - метрическим пространством. Таким образом, множество вершин любого графа можно рассматривать как метрическое пространство.
Расстояние от данной вершины до наиболее удаленной от нее вершины называется эксцентриситетом вершины и обозначается через . Таким образом,
Вершину с наименьшим эксцентриситетом называют центральной, а вершину с наибольшим эксцентриситетом - периферийной. Множество всех центральных вершин называется центром графа. Сама величина наименьшего эксцентриситета называется радиусом графа и обозначается через , а величина наибольшего - диаметром и обозначается . Иначе говоря,
Наименьший диаметр имеет полный граф - его диаметр равен 1. Среди связных графов с вершинами наибольший диаметр, равный , имеет цепь .
Если расстояние между двумя вершинами равно диаметру графа, то кратчайший путь, соединяющий эти вершины, называется диаметральным путем, а подграф, образованный вершинами и ребрами этого пути, - диаметральной цепью.
Для графа, изображенного на рис. 3.3, эксцентриситеты вершин приведены в следующей таблице:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Центр этого графа составляют вершины , , ; периферийные вершины - , и ; радиус его равен , а диаметр . Одна из диаметральных цепей порождается множеством вершин .
Рис. 3.3.
Маршруты и связность в орграфах
Для ориентированного графа можно определить два типа маршрутов. Неориентированный маршрут (или просто маршрут) - это чередующаяся последовательность вершин и ребер графа, такая, что для каждого выполняется одно из двух: или . Маршрут называется ориентированным (или ормаршрутом), если для каждого . Таким образом, при движении вдоль маршрута в орграфе ребра могут проходиться как в направлении ориентации, так и в обратном направлении, а при движении вдоль ормаршрута - только в направлении ориентации. Это различие очевидным образом распространяется на пути и циклы, так что в орграфе можно рассматривать пути и орпути, циклы и орциклы. Будем говорить, что маршрут соединяет вершины и , а ормаршрут ведет из в .
Соответственно двум типам маршрутов определяются и два типа связности орграфов. Орграф называется связным (или слабо связным), если для каждой пары вершин в нем имеется соединяющий их маршрут; он называется сильно связным, если для каждой упорядоченной пары вершин ( ) в нем имеется ормаршрут, ведущий из в . Максимальные по включению подмножества вершин орграфа, порождающие сильно связные подграфы, называются его областями сильной связности, а порождаемые ими подграфы - компонентами сильной связности. Очевидно, разные области сильной связности не могут иметь общих вершин, так что множество вершин каждого орграфа разбивается на области сильной связности. Областями сильной связности орграфа на рис. 3.4 являются множества , , .
Рис. 3.4.