- •Основы теории графов
- •Введение
- •Глава 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
Вопросы для повторения.
Плоский граф.
Планарный граф и его свойства.
Грань. Граница грани. Внешняя и внутренние грани
Теорема Эйлера.
Гомеоморфные графы.
Теорема Понтрягина-Куратовского.
Эквивалентная форма критерия планарности
Число планарности (искажённость) графа..
Толщина графа. Теорема о толщине связного графа
Сегмент.
Контактная вершина. Допустимая грань. цепи
Конфликтующие сегменты.
Алгоритм укладки планарного графа на плоскость.
Задачи для самостоятельного решения.
Является ли граф, изображённый на рис. 67, планарным?
Рис. 67
2. При каких n граф порядка 2n изображённый на рис. 68, является планарным?
…
…
Рис. 68
3. С помощью алгоритма укладки графа на плоскость постро
ить плоскую укладку или установить непланарность графа,
x222
x3
x4
x1
x5
x6
Рис. 69
4. Найти число планарности и толщину графов: а) К5; б) К3,3;
в) графа Петерсена.
Глава 5. Потоки в сетях
1. Потоки в сетях
Функциональное назначение большинства физически реализованных сетей состоит в том, что они служат носителями систем потоков, то есть систем, в которых некоторые объекты текут, движутся или транспортируются по системе каналов (дуг сети) ограниченной пропускной способности. Примерами могут служить потоки автомобильного транспорта по сети автодорог, грузов по участку железнодорожной сети, воды в городской сети водоснабжения, электрического тока в электросети, телефонных или телеграфных сообщений по каналам связи, программ в вычислительной сети. Ограниченная пропускная способность означает, что интенсивность перемещения соответствующих предметов по каналу ограничена сверху определённой величиной.
Наиболее часто в сети решается задача о максимальном потоке и минимальном разрезе. При этом граф должен удовлетворять следующим условиям:
G – связный граф без петель;
существует ровно одна вершина, не имеющая предшествующих; эта вершина называется источником и обозначается S;
существует ровно одна вершина, не имеющая последующих; эта вершина называется стоком и обозначается t;
каждой дуге ставится в соответствие неотрицательное число , называемое пропускной способностью дуги.
Функция , определённая на множестве U дуг сети , называется потоком, если и для любой вершины . Последнее условие называется условием сохранения потока; в промежуточных вершинах потоки не создаются и не исчезают.
Величина называется остаточной пропускной способностью дуги . Если , то дуга называется насыщенной.
Максимальный поток определяется с помощью одного из основных понятий теории сетей – разреза. Разрез может быть представлен как множество дуг, исключение которых из сети отделило бы некоторое множество узлов от остальной сети.
Предположим, что множество S вершин сети разбито на два непустых непересекающихся подмножества . Множество дуг, начала которых лежат в , а концы в , называется ориентированным разрезом и обозначается
. (1)
Пропускной способностью или величиной разреза называется сумма пропускных способностей входящих в него дуг, то есть
. (2)
На следующем рисунке изображена сеть, на которой около каждого ребра указана его пропускная способность. Произведены два разреза I и II. При разрезе I вершины оказались разбиты на подмножества , а рёбрами, образующими разрез, стали рёбра . При разрезе II , разрез образует рёбра .
Рис. 70