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

Определение. Если на плоскости задать конечное множество 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. Два ребра называются Смежными, если они имеют общюю вершину.

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

Определение. Графы G1(V1, X1) и G2(V2, X2) называются Изоморфмными, если существует взаимно однозначное отображение j: V1 ® V2, сохраняющее смежность.

Определение. Маршрутом (путем) для графа G(V, X) называется последовательность v1x1v2x2v3…xkvk+1. Маршрут называется Замкнутым, если его начальная и конечная точки совпадают. Число ребер (дуг) маршрута (пути) графа называется Длиной Маршрута (пути).

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

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

< Предыдущая		Следующая >