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

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

G₁ (X,Гх)=G₁ (X₁ ,Гх₁ ) G₂ (Y,Гy)= G₂ (X₂ ,Гх₂ )

X={x₁ x₂ x₃ } Y={y₁ y₂ }

Гх₁ =0 Гу₁ ={y₁ y₁ }

Гх₂ ={x₁ x₃ } Гу₂ ={y₁ }

Гх₃ =0

Z=X x Y={x ₁ y₁ , x₁ y₂ , x₂ y₁ , x₂ y₂ , x₃ y₁ , x₃ y₂ }

Z={z₁ z₂ z₃ z₄ z₅ z₆ }

Рис 2.3

7. Расширение графа.

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

8. Сжатие графа.

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

9. Стягивание графа.

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

Некоторые числа теории графов

Пусть существует мультиграф с b вершинами, p ребрами, и R компонентами связности, тогда цикломатическое число мультиграфа определяется равенством:

V= p-b+R

Матрицы для графов

Матрицей смежности графа G(X,Гх) , содержащего n вершин называется квадратная бинарная матрица А(G) n x n , c нулями на диагонали. Число единиц в строке равно степени соответствующей вершины.

Матрицей инциденций ориентированного графа G(X,U) называется прямоугольная матрица порядка [m x n] n - мощность множества Х, m - мощность множества U. Каждый элемент которой определяется следующим образом:

1, если х_i - начало дуги U_j

a_ij = -1, если х_i - конец дуги U_j

0, если х_i - не инцидентна дуге U_j

Пример.

Построим матрицы смежности (М1) и инциденций (М2) для графа G(X,U) (рис 2.1).

Рис 2.1

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

Деревья и прадеревья

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

Прадрево - ориентированное дерево.

Корень прадерева - вершина у которой Р⁺ (х)=0 .

Глава 2

Календарное планирование программ сетевыми методами