Цепи, циклы, пути, контуры

Цепью называется та­кая последовательность ребер Е₀, E_1,..., E_k-1, E_k,
когда каждое ребро Е_k-1 соприкасается одним из концов с ребром Е_k.

Понятие цепи обычно используется для неориентированных графов.

Цепь можно обозначить последовательностью вершин, которые она содержит. Например, для графа це­пью будет (1, 4, 3, 5) или (1, 3, 4).

Путем называется такая последователь­ность дуг, когда конец каждой предыдущей дуги совпадает с началом последующей. Например, для графа последова­тельность дуг (1, 3), (3, 4), (4, 2) является путем. Понятие пути обычно ис­пользуется для ориентированных графов.

Циклом называется такая конечная цепь, которая начинается и заканчивается в одной вершине. Понятие цикла имеет смысл только для неориентированных графов.

Эйлеров граф - это граф, в котором существует цикл, содержащий все ребра графа (вершины могут повторяться) (задача о кенигсбергских мостах).

Гамильтонов граф - это граф, в котором существует цикл (без повторений), содержащий все вершины графа.

Контуром называется такой конечный путь, у которого начальная вершина первой ду­ги совпадает с конечной вершиной последней дуги. Например, для графа последо­вательность дуг (1, 3), (3, 5), (5, 1) есть контур.

Длиной цепи (пути) называют число ребер (дуг), входящих в цепь (путь) графа.

Матрица смежности вершин графа А является матрицей непосредственных путей графа, имеющих длину, равную единице. Общее число транзитных путей длиной λ может быть получено в результате возведения в λ -тую степень матрицы А: Элемент матрицы А^λ а_ij(λ) определяет число путей длиной λ от вершины i к вершине j.

Степень вершины. Число ребер, инцидентных вершине i неориентированного графа, называют степенью вершины i о бозна­чают р(i).

Дата добавления: 2014-01-20