5 Конечные графы и сети Основные определения

Определение. Если на плоскости задать конечное множество V точек и конечный набор линий Х, соединяющих некоторые пары из точек V, то полученная совокупность точек и линий будет называться графом.

При этом элементы множества V называются вершинами графа, а элементы множества Х – ребрами.

В множестве V могут встречаться одинаковые элементы, ребра, соединяющие одинаковые элементы называются петлями. Одинаковые пары в множестве Х называются кратными (или параллельными) ребрами.

Количество одинаковых пар (v, w) в Х называется кратностью ребра (v, w).

Множество V и набор Х определяют граф с кратными ребрами – псевдограф.

G = (V, X)

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

Если в наборе Х ни одна пара не встречается более одного раза, то мультиграф называется графом.

Если пары в наборе Х являются упорядочными, то граф называется ориентированным или орграфом.

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

Определение. Если х = {v, w} – ребро графа, то вершины v, w называются концами ребра х.

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

Определение. Вершины v, w графа G = (V,X) называются смежными, если {v,w}?X. Два ребра называются смежными, если они имеют общюю вершину.

Определение. Степенью вершины графа называется число ребер, которым эта вершина принадлежит. Вершина называется изолированной, если если ее степень равна единице и висячей, если ее степень равна нулю.

Определение. Графы G₁(V₁, X₁) и G₂(V₂, X₂) называются изоморфмными, если существует взаимно однозначное отображение φ: V₁ → V₂, сохраняющее смежность.

Определение. Маршрутом (путем) для графа G(V, X) называется последовательность v₁ x₁ v₂ x₂ v₃ …x_k v_k+1. Маршрут называется замкнутым, если его начальная и конечная точки совпадают. Число ребер (дуг) маршрута (пути) графа называется длиной маршрута (пути).

Определение. Незамкнуты маршрут (путь) называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью.

Определение. Замкнутый маршрут (путь) называется циклом (контуром). Цикл, в котором все вершины попарно различны, называется простым циклом.