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

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)=[a_{i j}], где a_{i j} =

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

Таблица 8.1.

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

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

либо –1.

B(G)=[b_{i j}], где b_{i j}=

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

Таблица 8.2.

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

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

С(G)=[с_{i j}], где с_{i j}=

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

Таблица 8.3.

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

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

Пример

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

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

Рис. 8.6.

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

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

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

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

Рис. 8.7

Рис. 8.9.

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.

Рис. 8.11.

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

п. 6 надо преодолеть 5+7=12 км.

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

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

Рис. 8.13.

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

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

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

Рис. 8.15.

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

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

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

Рис. 8.17.

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

Таблица 8.4.

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

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