Введение в информационные системы. Брюхомицкий Ю.А. - 60 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

60
Граф, степени всех вершин которого одинаковы и равны r, называется
однородным (регулярным) r-й степени. Полный граф с n вершинами всегда од-
нородный степени n-1, а пустой граф – однородный степени 0. Граф третьей
степени называют кубическим. Он обладает рядом интересных свойств и, в ча-
стности, всегда имеет четное число вершин.
Две вершины
v
i
и v
j
графа G = (V, E) называются смежными, если
они являются граничными вершинами ребра E. Отношение смежности на
множестве вершин графа можно определить, представив каждое ребро как пару
смежных вершин, т.е. e
k
= (v
i
, v
j
), k = 1, 2, …, q. Для неориентированных графов
такие пары неупорядочены, так что e
k
= (v
i
, v
j
) = (v
j
v
i
,), а для орграфов – упоря-
дочены, причем v
i
и v
j
означают соответственно начальную и конечную верши-
ны дуги e
k
. Петля при вершине v
i
в обоих случаях представляется неупорядо-
ченной парой (v
i
, v
i
). Множество вершин V вместе с определенным на нем от-
ношением смежности полностью определяет граф.
Если вершина v
i
является концом ребра e
k
, то говорят, что они инци-
дентны: вершина v
i
инцидентна ребру e
k
и ребро e
k
инцидентно вершине v
i
. Для
орграфов различают положительную инцидентность (дуга исходит из верши-
ны) и отрицательную инцидентность (дуга заходит в вершину). Множество
вершин V и множество ребер E с определенными на них отношениями инци-
дентности полностью определяет граф.
Графы могут иметь различное геометрическое начертание, но одинако-
вые отношения инцидентности (при соответствующем обозначении вершин и
ребер). Графы, для которых сохраняется отношение инцидентности, называются
изоморфными, рис. 5.6.
Рис. 5.6. Изоморфные графы
Граф G′ = (V′, E′) является частью графа G = (V, E), если V′ V и E′
E, т.е. граф содержит все вершины и ребра любой его части. Часть, которая, на-
ряду с
некоторым подмножеством ребер графа, содержит и все инцидентные им
вершины, называется подграфом. Часть, которая, наряду с некоторым подмно-
жеством ребер графа, содержит и все вершины графа (V′ = V, E′ E), называет-
ся суграфом. Рассмотренные графы показаны на рис. 5.7.

Страницы