Диаметр графа
Диаметр графа — это наибольшее расстояние между двумя вершинами связного графа. Иными словами, он показывает, как далеко друг от друга могут находиться наиболее удалённые вершины, если двигаться по кратчайшему пути.
Формула
Чтобы найти диаметр, сначала определяют кратчайшее расстояние для каждой пары вершин, а затем выбирают самое большое значение.
Здесь \(V\) — множество вершин графа, а \(\operatorname{dist}(u,v)\) — расстояние между вершинами \(u\) и \(v\). В невзвешенном графе расстояние равно числу рёбер в кратчайшем пути. Если граф невзвешенный и небольшой, расстояния удобно находить перебором или поиском в ширину из каждой вершины.
Пусть в графе есть вершины \(A\), \(B\), \(C\), \(D\), а кратчайшие расстояния между некоторыми парами равны: \(\operatorname{dist}(A,B)=1\), \(\operatorname{dist}(A,C)=2\), \(\operatorname{dist}(A,D)=3\), \(\operatorname{dist}(B,D)=2\). Если остальные расстояния не превышают \(3\), то диаметр графа равен \(3\). Он достигается для пары \(A\) и \(D\).
Диаметр — это максимальное расстояние между двумя вершинами. Радиус — минимальное из максимальных расстояний от одной вершины до остальных. Вершина, для которой этот максимум минимален, называется центром графа; см. центр графа. Поэтому диаметр и радиус могут иметь разные значения.
В связном графе максимальное кратчайшее расстояние между двумя вершинами равно 5. Чему равен диаметр графа?
Главное
- Диаметр связного графа — максимальное расстояние между двумя его вершинами.
- Расстояние между вершинами берут по кратчайшему пути.
- Чтобы найти диаметр, находят расстояния для пар вершин и выбирают самое большое.