Реферат: Сетевые методы в планировании

Гамильтонов путь - путь проходящий через все вершины, но только по одному разу,

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

Длинна пути - число дуг последовательности (U₁ , U₂ , ...U_n ).

Ветвь - путь, в котором начальная и конечная вершины являются узлами. Дуга (x,y) называется замыкающей, если удаление ее не приводит к аннулированию пути из x в y.

Контур - конечный путь, начинающийся и заканчивающийся в одной и той же вершине. Контур единичной длинны называется петлей.

Ориентированный граф - граф, у которого вершины соединяются направляющими стрелками.

Графы можно рассматривать с учетом или без учета ориентации его дуг.

Разновидности графов

Нуль-граф - граф (X,U) , состоящий только из изолированных вершин.

Однородный граф - если степени всех вершин графа одинаковы и P⁺ (x)=P^- (x) =0.

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

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

Полный - граф, в котором любая пара вершин соединена одинаковым числом дуг.

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

Подмножества графов

Подграфом графа G(X,U) называется граф G(A,U_A ) , определяемый следующим образом:

1. Вершинами A подграфа G(A,U_A ) является некоторое подмножество вершин графа G(X,U);

2. Отображением каждой вершины подграфа является пересечение отображения той же вершины в графе G(X,U) со всем подмножеством вершин A подграфа G(A,U_A ).

Частичным графом для графа G(X,U) называется граф G(X,U) , в котором содержатся все вершины и некоторое подмножество дуг исходного графа.

Частичный подграф - это частичный граф от подграфа.

Фактором графа G(X,U) называется частичный граф G(X,U) , в котором каждая вершина обладает полустепенями исхода и захода, равными единице, имеются одна заходящая и одна исходящая дуги.

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

Связность графа

В общем случае граф может быть представлен несколькими отдельными графами, не имеющими общих дуг. Тогда граф G(X,U) называется несвязным, а каждый из составляющих его графов G₁ , G₂ ,...G_n - компонентами связности. Граф называется связным, когда каждую его вершину можно соединить с любой другой его вершиной некоторой цепью.

Операции над графами

1. Объединение графов

G₃ (X₃ ,Гх₃ ) = G₁ (X₁ ,Г1х₁ ) È G₂ (X₂ ,Г2х₂ ) , где X₃ =X₁ È X₂ , а Гx₃ =Г1x₁ È Г2x₂

Пример (Рис 1.1).

Рис 1.1

2. Пересечение графов

G₃ (X₃ ,Гх₃ ) = G₁ (X₁ ,Г1х₁ ) ÇG₂ (X₂ ,Г2х₂ ) , где X₃ =X₁ Ç X₂ , а Гx ₃ =Г1x₁ Ç Г2x₂

Пример (рис 1.2).

Рис 1.2

4. Прямое (декартово) произведение графов.

Прямым произведением множеств Х{x₁ .......x_n } и Y называется множество Z, элементами которого являются всевозможные пары вида x_i , y_j , где x_i ÎX, y_j ÎY. Обозначают: Z=X x Y.