Решение. Для определения этих параметров изобразим граф и составим матрицу расстояний: на пересечении столбца и строки (вершина графа) матрицы указывается расстояние

Для определения этих параметров изобразим граф и составим матрицу расстояний: на пересечении столбца и строки (вершина графа) матрицы указывается расстояние между этими вершинами; такая матрица (выделена на рисунке) симметрична относительно главной диагонали.

В столбце с заголовком r(v_i) укажем удаления от соответствующих вершин (максимальное значение расстояния каждой строки).

Максимальное из удалений и будет диаметром графа (т.е. максимально возможным расстоянием между вершинами в исследуемом графе): D(G) = 3.

Вершины, для которых удаление r(v_i) принимает минимальное значение (помечены в последнем столбце «Да»), являются центрами графа G, а значение удаления – радиусом графа:

r(G) = 2.

Если ребра графа нагружены (каждому ребру поставлено в соответствие определенное числовое значение), то процедура исследования аналогична описанной выше, но при заполнении матрицы нужно определять расстояние между вершинами не по числу ребер, а по суммарной их длине.

3. Диаметр протяженности, радиус протяженности и центр протяженности графа

Рассмотрим единичный связный неориентированный граф G. Максимальная длина простой цепи с началом в V¢, и концом в V² называется протяженностью между этими вершинами (обозначается g(v¢, v²)).

Диаметр протяженности графа – максимальная из протяженностей между любыми парами вершин:

L(G) = max g(v¢, v²).

v¢, v² Î G

Для каждой вершины v_i существуют самые длинные простые цепи, связывающие ее с другими вершинами графа; их длина называется числом протяженности для вершины v_i:

l(v_i) = max g(v_j).

v_j Î G

Центр (центры) протяженности – вершина с минимальным числом протяженности. Самые длинные простые цепи с началом в центре протяженности называются радиальными, а их длина – радиусом протяженности графа.

l(G) = min l(v_i).

v_i Î G

Параметры протяженности (центр, диаметр и радиус) при анализе графа на максимум определяются аналогично параметрам при анализе графа на минимум.

Пример. Для анализа на максимум используем граф G из предыдущего примера: V = {a, b, c, d, e, f}; E = {ab, ac, bc, cd, ce, de, ef}. Определить диаметр протяженности, центр (центры) протяженности и радиус протяженности этого графа.

Для определения этих параметров изобразим граф G и составим матрицу протяженностей: (на пересечении столбца и строки (вершины графа) матрицы указывается протяженность между этими вершинами; такая матрица (выделена на рисунке) симметрична относительно главной диагонали).

В столбце с заголовком l(v_i) приводятся числа протяженностей для вершин, указанных в начале каждой строки (максимальное из значений протяженностей каждой строки). Максимальное из числа протяженностей и будет диаметром протяженности графа (т.е. максимально возможной протяженностью между вершинами в исследуемом графе): L(G) = 5.

Вершина С, для которой число протяженности принимает минимальное значение, является центром протяженности графа G, а значение числа протяженности вершины С – радиусом протяженности графа: l(G) = 3.

Если ребра графа нагружены (каждому ребру поставлено в соответствие определенное числовое значение), то процедура исследования графа на максимум аналогична описанной выше, но при заполнении матрицы нужно определять протяженность между вершинами не по числу ребер, а по суммарной их длине.

числу ребер, а по суммарной их длине.