Метрические задачи в графах
by Мария Григанова
1. Максимальный поток в сети
1.1. Задача 2.
2. Задача 1. Найти диаметр графа Cn.
3. Взвешенный граф
3.1. Граф G, на множестве вершин V и ребер E которого заданы функции p и q соответственно, называется взвешенным графом.
4. Экстремальные задачи во взвешенных графах
4.1. Поиск кратчайших маршрутов
4.1.1. Алгоритм Флойда
4.2. Поиск минимального остового дерева
4.2.1. Алгоритм 1
4.2.2. Алгоритм 2
5. Расстояние между вершинами
5.1. Пусть u и v – две вершины связного графа G . Наименьшее число k такое, что в G существует цепь из k ребер, соединяющая вершины u и v, называется расстоянием между этими вершинами графа G и обозначается p (u, v).
5.2. Аксиомы для любых вершин u, v и w
5.2.1. p(u, v) >= 0, причем p(u, v) = 0 тогда и только тогда, когда u=v ;
5.2.2. p(u, v) = p(v, u) ;
5.2.3. p(u, v)+p(v, w)>=p(u, w).
5.3. Примечание
5.3.1. При определении расстояния между вершинами в связных орграфах приходится учитывать, что дуги орграфа являются ориентированными.