В процессе BFS поиска из начальной вершины s=1 получен кратчайший путь 
, ведущий в сток t=4 и состоящий из двух прямых дуг 
и 
, имеющих добавочные пропускные способности 2 и 1. Поэтому вдоль найденного пути текущий поток в сети может быть наращен на величину 
. Получаем остаточную сеть следующего этапа с модифицированными весами дуг:
4.
BFS - дерево поиска из вершины s.
В процессе BFS поиска из начальной вершины s=1 получен кратчайший путь 
, ведущий в сток t=4 и состоящий из двух прямых дуг 
и 
, имеющих добавочные пропускные способности 1 и 3 Поэтому вдоль найденного пути текущий поток в сети может быть наращен на величину 
.
Получаем остаточную сеть следующего этапа с модифицированными весами дуг:
5. BFS - дерево поиска из вершины s.
В процессе BFS поиска из начальной вершины s=1 получен кратчайший путь 
, ведущий в сток t=4 и состоящий из трех прямых дуг 
, 
и 
, имеющих добавочные пропускные способности 1, 3 и 2 соответственно. Поэтому вдоль найденного пути текущий поток в сети может быть наращен на величину 
. Получаем остаточную сеть следующего этапа с модифицированным (увеличенным) потоком 
:
6.BFS - дерево поиска из вершины s.
Комментарий: В построенном BFS дереве(состоящем только из начальной вершины s=1) отсутствует конечная вершина t=4, которая, таким образом, является не достижимой в остаточном графе текущего потока. Поэтому текущий поток является максимальным.
7. Переносим информацию с последнего остаточного графа на исходную сеть, используя веса обратных дуг остаточного графа. При этом вес обратной дуги равен реальному потоку по соответствующей прямой дуге.
Задача решена.
Ответ: Потоки по дугам графа:
№ дуги | Начальная вершина | Конечная вершина | Поток |
1 | 1 | 2 | 2 |
2 | 2 | 4 | 1 |
3 | 1 | 4 | 3 |
4 | 2 | 3 | 1 |
5 | 1 | 3 | 1 |
6 | 3 | 4 | 1 |
Суммарный поток (Пропускная способность сети): 2+3+1=5.
7. Графы. Нахождение радиуса, диаметра, центра, периферии графа.
Краткие теоретические положения.
Для связного графа 
симметрическая матрица 
расстояний по графу это квадратная матрица 
, в которой 
длина кратчайшего пути 
по данному графу из вершины 
в вершину 
этого графа. При этом длина пути во невзвешенном графе(т. е. если не указана функция веса ребер 
) это количество ребер в этом пути. Экцентриситетом вершин графа называется функция 
вида 
, т. е. эксентриситет 
вершины 
- это максимальное расстояние по графу от данной вершины до остальных вершин графа. Радиус 
графа это 
,т. е. минимальный эксцентриситет по всем вершинам графа. Диаметр 
графа это 
,т. е. максимальный эксентриситет по всем вершинам данного графа. Центр 
графа это подграф 
данного графа, порожденный по множеству 
центральных вершин графа. Таким образом, центр 
- это граф, включающий центральные вершины 
данного графа и ребра исходного графа 
, которые их соединяют. Периферия 
графа, это подграф 
данного графа, порожденный по множеству 
периферических вершин графа. Две вершины 
данного графа называются антиподальными(антиподами) , если 
, т. е. такие вершины находятся на расстоянии, равном диаметру графа и являются концами некоторого диаметра графа, т. е. некоторого пути графа, имеющего максимально возможную длину.
Пример выполнения.
Дан связный граф 
.
Эту задачу решаем методом предварительного построения всех BFS (т. е. широтных) деревьев достижимости из всех вершин данного графа как начальных. Эта процедура дает следующий результат:
Используя уровни вершин в широтных деревьях достижимости, получаем дистанционную матрицу вида
| 1 | 2 | 3 | 4 | 5 |
|
|
1 | 0 | 1 | 3 | 2 | 3 | 3 | - |
2 | 1 | 0 | 2 | 1 | 2 | 2 | 2 |
3 | 3 | 2 | 0 | 1 | 1 | 3 | - |
4 | 2 | 1 | 1 | 0 | 1 | 2 | 4 |
5 | 3 | 2 | 1 | 1 | 0 | 3 | - |
Итак, эксентриситеты вершин характеризутся таблицей
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 |
