Для построения матрицы расстояний, сопоставим строки и столбцы вершинам. На пересечении строк и столбцов укажем расстояние между соответствующими вершинами.
Таблица 7.1
1 2 3 4 5 6 7 8
1 0 1 2 3 1 1 2 3 3
2 1 0 1 2 2 1 2 3 3
3 2 1 0 1 2 1 2 3 3
4 3 2 1 0 3 2 1 1 3
5 1 2 2 3 0 1 2 3 3
6 1 1 1 2 1 0 1 2 2
7 2 2 2 1 2 1 0 1 2
8 3 3 3 2 3 2 1 0 3
На месте (1, 1) стоит 0, так как кратчайший маршрут между вершиной 1 и вершиной 1 – это вырожденный маршрут (без ребер) длины 0.
На месте (1, 2) стоит 1, так как кратчайший маршрут между вершиной 1 и вершиной 2 – это единственное ребро, связывающее эти вершины.
На месте (1, 3) стоит 2, так как кратчайшая простая цепь, между вершиной 1 и вершиной 3 – это цепь из двух ребер (1, 2, 3). Значит, расстояние между этими вершинами равно 2.
И так далее.
В последнем столбце таблицы указано расстояние от данной вершины до наиболее удаленной от нее вершины – эксцентриситет. Это максимальное значение в строке.
Максимум значений последнего столбца – диаметр графа. Откуда d(G) = 3.
Минимум значений последнего столбца – радиус графа. Откуда r(G) = 2.
Центрами являются вершины: 6, 7. Их эксцентриситеты минимальны и равны радиусу графа.
Для построения диаметральных цепей выясним с помощью матрицы расстояний, какие вершины наиболее удалены друг от друга. Так как максимальное расстояние между вершинами – это диаметр графа, значит, найдем вершины, находящиеся на расстоянии, равном диаметру, то есть на расстоянии 3 ребер. Это вершины 1, 2, 3, 4, 5, 8. Следовательно, все диаметральные цепи в графе связывают эти вершины. Таких цепей две:
; .
Для построения радиальных цепей выясним с помощью матрицы расстояний, какие вершины наиболее удалены от центров.
От центра, которым является вершина 6, на расстоянии радиуса, равного 2, находятся вершины 4 и 8. Значит можно провести радиальные цепи: , , .
От другого центра, которым является вершина 7, на расстоянии радиуса находятся вершины 1, 2, 3 и 5. Значит можно провести радиальные цепи: , , , , .
8. Индивидуальные задания по теме «Характеристические числа графов»
Для графа, приведенного на рисунке, определить цикломатическое число, число внутренней устойчивости, число внешней устойчивости, хроматическое число, хроматический индекс.
Рис. 8.1
Нужно полное решение этой работы?
Решение
Пронумеруем вершины (рис. 8.2).
Рис. 8.2
Для нахождения цикломатического числа необходимо выяснить, сколько ребер графа достаточно убрать, чтобы разрушить все существующие циклы. Из рисунка 8.3 видно, что таких ребер минимум 5. Они указаны пунктиром.
Рис. 8.3. Нахождение цикломатического числа графа
Этот же результат можно получить по формуле:
.
Здесь – число компонент связности графа. Так как все вершины графа связны (связаны маршрутами), то у этого графа 1 компонента связности.
Для нахождения числа внутренней устойчивости, необходимо выяснить, каким будет максимальное внутренне устойчивое множество графа. Для этого надо определить максимальную совокупность попарно несмежных вершин. Из рисунка 8.4 видно, что таких вершин максимум 3. Они помечены белыми кружкам на рисунке 8.4.
Рис. 8.4. Нахождение числа внутренней устойчивости графа
Таким образом, максимальным внутренне устойчивым множеством будут множества вершин , .
Тогда по получим число внутренней устойчивости: .
Для нахождения числа внешней устойчивости, необходимо выяснить, каким будет минимальное внешне устойчивое множество графа
.
Рис. 8.5. Нахождение числа внешней устойчивости графа
На рисунке 8.5 видно, что вершины множества таковы, что из остальных вершин графа, составляющих множество , ведут ребра в вершины 2 или 7. Значит множество – это множество внешней устойчивости. Очевидно, что таким же свойством обладает множество , .
Получим число внешней устойчивости: .
Для нахождения хроматического числа, необходимо выяснить, каким будет минимальное количество красок, в которые можно раскрасить вершины графа, так чтобы никакие две смежные вершины не были окрашены в один цвет.
Для этого надо определить внутренне устойчивые множества графа с как можно большей мощностью.
На рисунке 8.6 видно, что вершины 1, 4 и 3 – попарно несмежны, значит, их можно раскрасить в один и тот же цвет (например, красный)
Задать вопрос
на новый заказ в Автор24.
