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

UptoLike

ВУЗ: 

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

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

Рубрика: 

60
Определение 1.50. Минимальный из эксцентриси-
тетов графа G называется его радиусом и обозна-
чается через r (G):
r (G) = min{e (a) | a ´ M}.
Определение 1.51. Вершина а называется цен-
тральной, если е (а) = r (G).
Определение 1.52. Множество всех центральных
вершин графа называется его центром.
Пример 1.29.
Радиус графа, показанного на рис. 1.22, ра-
вен 2, а его центром является множество {2,4,5}.
1.14. Фундаментальные циклы
Пусть G = (М, R) – неорграф, имеющий п
вершин, т ребер и с компонент связности, Т – ос-
тов графа G.
Определение 1.53. Число v (G) = = m – п + с назы-
вается цикломатическим числом или циклическим
рангом графа G.
Определение 1.54. Число v* (G) = п – с называется
коциклическим рангом или корангом графа G.
Таким образом, v*(G) есть число ребер, вхо-
дящих в остов графа.
Определение 1.55. Остов Т графа G имеет v*(G) =
= п – с ребер и
i
, ..., u
n – c
, которые называются вет-
вями остова.
117
Рис. 5.4.
разрезаются, закрашены целиком; остальные ос-
таются незакрашенными.
При разрезании одного листа на три части
число листков увеличивается на два. Если же вме-
сто одного разрезано k листов, то образовалось
1 + 2
k
листов (рис. 5.4).
Задача 5.3.
Утверждают, что в одной компании из пяти
человек каждый знаком с двумя и только с двумя
другими. Возможна ли такая компания?
Решение.
Каждого из этой компании изобразим на ри-
сунке кружком. Если двое знакомы, соединим со-
ответствующие кружки отрезком. Оказывается,
такие ситуации не только возможны, но все их
можно
описать аналогичными схемами. Из рас-
Определение 1.50. Минимальный из эксцентриси-
тетов графа G называется его радиусом и обозна-
чается через r (G):
            r (G) = min{e (a) | a ´ M}.
Определение 1.51. Вершина а называется цен-
тральной, если е (а) = r (G).
Определение 1.52. Множество всех центральных
вершин графа называется его центром.
                   Пример 1.29.                                              Рис. 5.4.
      Радиус графа, показанного на рис. 1.22, ра-        разрезаются, закрашены целиком; остальные ос-
вен 2, а его центром является множество {2,4,5}.         таются незакрашенными.
                                                               При разрезании одного листа на три части
            1.14. Фундаментальные циклы
                                                         число листков увеличивается на два. Если же вме-
      Пусть G = (М, R) – неорграф, имеющий п             сто одного разрезано k листов, то образовалось
вершин, т ребер и с компонент связности, Т – ос-                                  1 + 2k
тов графа G.                                             листов (рис. 5.4).
Определение 1.53. Число v (G) = = m – п + с назы-
                                                                            Задача 5.3.
вается цикломатическим числом или циклическим
                                                               Утверждают, что в одной компании из пяти
рангом графа G.
                                                         человек каждый знаком с двумя и только с двумя
Определение 1.54. Число v* (G) = п – с называется
                                                         другими. Возможна ли такая компания?
коциклическим рангом или корангом графа G.
                                                                             Решение.
      Таким образом, v*(G) есть число ребер, вхо-
                                                               Каждого из этой компании изобразим на ри-
дящих в остов графа.
                                                         сунке кружком. Если двое знакомы, соединим со-
Определение 1.55. Остов Т графа G имеет v*(G) =
                                                         ответствующие кружки отрезком. Оказывается,
= п – с ребер иi, ..., un – c, которые называются вет-
                                                         такие ситуации не только возможны, но все их
вями остова.
                                                         можно описать аналогичными схемами. Из рас-


                            60                                                     117

Страницы