Тема 2-2. Методы оптимизации на графах.

Методы оптимизации находят широкое применение при проектировании сложных систем обработки и передачи информации, в частности: вычислительных систем и сетей, сетей передачи и распределения электроэнергии, товаров и т.д.

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

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

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

Порядковая функция графа

Пусть задан граф G=(X,), а N₀, N₁, ... , N_r - такие подмножества, что:

N₀={x_i/x_i  X,  ^(-1)_xi=}

N₁={x_i/x_i  X-N₀,  ^(-1)_xi N₀}

N₂={x_i/x_i  X-(N₀  N₁),  ^(-1)_xi (N₀  N₁)}

.......................................................

N_r={x_i/x_i  X- N_k,  ^(-1)_xi N_k }

Суть задания множеств N₀, N₁, ... , N_r : в множество N₀ ни одна дуга не входит. В любое из оставшихся множеств могут входить дуги только из множеств, номера индексов которых меньше номера индекса рассматриваемого множества. Сказанное даёт возможность разбить всё множество вершин графа Х на (r +1) ярусов со связями между ярусами по типу "с предыдущего в последующие".

Графически множества N₀, N₁, ... , N_r могут быть проиллюстрированы так:

Функция О(х), определяемая равенством

(x_iN_k) (O(x_i)=k)

называется порядковой функцией графа без контуров.

Пример. Задан граф G.

Множество Х, можно, например, разбить на подмножества N₀, N₁, ... , N₃, т.е. задать порядковую функцию следующим образом:

Подмножества N₀, N₁, ... , N_r называются обычно уровнями.

Рассмотрим алгоритм нахождения уровней графа:

1. Задать граф матрицей смежности.

2. Образовать дополнительную к матрице смежности строку ₀, в каждой её клетке записать число единиц по соответствующему столбцу матрицы смежности. Вершины графа, соответствующие нулевым клеткам строки ₀, образуют подмножество N₀.

3. Вычеркнуть из матрицы смежности строки, соответствующие вершинам графа, вошедшим в N₀.

4. Образовать дополнительную строку ₁ , заменив в ней нулевые клетки строки ₀ крестиками. В остальные клетки строки ₁ вписать число единиц по соответствующему столбцу матрицы смежности графа. Вершины графа, соответствующие нулевым клеткам строки ₁ , образуют подмножество N₁.

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

Пример. Задан граф G (из предыдущего примера).

	1	2	3	4	5	6	7
1		1	1	1		1
2					1
3					1	1	1
4						1
5							1
6							1
7

0

0

1

1

1

2

3

3

N₀={1}

1

Х

0

0

0

2

2

3

N₁={2,3,4}

2

Х

Х

Х

Х

0

0

2

N₂={5,6}

3

Х

Х

Х

Х

Х

Х

0

N₃={7}

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