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

Начать. Это бесплатно
или Регистрация c помощью Вашего email-адреса
Rocket clouds
Метрические задачи в графах создатель 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