Понятия и определения теории графов

Теория графов

Стандарт ТПР: Комбинаторные методы (метод преобразования графов)

 

Понятия и определения теории графов

 

Теория графов используется при решении:

- задач сетевого планирования;

- задач календарного планирования;

- теории массового обслуживания;

- теории алгоритмов;

- рационального размещения производства и перевозки продукции и др.

 

Граф G можно определить заданием двух множеств G = (X; U).

Элементы множества Х назовём вершинами.

Их можно изображать точками плоскости или пространства.

Множество U состоит из пар элементов множества Х.

Элементами множества U являются пары связанных между собой вершин.

Их изображают дугами кривых или отрезками прямых линий.

У дуги указывается направление связи, у ребра – нет.

 

Если в графе G все элементы множества U изображаются дугами, то граф называется ориентированным (орграф) (рис. 1, а), если рёбрами – неориентированным (рис. 1, б).

Смешанные графы состоят из дуг и ребер (рис. 1,в).

Рисунок 1 – Графы.

 

Не всегда точки пересечения дуг (рёбер) являются вершинами графа.

Примеры графов: схемы ж/д и автодорог, схемы связи между поставщиками и потребителями, структурные формулы молекул.

 

Конечные графы состоят из конечного числа элементов множества Х и U.

Два графа G и G изоморфны, если между множествами их вершин существует такое взаимно однозначное соответствие, при котором в одном из графов отрезками соединены вершины в том и только в том случае, если в другом графе отрезками соединены соответствующие вершины.

Т.е. изоморфные графы одинаковые по смыслу, но разные в изображении.

Рисунок 2 – Изоморфные графы

 

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

Граф, в котором хотя бы две смежные вершины соединены более чем одной дугой (имеет кратные дуги), называется мультиграфом (см. рис. 1, а, б).

Вершины в графе могут отличаться друг от друга количеством дуг (рёбер), которым они принадлежат (инцидентны).

Степенью P(x_i) вершины x_i называется число рёбер (дуг) графа G, инцидентных данной вершине.

Полустепень захода орграфа P⁺(x_i) вершины х_i – количество дуг, заходящих в х_i.

Полустепень исхода орграфа P^-(x_i) вершины х_i – количество дуг, исходящих из х_i.

P⁺(x_i) + P^-(x_i) = P(x_i).

На рис. 2, а P^-(x₁) = 3, P⁺(x₃) = 1.

 

Путём в орграфе называется последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей.

Путь, проходящий через все вершины и притом только по одному разу, называется гамильтоновым (рис. 3, х₁х₂х₃х₄х₅).

 

Рисунок 3

 

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

Конечный путь, у которого начальная вершина совпадает с конечной, называется контуром (рис. 3, х₃х₄х₅).

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

 

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

 

Неориентированный граф называется связным, если любые две его вершины можно соединить путём (рис. 4, а), и несвязным в противном случае (рис. 4, б).

 

Рисунок 4

 

Для установления связности орграфа ориентацию его дуг принимать в расчёт не следует.

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

Дерево – конечный связанный граф без циклов (рис. 5).

 

Рисунок 5 – Граф дерево

 

Для каждой пары вершин дерева существует единственный соединяющий их путь.

Несвязный граф, представляющий объединение деревьев, называется лесом (рис. 6).

Рисунок 6 - Граф лес

 

При очень большом числе вершин и рёбер (дуг) для задания графов используются матрицы.

Для простоты рассмотрим орграф с однократными дугами (рис. 7).

 

Рисунок 7

 

Такой граф можно однозначно задать матрицей смежности вершин.

Это квадратная матрица n-го порядка (n – число вершин) с элементами

р_ij =1, если существует дуга (x_i; x_j),

р_ij =0, если такой дуги нет.

 

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

Полустепень захода P⁺(x_i) вершины х_i равна сумме элементов i-го столбца;

Полустепень исхода P^-(x_i) - сумме элементов i-й строки.

В табл. 1 приведена матрица смежности вершин.

 

Таблица 1 – Матрица смежности вершин

хi	x1	x2	x3	x4	x5	x6	P-(xi)
x1 x2 x3 x4 x5 x6
P+(xi)

 

Например, для вершины х₃: P⁺(x₃) = 2, P^-(x₃) = 1, так что P(x₃) = 3.

 

Дуга u_i непосредственно предшествует дуге u_j, если конец дуги u_i является началом дуги u_j.

 

Граф можно задать матрицей смежности дуг.

Это квадратная матрица m-го порядка (m – число дуг в графе) с элементами

q_ij =1, если дуга u_i непосредственно предшествует дуге u_j,

q_ij =0, в противном случае.

 

Матрица смежности дуг для графа приведена в табл. 2.

 

Таблица 2 – Матрица смежности дуг

ul	u1	u2	u3	u4	u5	u6	u7	u8
u1 u2 u3 u4 u5 u6 u7 u8