Способы описания и задания графов
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 = Построим матрицу смежности для графа рис.8.5. Таблица 8.1.
4) Матрица инцидентности. Если G=<V, X> – ориентированный граф, где V – совокупность вершин (n вершин), а X – совокупность дуг (m дуг), то матрицей инцидентности этого графа называется матрица B(G), размера n × m, где элемент матрицы либо 1, либо 0, либо –1. B(G)=[bi j], где bi 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.
Сетевой график Сетевой график — это динамическая модель производственного процесса, отражающая технологическую зависимость и последовательность выполнения комплекса работ, увязывающая их свершение во времени с учетом затрат ресурсов и стоимости работ с выделением при этом узких (критических) мест. Примером сетевого графика может быть граф, вершины которого отображают состояния некоторого объекта (например, строительства), а дуги — работы, ведущиеся на этом объекте. Каждой дуге сопоставляется время, за которое осуществляется работа и/или число рабочих, которые осуществляют работу. Часто сетевой график строится так, что расположение вершин по горизонтали соответствует времени достижения состояния, соответствующего заданной вершине. Основными элементами сетевого графика являются: работа, события, пути.
Работа
Работа отражает трудовой процесс, в котором участвуют люди, машины, механизмы, материальные ресурсы (проектирование сооружения, поставки оборудования, кладка стен, решение задач на ЭВМ и т. п.) либо процесс ожидания (твердение бетона, сушка штукатурки и т. п.). Каждая работа сетевого графика имеет конкретное содержание.
Виды работ · действительная работа в прямом смысле слова (например — подготовка трассы соревнований), требующая затрат труда, материальных ресурсов и времени; · ожидание — работа не требующая затрат труда и материальных ресурсов, но занимающая некоторое время; · фиктивная работа (зависимость) — связь между двумя или более событиями, не требующая затрат труда, материальных ресурсов и времени, но указывающая, что возможность начала одной операции непосредственно зависит от выполнения другой. Продолжительность такой работы = 0. Фиктивные работы изображают штриховыми линиями в виде дополнительных дуг и используют для правильного и наглядного отображения порядка предшествования работ при построении сети. Всякая работа в сети соединяет два события: предшествующее (являющееся для нее начальным) и следующее за ней (конечное).
Событие
Событие выражает факт окончания одной или нескольких непосредственно предшествующих (входящих в событие) работ, необходимых для начала непосредственно следующих (выходящих из события) работ. Событие, стоящее в начале работы, называется начальным, а в конце – конечным.
Виды событий · исходное событие — начало выполнения комплекса работ; · завершающее событие — конечное событие, означающее достижение конечной цели комплекса работ; · промежуточное событие, как результат одной или нескольких работ, представляющих возможность начать одну или несколько непосредственно следующих работ. Продолжительность промежуточного события во времени всегда = 0. В исходное событие сетевого графика не входит, а из завершающего не выходит ни одна работа. В отличие от работ, события совершаются мгновенно без потребления ресурсов. Следует отметить, что событие определяет состояние, а не процесс.
Пути
Любая последовательность работ в сетевом графике, в котором конечное событие каждой работы этой последовательности совпадает с начальным событием следующей за ней работой, называется путем. Виды пути
· путь, следующий за событием — путь, соединяющий событие с завершающим событием;
Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь наибольшей длины между исходными и завершающими событиями называется критическим (Lm). Если критическое время не соответствует заданному или нормативному, сокращение сроков производственного процесса необходимо начинать с сокращения продолжительности критических работ.
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (451)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |