Способы описания и задания графов

1) Графический.

Данный способ задания подразумевает схематическое изображение графа на рисунке с указанием всех необходимых данных. В качестве примера можно привести

рис. 8.1 – 8.5.

2) Перечисление всех вершин и дуг.

Вершины: 1, 2, 3, 4, 5, 6.

Дуги: x1 <1, 2>, x2 <1, 3>, x3 <2, 5>, x4 <2, 4>, x5 <3, 6>, x6 <4, 6>, x7 <5, 6>.

3) Матрица смежности.

Если G=<V, X>, где V – совокупность вершин (n вершин), а X – совокупность дуг, то матрицей смежности этого графа называется квадратная матрица А(G) порядка n × n, где элемент матрицы либо 0, либо 1, в зависимости от того, смежны ли вершины.

A(G)=[ai j], где ai j = способы описания и задания графов - student2.ru

Построим матрицу смежности для графа рис.8.5.

Таблица 8.1.

A(G)

4) Матрица инцидентности.

Если G=<V, X> – ориентированный граф, где V – совокупность вершин (n вершин), а X – совокупность дуг (m дуг), то матрицей инцидентности этого графа называется матрица B(G), размера n × m, где элемент матрицы либо 1, либо 0,

либо –1.

B(G)=[bi j], где bi j= способы описания и задания графов - student2.ru

Построим матрицу инцидентности для графа рис. 8.5.

Таблица 8.2.

B(G) дуги вершины
-1
-1
-1
-1
-1 -1 -1

5) Матрица длин дуг.

Если G=<V, X> – ориентированный граф, где V – совокупность вершин (n вершин), а X – совокупность дуг, то матрицей длин дуг этого графа называется матрица С(G), размера n × n, где элемент матрицы это значения весовой функции для каждой из дуг или ребер.

С(G)=[сi j], где сi j= способы описания и задания графов - student2.ru

Построим матрицу длин дуг для графа рис. 8.5.

Таблица 8.3.

C(G)

Задача нахождения кратчайшего пути

Рассмотрим решение задачи нахождения кратчайшего пути методом «волны».

Пример

Допустим, в п. 1 находится склад, а в остальных пунктах – строительные площадки компании (рис. 8.6).

способы описания и задания графов - student2.ru Показатели на дугах – расстояния в километрах. Надо найти кратчайшие расстояния от склада до каждой строительной площадки.

Рис. 8.6.

Первый пункт является стартовым и ему присваивается постоянная метка.

Постоянная метка присваивается тем пунктам, если для них определено кратчайшее расстояние.

1) рассмотрим каждый пункт, в который можно попасть непосредственно из пункта 1.

способы описания и задания графов - student2.ru До п. 2 расстояние в 3 км, до п. 3 – 8 км. Т.о. пунктам 2 и 3 присвоены временные метки [3,1] и [8,1] соответственно (рис. 8.7). Первое число в метке обозначает расстояние от п.1, второе число – это номер пункта, из которого непосредственно «пришли» в рассматриваемый пункт. Далее рассматриваются все временные метки на предмет нахождения метки с минимальным расстоянием. На данный момент это метка [3,1]. Пункту 2 присваиваем постоянную метку и фиксируем дугу из п.1 в п.2 (рис. 8.9).

Рис. 8.7

способы описания и задания графов - student2.ru

Рис. 8.9.

способы описания и задания графов - student2.ru 2) теперь рассматриваются все пункты, которые ещё не имеют постоянных меток и непосредственно связаны с пунктом 2, т.е. мы рассматриваем п. 4 и п. 5. Достичь п. 4 можно, преодолев 3+2=5 км., а п. 5 – преодолев 3+5=8 км. Т.о. п. 4 и п. 5 присваиваются временные метки [5,2] и [8,2] соответственно (рис.8.10). Теперь снова рассматриваем временные метки и выбираем из них ту, которая имеет в своём обозначении кратчайшее расстояние, т.е. метку [5,2] для п.4. Эта метка теперь получает статус постоянной и фиксируем дугу из п.2 в п.4 (рис.8.11).

Рис. 8.10.

способы описания и задания графов - student2.ru

Рис. 8.11.

