- •Основы теории графов
- •Введение
- •Глава 1. Способы задания графов. Операции над графами. Метрические характеристики графов. Упорядочивание элементов орграфов
- •1. Способы задания графов. Операции над графами. Метрические характеристики графов
- •Основные понятия и определения
- •1.2. Операции над графами
- •1.3. Маршруты, цепи, циклы
- •. Способы задания графов
- •1.5. Метрические характеристики графа.
- •1.6. Упорядочивание дуг и вершин орграфа
- •1.8. Определение экстремальных путей на графах.
- •1.9. Порядковая функция орграфа без контуров.
- •Вопросы для повторения.
- •Глава 2. Нахождение минимальных и максимальных путей на орграфах
- •1. Нахождение кратчайших путей. Алгоритм Дейкстры
- •2. Нахождение кратчайших путей. Алгоритм Беллмана-Мура
- •Алгоритм нахождения максимального пути
- •4. Особенности алгоритмов теории графов
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Глава 3. Остовы графов, фундаментальные циклы. Эйлеровы и гамильтоновы графы. Доминирующие множества и клики
- •1. Деревья (основные определения)
- •2. Задача об остове экстремального веса
- •3. Обходы графов. Фундаментальные циклы
- •4. Клики, независимые множества
- •Вопросы для повторения.
- •Глава 4. Планарные графы
- •1. Планарность графов
- •2. Алгоритм укладки графа на плоскости
- •Вопросы для повторения.
- •Глава 5. Потоки в сетях
- •1. Потоки в сетях
- •Теорема Форда-Фалкерсона
- •Случайные графы
- •Заключение
- •Библиографический список
- •Оглавление
- •Основы теории графов
- •394026 Воронеж, Московский просп., 14
Задачи для самостоятельного решения.
По заданной матрице весов графа G найти величину минимального пути и сам путь от вершины s = x1 до вершины
t = x6 по алгоритму Дейкстры.
Для графа G из задачи 1 найти величину максимального пути и сам путь между теми же вершинами.
По заданной матрице весов графа G найти минимальный путь по алгоритму Беллмана-Мура между вершиной s = x1 и конечной вершиной t = x6.
Глава 3. Остовы графов, фундаментальные циклы. Эйлеровы и гамильтоновы графы. Доминирующие множества и клики
1. Деревья (основные определения)
Деревом называется связной граф, не содержащий циклов.
Любой граф без циклов называется лесом. Таким образом, деревья являются компонентами леса.
Теорема о дереве.
Пусть G = (S,U) и Card S = n, Card U = m. Тогда справедлива эквивалентность следующих утверждений.
G – дерево.
G – связной граф и m = n – 1.
G – ациклический граф и m = n – 1.
Любые две несовпадающие вершины графа соединяет единственная простая цепь.
G – ациклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.
Рис. 38
Ориентированный граф называется ориентированным деревом (ордеревом), если:
существует ровно одна вершина , называемая корнем, которая не имеет предшествующих вершин, т.е. ;
любой вершине в графе G непосредственно предшествует ровно одна вершина, т.е. .
Неориентированное дерево можно превратить в ориентированное, выбрав в качестве корня произвольную вершину.
Рис. 39
Корень графа G – вершина х6.
Подграф графа называется остовным подграфом, если
Подграф графа G называется остовным поддеревом, если и G – дерево.
Теорема Кэли.
Число различных деревьев, которые можно построить на n различных вершинах равно .
Теорема Кирхгофа.
Число остовных деревьев в связном графе G порядка равно алгебраическому дополнению любого элемента матрицы Кирхгофа В(G).
Пример.
Рис. 40
Найдём число всех остовов графа G по теореме Кирхгофа.
Матрица Кирхгофа
Таким образом, у этого графа существует 11 различных остовов.
Рис. 41
Число где m – число рёбер, n – число вершин, к – число компонент связности. Связного графа называется циклическим числом или циклическим рангом графа G, число - коциклическим рангом или корангом.
равно числу рёбер, входящих в любой остов графа G.
Теорема. Число рёбер произвольного связного неориентированного графа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно циклическому рангу графа G.
Следствие 1. Неориентированный граф является лесом тогда и только тогда, когда .
Следствие 2. Неориентированный граф имеет единственный цикл тогда и только тогда, когда .