Вопросы для повторения.

1. Плоский граф.

2. Планарный граф и его свойства.

3. Грань. Граница грани. Внешняя и внутренние грани

4. Теорема Эйлера.

5. Гомеоморфные графы.

6. Теорема Понтрягина-Куратовского.

7. Эквивалентная форма критерия планарности

8. Число планарности (искажённость) графа..

9. Толщина графа. Теорема о толщине связного графа

10. Сегмент.

11. Контактная вершина. Допустимая грань. цепи

12. Конфликтующие сегменты.

13. Алгоритм укладки планарного графа на плоскость.

Задачи для самостоятельного решения.

1. Является ли граф, изображённый на рис. 67, планарным?

Рис. 67

2. При каких n граф порядка 2n изображённый на рис. 68, является планарным?

…

…

Рис. 68

3. С помощью алгоритма укладки графа на плоскость постро

ить плоскую укладку или установить непланарность графа,

x₂₂₂

x₃

изображённого на рис. 69.

x₄

x₁

x₅

x₆

Рис. 69

4. Найти число планарности и толщину графов: а) К₅; б) К_3,3;

в) графа Петерсена.

Глава 5. Потоки в сетях

1. Потоки в сетях

Функциональное назначение большинства физически реализованных сетей состоит в том, что они служат носителями систем потоков, то есть систем, в которых некоторые объекты текут, движутся или транспортируются по системе каналов (дуг сети) ограниченной пропускной способности. Примерами могут служить потоки автомобильного транспорта по сети автодорог, грузов по участку железнодорожной сети, воды в городской сети водоснабжения, электрического тока в электросети, телефонных или телеграфных сообщений по каналам связи, программ в вычислительной сети. Ограниченная пропускная способность означает, что интенсивность перемещения соответствующих предметов по каналу ограничена сверху определённой величиной.

Наиболее часто в сети решается задача о максимальном потоке и минимальном разрезе. При этом граф должен удовлетворять следующим условиям:

1. G – связный граф без петель;

2. существует ровно одна вершина, не имеющая предшествующих; эта вершина называется источником и обозначается S;

3. существует ровно одна вершина, не имеющая последующих; эта вершина называется стоком и обозначается t;

4. каждой дуге ставится в соответствие неотрицательное число , называемое пропускной способностью дуги.

Функция , определённая на множестве U дуг сети , называется потоком, если и для любой вершины . Последнее условие называется условием сохранения потока; в промежуточных вершинах потоки не создаются и не исчезают.

Величина называется остаточной пропускной способностью дуги . Если , то дуга называется насыщенной.

Максимальный поток определяется с помощью одного из основных понятий теории сетей – разреза. Разрез может быть представлен как множество дуг, исключение которых из сети отделило бы некоторое множество узлов от остальной сети.

Предположим, что множество S вершин сети разбито на два непустых непересекающихся подмножества . Множество дуг, начала которых лежат в , а концы в , называется ориентированным разрезом и обозначается

. (1)

Пропускной способностью или величиной разреза называется сумма пропускных способностей входящих в него дуг, то есть

. (2)

На следующем рисунке изображена сеть, на которой около каждого ребра указана его пропускная способность. Произведены два разреза I и II. При разрезе I вершины оказались разбиты на подмножества , а рёбрами, образующими разрез, стали рёбра . При разрезе II , разрез образует рёбра .

Рис. 70