Основные понятия теории графов. Гладких О.Б - 58 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

Составители: 

Рубрика: 

58
Для некоторых классов графов последова-
тельная раскраска является минимальной. В об-
щем случае это не так.
1.13. Расстояния в графах
Пусть G = (М, R) – связный неорграф, а, b –
две его несовпадающие вершины.
Определение 1.45. Длина кратчайшего (а, b) –
маршрута называется расстоянием между верши-
нами а и b и обозначается через ρ (а, b).
Определение 1.46. Если М = {a
1
, a
2
, ..., a
n
}, то
матрица Р = (р
ij
), в которой p
ij
= ρ (a
i
, a
j
), называет-
ся матрицей расстояний.
Определение 1.47. Для фиксированной вершины а
величина е (а) = mах {ρ (а, b) | b ´ М} называется
эксцентриситетом вершины а. Таким образом,
эксцентриситет вершины равен расстоянию от
данной вершины до наиболее удаленной от нее.
Если Р – матрица расстояний, то эксцентри-
ситет e.(a
i
) равен наибольшему из чисел, стоящих
в i-й строке.
Определение 1.48. Максимальный среди всех экс-
центриситетов вершин называется диаметром
графа G и обозначается через d (G):
d (G) = тах{е (а) | а ´ М}.
Определение 1.49. Вершина а называется перифе-
рийной, если e (a) = d (G).
119
могут соответствовать такой компании (рис. 5.6 и
рис. 5.7).
Рис. 5.6. Рис. 5.7.
Итак, ситуация рассмотренная в задаче
вполне возможна. Но случай, рассмотренный на
рис. 5.7, соответствует не одной, а двум компани-
ям, участники одной из них не знакомы с участни-
ками другой.
Про граф, изображенный на рис. 5.6, гово-
рят, что он связный, так как из каждой вершины
по ребрам можно попасть в любую другую
. Дела-
ем вывод, что в этом случае каждый через своих
знакомых может познакомиться со всеми
остальными.
Во втором случае получились два простых
цикла, не сцепленные между собой в вершинах.
Такой граф называется не связным.
Задача 5.5.
Для графа G = (A, U) (рис. 5.8) найти матри-
цу смежности.
u
3
u
4
u
6
u
8
u
7
u
9
1
2
3
                                                           могут соответствовать такой компании (рис. 5.6 и
     Для некоторых классов графов последова-               рис. 5.7).
тельная раскраска является минимальной. В об-
щем случае это не так.
             1.13. Расстояния в графах
       Пусть G = (М, R) – связный неорграф, а, b –
две его несовпадающие вершины.
Определение 1.45. Длина кратчайшего (а, b) –
маршрута называется расстоянием между верши-                       Рис. 5.6.                       Рис. 5.7.
нами а и b и обозначается через ρ (а, b).
Определение 1.46. Если М = {a1, a2, ..., an}, то                 Итак, ситуация рассмотренная в задаче
матрица Р = (рij), в которой pij = ρ (ai, aj), называет-   вполне возможна. Но случай, рассмотренный на
ся матрицей расстояний.                                    рис. 5.7, соответствует не одной, а двум компани-
Определение 1.47. Для фиксированной вершины а              ям, участники одной из них не знакомы с участни-
величина е (а) = mах {ρ (а, b) | b ´ М} называется         ками другой.
эксцентриситетом вершины а. Таким образом,                       Про граф, изображенный на рис. 5.6, гово-
эксцентриситет вершины равен расстоянию от                 рят, что он связный, так как из каждой вершины
данной вершины до наиболее удаленной от нее.               по ребрам можно попасть в любую другую. Дела-
       Если Р – матрица расстояний, то эксцентри-          ем вывод, что в этом случае каждый через своих
ситет e.(ai) равен наибольшему из чисел, стоящих           знакомых может познакомиться со всеми
в i-й строке.                                              остальными.
Определение 1.48. Максимальный среди всех экс-                   Во втором случае получились два простых
центриситетов вершин называется диаметром                  цикла, не сцепленные между собой в вершинах.
графа G и обозначается через d (G):                        Такой граф называется не связным.
              d (G) = тах{е (а) | а ´ М}.                                    Задача 5.5.
Определение 1.49. Вершина а называется перифе-                  Для графа G = (A, U) (рис. 5.8) найти матри-
рийной, если e (a) = d (G).                                цу смежности.
                                                                                         2
                                                                               u7
                                                                                              u6
                             58                                                     u8   119
                                                                      u9                               3
                                                                                         u3
                                                                               1

Страницы