Метрические задачи в графах

马上开始. 它是免费的哦
注册 使用您的电邮地址
Метрические задачи в графах 作者: Mind Map: Метрические задачи в графах

1. Максимальный поток в сети

1.1. Задача 2.

2. Расстояние между вершинами

2.1. Пусть u и v – две вершины связного графа G . Наименьшее число k такое, что в G существует цепь из k ребер, соединяющая вершины u и v, называется расстоянием между этими вершинами графа G и обозначается p (u, v).

2.2. Аксиомы для любых вершин u, v и w

2.2.1. p(u, v) >= 0, причем p(u, v) = 0 тогда и только тогда, когда u=v ;

2.2.2. p(u, v) = p(v, u) ;

2.2.3. p(u, v)+p(v, w)>=p(u, w).

2.3. Примечание

2.3.1. При определении расстояния между вершинами в связных орграфах приходится учитывать, что дуги орграфа являются ориентированными.

3. Диаметр

3.1. Наибольшее из всех расстояний между вершинами графа G называется диаметром этого графа; обозначение - d(G).

4. Радиус

4.1. Минимальный эксцентриситет вершин.

5. Задача 1. Найти диаметр графа Cn.

6. Эксцентриситет вершины графа

6.1. Расстояние до максимально удаленной от нее вершины.

7. Взвешенный граф

7.1. Граф G, на множестве вершин V и ребер E которого заданы функции p и q соответственно, называется взвешенным графом.

8. Экстремальные задачи во взвешенных графах

8.1. Поиск кратчайших маршрутов

8.1.1. Алгоритм Флойда

8.2. Поиск минимального остового дерева

8.2.1. Алгоритм 1

8.2.2. Алгоритм 2