Понятия смежности, инцидентности, степени

Если x ={ v, w } - ребро, то v и w − концы ребра x.

Если x =(v, w) - дуга ориентированного графа, то v − начало, w – конец дуги.

Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x).

Вершины v, w называются смежными, если { v, w }Î X.

Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.

Маршруты и пути

Последовательность v ₁ x ₁ v ₂ x ₂ v ₃... x _k v _k+1, (где k ³1, v _iÎ V, i =1,..., k +1, x _iÎ X, j =1,..., k), в которой чередуются вершины и ребра (дуги) и для каждого j =1,..., k ребро (дуга) x _j имеет вид { v_j, v_{j +1}} (для ориентированного графа (v_j, v_{j +1})), называется маршрутом, соединяющим вершины v ₁ и v_{k +1} (путем из v ₁ в v_{k +1}).

Пример

В графе, изображенном на рис.4, v ₁ x ₁ v ₂ x ₂ v ₃ x ₄ v ₄ x ₃ v ₂ - маршрут, v ₂ x ₂ v ₃ x ₄ v ₄ – подмаршрут; маршрут можно восстановить и по такой записи x ₁ x ₂ x ₄ x ₃;

Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.

Цикл − замкнутая цепь (в неориентированном графе).

Контур − замкнутый путь (в ориентированном графе).

Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.

Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.

Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.

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

Длина маршрута (пути) − число ребер в маршруте (дуг в пути).

Утверждение 1. Для того чтобы связный псевдограф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.

Утверждение 2. Для того чтобы связный псевдограф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.

Матрицы смежности и инцидентности

Пусть D =(V, X) ориентированный граф, V ={ v ₁,..., v _n}, X ={ x ₁,..., x _m}.

Матрица смежности ориентированного графа D − квадратная матрица

A (D)=[ a_ij ] порядка n, где

Матрица инцидентности − матрица B (D)=[ b_ij ] порядка n ´ m, где

Матрицей смежности неориентированного графа G =(V, X) называется квадратная симметричная матрица A (G)=[ a_ij ] порядка n, где

.

Матрица инцидентности графа G называется матрица B (G)=[ b_ij ] порядка n ´ m, где

Расстояния в графе

Пусть - граф. Расстоянием между вершинами называется минимальная длина пути между ними, при этом , , если не пути.

Расстояние в графе удовлетворяют аксиомам метрики

1) ,

2) (не в ориентированном графе)

3)

4) в связном графе (не в ориентированном графе).

Нагруженные графы

Нагруженный граф − ориентированный граф D =(V, X), на множестве дуг которого определена не которая функция , которую называют весовой функцией.

Цифра над дугой (см. рис. 5)− вес дуги (цена дуги).

Рис. 5.

Обозначения: для любого пути П нагруженного ориентированного графа D через l (П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).

Величина l называется длиной пути.

Если выбрать веса равными 1, то придем к ненагруженному графу.

Путь в нагруженном ориентированном графе из вершины v в вершину w, где v ¹ w, называется минимальным, если он имеет наименьшую длину.

Аналогично определяется минимальный маршрут в нагруженном графе.

Введем матрицу длин дуг C (D)=[ c_ij ] порядка n, причем

Свойства минимальных путей в нагруженном ориентированном графе

1) Если для " дуги , то " минимальный путь (маршрут) является простой цепью;

2) если минимальный путь (маршрут) то для " i, j: путь (маршрут) тоже является минимальным;

3) если − минимальный путь (маршрут) среди путей (маршрутов) из v в w, содержащих не более k +1 дуг (ребер), то − минимальный путь (маршрут) из v в u среди путей (маршрутов), содержащих не более k дуг (ребер).