3) следующий этап начинается в п. 4, последнем, помеченном постоянной меткой. Как и раньше, рассматриваем каждый пункт без постоянной метки, в который можно попасть непосредственно из п. 4. В этом случае, это единственный п. 6. Для того, чтобы достичь

способы описания и задания графов - student2.ru п. 6 надо преодолеть 5+7=12 км.

Временная метка пункта 6 будет иметь вид [12,4] (рис. 8.12). Среди всех временных метках, которые имеются на данный момент, выбираем ту, которой соответствует наименьшее количество километров. Таких пунктов два: п. 5 и п. 3 ( до каждого из них длина равна 8 км.). Выбираем любой из этих пунктов, например, п. 5. Эта метка

Рис.8.12. фиксируется как и путь из п. 2 в п. 5 (рис. 8.13).

способы описания и задания графов - student2.ru

Рис. 8.13.

способы описания и задания графов - student2.ru 4) теперь рассмотрим пункты, в которые можно попасть из п. 5. Таковым является только п. 6, имеющий уже временную метку. Добавляем к этой временной метке ещё одну, относящуюся к п. 5 (рис. 8.14).

Из имеющихся трёх временных меток опять выбираем ту, в которой указано минимальная длина пути от п. 1 до данного пункта. Таковой меткой является

Рис. 8.14 метка [8,1] для п. 3. Эти пункт и метка получают статус стационарных и путь из п. 1 в п. 3 фиксируется (рис. 8.15).

способы описания и задания графов - student2.ru

Рис. 8.15.

способы описания и задания графов - student2.ru 5) из фиксированного п. 3 можно попасть в п. 6, у которого уже есть две временные метки, но нет постоянной. Добавляем п. 6 ещё одну временную метку [17,3] (рис. 8.16). Т. о. п. 6 имеет три временные метки, т. е. до п. 6 можно пройти тремя путями различной длины. Выбираем наикратчайший путь. Таких пути два: через п. 5 и через п. 6. Выбираем любой, потому что длина их одинаковая. Пусть это будет путь,

проходящий через п. 4. Тогда фиксируем

Рис. 8.16 метку [12,4], п. 6 и путь из п. 4 в п. 6 (рис.8.17).

способы описания и задания графов - student2.ru

Рис. 8.17.

Теперь можно использовать информацию в постоянных метках для нахождения кратчайшего пути из п. 1 в любой другой пункт. Например, кратчайший путь из п. 1 в п. 4 есть путь 1 – 2 – 4 и длина его 5 км. Используя этот подход, можно определить кратчайшие пути применительно ко всей сети компании, состоящей из её строительных площадок.

Таблица 8.4.

Пункт Кратчайший путь из п.1 Расстояние, км.
1 – 2 1 – 3 1 – 2 – 4 1 – 2 – 5 1 – 2 – 4 – 6

Сетевой график

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

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

Основными элементами сетевого графика являются: работа, события, пути.

Работа

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

Виды работ

· действительная работа в прямом смысле слова (например — подготовка трассы соревнований), требующая затрат труда, материальных ресурсов и времени;

· ожидание — работа не требующая затрат труда и материальных ресурсов, но занимающая некоторое время;

· фиктивная работа (зависимость) — связь между двумя или более событиями, не требующая затрат труда, материальных ресурсов и времени, но указывающая, что возможность начала одной операции непосредственно зависит от выполнения другой. Продолжительность такой работы = 0.

Фиктивные работы изображают штриховыми линиями в виде дополнительных дуг и используют для правильного и наглядного отображения порядка предшествования работ при построении сети.

Всякая работа в сети соединяет два события: предшествующее (являющееся для нее начальным) и следующее за ней (конечное).

Событие

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

Виды событий

· исходное событие — начало выполнения комплекса работ;

· завершающее событие — конечное событие, означающее достижение конечной цели комплекса работ;

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

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

Следует отметить, что событие определяет состояние, а не процесс.

Пути

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

Виды пути

  • полный путь — начало которого совпадает с исходным событием сети, а конец — с завершающим, называется полным путем;
  • путь, предшествующий событию — путь от исходного события сети до данного события;

· путь, следующий за событием — путь, соединяющий событие с завершающим событием;

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

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

Если критическое время не соответствует заданному или нормативному, сокращение сроков производственного процесса необходимо начинать с сокращения продолжительности критических работ.

Наши рекомендации