Теория графов. Свойства графов

1. Сумма степеней вершин графа (логистической системы) всегда четна.
2. Количество вершин нечетной степени всегда четно.

Подсистема графа – это граф, который входит в основной граф (рис. 2.8).

Рисунок 2.8 – Подсистема графа.

Граф G′(V′,E′) является подсистемой графа G(V,E), если все вершины и ребра графа G′ принадлежат графу G.

Тут G, G′ – графы;

V, V′ – количества вершин;

Е, Е′ – количества ребер.

Путь (маршрут) графа – совокупность ребер, которые объединены вершинами так, что вдоль их можно двигаться по графу (рис. 2.9).

Рисунок 2.9 – Подсистема графа.

Граф называется связным, если имеется путь двумя его вершинами, в противном случае граф является несвязным (рис. 2.10).

Рисунок 2.10 – Несвязный граф.

3. Если существует путь между вершинами графа, то существует и простой путь между этими вершинами.

Циклом называется путь ненулевой длины соединяющий вершину саму с собой.

Эйлеров цикл – цикл, включающий все ребра графа и все его вершины.

Эйлеров путь – путь, включающий каждое ребро графа.

Граф называется полным, если любые 2 его вершины соединены ребром (рис. 2.11).

Рисунок 2.11 – Полный граф.

Двудольный граф (полный двудольный граф) – это граф, состоящий из 2-х (непересекающихся) полных графов (рис. 2.12).

Рисунок 2.12 – Двудольные графы.

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

Если граф ориентированный, то степень входа равна количеству входящих в вершину ребер, а степень выхода равна количеству исходящих ребер.

K_n – обозначение полного графа,

где n – количество вершин.

Литература:

1. Шевченко В.В. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2009 г.
2. Ткачук А.Н. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2008 г.