3.3 Участок сети согласно алгоритму Краскала.
Выбираем участок из нашей компьютерной сети предприятия.
1
2 3 4 4
2
3
5 7
1 4
3 1
2
Рисунок 9 - Участок сети
С помощью алгоритма Краскала получаем следующее основное дерево минимального потока сети.
1
4
2 2
1
1
2
Рисунок 10 - Применение алгоритма Краскала
Последовательность выбираемых рёбер: (A,B),(D,H),(E,Q),(Q,H),(A,F), (A,E),(B,C)
Поток:1+2+1+1+2+2+3+3=14
3.4 Транспортная сеть.
В теории графов транспортная сеть - это ориентированный граф G = (V,E), в котором каждое реброимеет неотрицательную пропускную способность. Целочисленная транспортная сеть - транспортная сеть, все пропускные способности ребер которой - целые числа.
Транспортная сеть - ориентированный граф G = (V,E), в котором:
Каждому ребруприписана неотрицательная пропускная способность и поток f(u,v). Если,то
Выделены две вершины: источникsi и стокdj, такие, что любая другая вершина сети лежит на пути из siвdj.
Поток - функция со следующими свойствами для любых вершинu и v:
Ограничение пропускной способности. Поток не может превысить пропускную способность:
Антисимметричность. Поток изu вv должен быть противоположным потоку из vв u:
Сохранение потока: для всех , кроме источника и стока.
Величиной потоканазывается сумма потоков из источника.
Разрез - разбиение множества всех вершин V на два подмножества, S и D, таких что, пропускная способность разреза (S,D) - суммапропускных способностей всех рёбер из S в D .
Поток через разрез (S,D) - сумма всех потоков из S в D . Он не превышает пропускную способность разреза, поскольку .
Транспортная сеть обладает следующим рядом свойств:
Поток через любой разрез равен сумме потоков из источника.
Сумма потоков из источника равна сумме потоков в сток.
Максимальный поток положителен тогда и только тогда, когда существует путь из источника в сток, проходящий по рёбрам с положительной пропускной способностью.
Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети.
Величина максимального потока равна пропускной способности минимального разреза.
Транспортные сети удобно моделировать при помощи графов. Зарождение теории графов в XVIII веке было связано с математическими головоломками, и довольно долго на учение о графах смотрели как на «несерьезную» тему, значение которой целиком связывали с играми и развлечениями. Первая работа по теории графов, принадлежащая швейцарскому математику Л. Эйлеру, появилась в 1736 году. Уже в XIX столетии графы использовались при построении схем электрических цепей и молекулярных схем. В настоящее время существуют главы чистой математики, например, теория математических отношений, в которых теория графов служит естественным аппаратом. С другой стороны, эта теория находит многочисленные применения в разнообразных практических вопросах, в том числе в задачах планирования и управления производством. Теория графов очень популярна при решении транспортных задач, хотя только этой областью применения она, конечно не исчерпывается.