Упорядочение элементов орграфа. Алгоритм Фалкерсона
Расчеты в задачах с графами заметно упрощаются, если их элементы упорядочены.
Вершина xi предшествует вершине xj, если существует путь из xi в xj (xj называется последующей).
Под упорядочением вершин связного орграфа без контуров понимают такое разбиение его вершин на группы, при котором:
вершины первой группы не имеют предшествующих, а вершины последней – последующих;
вершины каждой другой группы не имеют предшествующих в следующей группе;
вершины одной группы дугами не соединяются.
Аналогично вводится понятие упорядочения дуг.
В результате получается граф, изоморфный данному.
Графический способ упорядочения вершин (алгоритм Фалкерсона):
Находят вершины, в которые не входит ни одна дуга (I группа). Нумеруют их в натуральном порядке.
Мысленно вычеркивают все пронумерованные вершины и дуги, из них выходящие.
В полученном графе находят вершины, в которые не входит ни одна дуга (II группа). Их нумеруют соответствующими номерами.
И т.д., пока не будут пронумерованы все вершины.
Аналогично упорядочивают дуги орграфа:
Находят дуги, которые не имеют предшествующих дуг (I группа).
Вычеркивают найденные дуги.
Находят дуги, которые не имеют непосредственно предшествующих (без дуг I группы). Они составляют II группу.
И т.д. пока все дуги не будут разбиты на группы.
Пример 3. Упорядочить вершины данного графа и построить изоморфный граф.
Решение.
|
В вершину х6 не входит ни одна дуга, т.е. х6 не имеет предшествующих вершин. Поэтому относится к I группе. Исключаем х6 и дуги, исходящие из нее. Далее х2 и х4 не имеют предшествующих вершин – II группа. х3, х5 – III группа. х1 – IV группа; х7 – V гр.
|
Строим новый граф.
|
|
Тема 2. Сетевое планирование и управление в.1. Сетевая модель и её основные элементы
Сетевая модель – план выполнения некоторого комплекса взаимосвязанных работ, заданного в форме сети, графическое изображение которой называется сетевым графиком.
Главными элементами сетевой модели являются события и работы.
Работа – это любые действия, требующие затрат ресурсов и времени.
Выделяют виды работ:
- действительная работа – протяжённый во времени процесс, требующий затрат ресурсов;
- ожидание – протяжённый во времени процесс, не требующий затрат труда;
- зависимость (фиктивная работа) – логическая связь между работами, не требующая затрат. Показывает, что возможность одной работы зависит от результатов другой. Её протяжённость равна нулю.
Событие – это результат завершения одной или нескольких работ.
Любая работа на сети может быть определена двумя событиями, между которыми она находится. Предполагается, что событие не имеет продолжительности и свершается мгновенно. Событие является предпосылкой для выполнения работ, следующих за ним. Событием может начинаться или заканчиваться сразу несколько работ.
Среди событий сети особое место занимают исходное, которое не имеет предшествующих работ и событий, и завершающее, которое не имеет последующих работ и событий.
Работы на сети изображаются стрелками произвольной длины, а события – кружками.