Обоснование алгоритма Флойда.

Пусть задан граф, содерж. m+1 вершину. Рассм. кратчайший путь из v_i в v_j, содерж. вершин .

1. Если этот путь не содержит , то .

2. Если же он содерж. , то, деля путь на отрезки от v_i до v_m и от v_m до v_j, получ. рав-во .

Тогда рекуррентная формула для задания расстояния между всеми парами вершин из множ. {v₁,..., v_m, v_m+1} имеет вид:

; .

Из 2 возмож. знач. длины выбир. мин.

Данные: матрица весов дуг A[i, j], 1 £ i, j £ n, орграфа без контуров отрицательной длины.

Результаты: расстояния между всеми парами вершин D[i, j] = d(vi, vj).

1. Begin

2. for i:= 1 to n do

3. for j:= 1 to n do D[i, j]:= A[i, j];

4. for i:= 1 to n do D[i, i]:= 0;

5. for m:= 1 to n do

6. for i:= 1 to n do

7. for j:= 1 to n do

8. D[i, j]:= min(D[i, j], D[i, m] + D[m, j];

9. End;

Сложность алгоритма — O(n³). Такую же сложность имел алгоритм Форда–Беллмана нахождения расстояний от фиксированной вершины до всех остальных вершин.

С задачей опред. кратчайших путей в графе тесно связана задача транзитив. замыкания бинарного отношения.

Транзитивное, если квадрат отношения явл. подмнож. исх. отнош.: ().

Бинарное отношение E Í V´ V можно однозначно представить орграфом G = <V, E>. Для произвольного отношения E определяется отношение E*, такое что E*={(x, y): в <V, E> сущ. путь ненул. длины из x в y}.

E* — транзитивное отношение на множестве V и E Í E*. E* явл. наименьшим транзитивным замыканием, содержащим E.

Обоснование алгоритма Уоршалла:

Строка ; зам. на .

Если в отношении присутствуют обе пары (i,m) и (m,j), то в транзитивном замыкании должна существовать пара (i,j). Т.е. .

Сложность алгоритма O(n³).

41. Потоки в сетях. Классификация вершин по воздействию на поток. Величина потока. Разрез и поток через разрез. Теорема о максимальном потоке. Метод увеличивающих цепей.

Пусть G = (V, E) — связный граф и F Ì E — подмнож. множ. его ребер. При этом F называется разделяющим множеством если подграф G¢ = (V, E – F) несвязен. Разделяющие множества всегда сущ. (если в графе вершины), т. к. всегда можно положить F = E. Разделяющее множ. Может разбить граф на 2 и больше компонент.

Если задан связный граф G = (V, E) и множ. его вершин разбито на 2 непустых подмнож. W и множ. ребер, соединяющих W с W¢, называется разрезом. Для любого множ. W это множ. ребер будет непусто в силу связности графа G, поэтому разрез определен.

Сеть — пара S = áG, сñ, где G = áV, Eñ — произвольный орграф, а с: E ® R — функция, которая каждой дуге áu, vñ ставит в соответствие неотриц. вещественное число с(и, v), называемое пропускной способностью этой дуги. Множества V и Е называются соответственно множ. вершин и множ. дуг сети S.

Под разрезом Р(А) сети S, соотв. подмнож. А Í V (А ¹ Æ, А ¹ V), мы понимаем множ. дуг áu, vñ Î Е, таких что u Î А и v Î V\A, т. е. P(A) = E Ç (A ´ (V\A)).

Для произвольного потока f в сети S поток через разрез Р(А): .

Определим пропускную способность разреза Р(А) следующим образом: .

Под минимальным разрезом, разделяющим s и t, мы будем понимать произвольный разрез Р(А), s Î А, t Î V\A с минимальной пропускной способностью.

Теорема (Форд и Фалкерсон). Величина каждого потока из s в t не превосходит пропускной способности мин. разреза, разделяющего s и t, причем существует поток, достигающий этого значения.

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

Будем говорить, что дуга е сети S явл. допустимой дугой из u в v относительно потока f, если

и (1) или

и (2).

В зависимости от того, какое из приведенных условий вып., будем говорить соответственно о согласованной или несогласованной допустимой дуге из и в v. Увеличивающей цепью (длины l) для данного потока f из s в t называется произвольная знакоперем. последовательность (попарно различных) вершин и дуг такая, что v₀ = s, v_l = t, и для каждого i £ l дуга допустима из v_i–1 в v_i относительно потока f.

42. Знаковые орграфы и задачи социологии. Теорема Харари о балансе. Недостатки математической модели о балансе.

Знаковый граф — граф, каждому ребру кот. приписан какой-либо знак.

Знак маршрута определяется как знак произведения входящих в них дуг или ребер (если знак плюс зам. на +1, а знак минус на –1).

Маршрут имеет знак минус, если число дуг / ребер в нем нечетно, иначе — плюс.

Хейдер изучал задачи из обл. социологии малых групп людей.

#: группа из 3 человек. Знак означает явно выраженную симпатию или антипатию.

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

Дата добавления: 2015-11-16