Схема, показанная на этой ссылке "График с 6 вершинами и 7 краями, где вершина № 6 на крайне левом является листовой вершиной или подвесной вершиной". имеет ДИАМЕТР 4? право или неправильно?
Определения
Диаметр графика является максимальным эксцентриситетом любой вершины в графике. Таким образом, это - самое большое расстояние между любой парой вершин. Для нахождения диаметра графика сначала найдите кратчайший путь между каждой парой вершин. Самая большая длина любого из этих путей является диаметром графика.
Диаметр, D, сети, имеющей N узлы, определяется как максимальные кратчайшие пути между любыми двумя узлами в сети
Диаметр, D, сети, имеющей N узлы, определяется как самый длинный путь, p, кратчайших путей между любыми двумя узлами D ¼ макс. (minp [pij длина (p)). В этом уравнении pij является длиной пути между узлами i и j, и длина (p) является процедурой, которая возвращает длину пути, p. Например, диаметр 4 4 Сетки D ¼ 6.
Похоже, что диаметр по определению равен 3.
Самые длинные кратчайшие пути имеют длину 3 ребра, например между 6-1
и 6-2
.
Вот ваше второе определение с некоторыми типографскими исправлениями, чтобы оно имело смысл:
Диаметр
D
сети определяется как самый длинный путь из кратчайших путей между любыми два узла. Например, диаметр сетки 4x4 D = 6
Давайте посмотрим на пример сетки 4x4 :
A---B---C---D
| | | |
E---F---G---H
| | | |
I---J---K---L
| | | |
M---N---O---P
Самый длинный кратчайший путь имеет длину 6 ребер, то есть между AP
и MD
.
Mathworld - Wolfram / Graph Diameter
Длина «самого длинного кратчайшего пути» между любыми двумя вершинами графа графа.
Глоссарий графов и графов - cudenver.edu
Диаметр : Диаметр графа - это длина самой длинной цепочки, которую вы вынуждены использовать для перехода от одной вершины к другой в этом графе. Вы можете найти диаметр графа, найдя расстояние между каждой парой вершин и взяв максимальное из этих расстояний.