double arrow

Цепи, циклы, пути и контуры графов


Для неориентированных графовсправедливы следующие понятия.

Цепь – конечная или бесконечная последовательность ребер

S = (…,g1, g2,…), в которой у каждого ребра gk одна из вершин является вершиной ребра gk-1, а другая – вершиной ребра gk+1. При этом одно и то же ребро или вершина может встречаться несколько раз (рис.2.6):

{g0, g1, g2, g3, g4, g5, g2, g6} = {(x0, x1), (x1, x2), (x2, x3), (x3, x1), (x1, x4), (x4, x3), (x3, x2), (x2, x5)}.

Цепь называется простой, если все ребра в ней различны, и состав­ной или сложной – в противном случае. Величины (вершины)в простой цепи могут повторяться. Цепь называется элементарной,если в ней ни одна из вершин не повторяется.

Циклом называется конечная цепь, начинающаяся на некоторой вершине xi и оканчивающаяся на той же вершине.

Простые, составные или сложные, элементарные циклы – по анало­гии с цепями.

Для ориентированных графоввведены следующие дополнительные понятия.

Путем в графе G(x) называется такая последовательность дуг

(g1, g2 ,…), что конец каждой предыдущей дуги является началом следую­щей. Существуют простые, составные (сложные), элементарные пути.

Контур графа – это конечный путь, у которого начальная вершина совпадает с конечной. Существуют простые, составные (сложные), эле­ментарные контуры.

Длина пути есть число дуг L(s) в последовательности дуг пути s. В случае бесконечного пути L(s) = ¥.

Граф называется симметри­ческим, если " xi, xj из того, что xi Î G(xj) Þ xj Î G(xi), то есть две смежные вершины xi, xj всегда соединены противоположно ори­ентированными дугами (рис.2.7).

Граф называется антисим­метрическим,если " xi, xj; xi Î G(xj) Þ xj Ï G(xi), то есть каждая пара смежных вершин соединена только в одном направлении.


Сейчас читают про: