Что подразумевается под диаметром сети? - PullRequest
Новая
       27

Что подразумевается под диаметром сети?

19 голосов
/ 04 июля 2010

Диаграмма, показанная на этой ссылке графа * Граф с 6 вершинами и 7 ребрами, где вершина № 6 в дальнем левом углу является листовой вершиной или подвесной вершиной."имеет ДИАМЕТР 4? правильно или неправильно?

Определения

Максимальный диаметр графика эксцентриситет любой вершины в граф. То есть это самый большой расстояние между любой парой вершин. Чтобы найти диаметр графика, сначала найти кратчайший путь между каждым пара вершин. Наибольшая длина любой из этих путей является диаметром графика.

Диаметр D сети, имеющей N узлы определяется как максимум кратчайшие пути между любыми двумя узлами в сети

Диаметр D сети, имеющей N узлы определяется как самый длинный путь, р, из кратчайших путей между любыми два узла D ¼ max (minp [длина pij ( п)). В этом уравнении pij является длина пути между узлами я и J и длина (р) представляет собой процедуру, которая возвращает длину пути, с. За Например, диаметр 4 4 Mesh D ¼ 6.

1 Ответ

29 голосов
/ 04 июля 2010

Пример из Википедии

Похоже, диаметр для меня 3 по определению.

alt text

Самые длинные кратчайшие пути имеют длину 3 ребра, например, между 6-1 и 6-2.

Пример Mesh

Вот ваше второе определение с некоторой типографской поправкой, так что оно имеет смысл:

Диаметр D сети определяется как самый длинный путь из самых коротких путей между любыми двумя узлами. Например, диаметр сетки 4х4 D = 6

Давайте посмотрим на 4x4 меш пример: 

A---B---C---D
|   |   |   |
E---F---G---H
|   |   |   |
I---J---K---L
|   |   |   |
M---N---O---P

Самый длинный кратчайший путь имеет длину 6 ребер, то есть между A-P и M-D.

Ссылки

  • Mathworld - Диаметр Вольфрама / Графа

    Длина «самого длинного кратчайшего пути» между любыми двумя вершинами графа графа.

  • Глоссарий графиков и диграфов - cudenver.edu

    Диаметр : диаметр графа - это длина самой длинной цепочки, которую вы вынуждены использовать для перехода от одной вершины к другой в этом графе. Вы можете найти диаметр графика, найдя расстояние между каждой парой вершин и взяв максимум этих расстояний.

Смотри также

...