Эксцентриситет вершины
Эксцентриситет вершины показывает, насколько далеко от неё может находиться самая удалённая вершина графа. Он вычисляется через расстояния между вершинами и используется для нахождения диаметра и центра графа.
Здесь \(V\) — множество вершин графа, а \(d(v,u)\) — длина кратчайшего пути от вершины \(v\) до вершины \(u\). Если граф задан матрицей расстояний, достаточно выбрать строку, соответствующую вершине \(v\), и найти в ней наибольшее конечное значение. Для вычисления расстояний в больших графах могут применять алгоритм Флойда.
Пусть из вершины \(A\) до вершин \(B\), \(C\), \(D\) кратчайшие расстояния равны соответственно \(1\), \(2\) и \(3\). Тогда \(e(A)=\max(1,2,3)=3\). Это означает, что самая удалённая от \(A\) вершина находится на расстоянии трёх рёбер.
Эксцентриситет относится к одной вершине, а диаметр — ко всему графу. Диаметр равен наибольшему эксцентриситету среди всех вершин: \(D=\max_{v\in V}e(v)\). Наименьший эксцентриситет определяет вершины центра графа. Если граф несвязный, расстояние между вершинами разных компонент считают бесконечным, поэтому обычные определения диаметра и эксцентриситета требуют уточнения.
Расстояния от вершины \(X\) до остальных вершин равны \(2\), \(4\), \(1\) и \(3\). Чему равен её эксцентриситет?
Главное
- Эксцентриситет вершины — максимальное кратчайшее расстояние от неё до других вершин.
- Формула: \(e(v)=\max_{u\in V}d(v,u)\).
- Диаметр графа — максимальный эксцентриситет, а центр графа образуют вершины с минимальным эксцентриситетом.