metod_15.03.04_atppp_moas_tg_2016 (Методические документы)

МИНОБРНАУКИ РОССИИФедеральное государственное бюджетное образовательное учреждение высшегообразо-вания«Московский технологический университет»МИРЭАСОГЛАСОВАНОУТВЕРЖДАЮУчебно-методический советДиректор Института информационныхИнститута информационных технологийтехнологий____________________«____» ______________ 2016 г.____________________А.С. Зуев«____» ______________ 2016 г.«Математические основы автоматизированныхсистем»ПРИМЕНЕНИЕ АППАРАТА ТЕОРИИ ГРАФОВДЛЯ РЕШЕНИЯ ЗАДАЧ СЕТЕВОГО ПЛАНИРОВАНИЯУчебное пособие по дисциплинеНаправление подготовки:15.03.04«Автоматизация технологических процессов и производств»Профиль подготовки:«Автоматизация технологических процессов и производств впромышленности»Составители:к.т.н., доцент Каширская Е.Н.,студент Кузнецова А.А.Москва 20161СОДЕРЖАНИЕ1.ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ .........................................................32.СПОСОБЫ ЗАДАНИЯ ГРАФОВ ..............................................................................83.СВЯЗНОСТЬ, ПУТИ, ЦИКЛЫ В ГРАФАХ ...........................................................104.ИЗОМОРФИЗМ ГРАФОВ .......................................................................................145.ОБЗОР ЗАДАЧ ТЕОРИИ ГРАФОВ ........................................................................166.СЕТЕВОЕ ПЛАНИРОВАНИЕ И УПРАВЛЕНИЕ ПРОЦЕССОМ ......................187.ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ СЕТЕВЫХ МОДЕЛЕЙ...............198.ВРЕМЕННЫЕ ПАРАМЕТРЫ СОБЫТИЙ .............................................................229.ВРЕМЕННЫЕ ПАРАМЕТРЫ РАБОТ И ПУТЕЙ .................................................2310.ПРИМЕР ПОСТРОЕНИЯ И РАСЧЕТА СЕТЕВОЙ МОДЕЛИ ............................2511.ОПТИМИЗАЦИЯ СЕТЕВЫХ МОДЕЛЕЙ ПО КРИТЕРИЮ «МИНИМУМИСПОЛНИТЕЛЕЙ» ....................................................................................................................2712.ПРИМЕР ПРОВЕДЕНИЯ ОПТИМИЗАЦИИ ПО КРИТЕРИЮ «МИНИМУМИСПОЛНИТЕЛЕЙ» ....................................................................................................................2813.ЗАДАНИЕ И ВАРИАНТЫ.......................................................................................3314.СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ ...............................................3921.

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВГрафы являются существенным элементом математических моделей всамых разнообразных областях науки и практики. Они помогают нагляднопредставить взаимоотношения между объектами или событиями в сложныхсистемах. Многие алгоритмические задачи дискретной математики могутбыть сформулированы как задачи, так или иначе связанные с графами,например задачи, в которых требуется выяснить какие-либо особенностиустройства графа, или найти в графе часть, удовлетворяющую некоторымтребованиям, или построить граф с заданными свойствами.В теории графов нет устоявшейся терминологии.

В различных источниках одни и те же термины означают разные вещи. Мы будем использоватьнаиболее часто встречающиеся определения.Обычно под графом понимается совокупность непустого множествавершин и наборов пар вершин, которые характеризуют связи между вершинами.Граф(неориентированный)G=(V, U)- непустое множество V и U- некоторый набор пар элементов из V. Элементы множества V называются вершинами, а элементы набора U– ребрами.1BA2C34DE5Рисунок 1.1 – Связный неориентированный не взвешенный граф.Вершины и рёбра графа называются также элементами графа, числовершин в графе |V| —порядком, число рёбер |U| —размером графа.3Подграф - граф, все вершины и ребра которого содержатся среди вершин и ребер графа G.Связный граф - граф, у которого для любых двух различных вершинсуществует цепь (последовательность смежных вершин), соединяющая их.Взвешенный связный граф - связный граф, с заданной весовой функцией (каждому элементу набора U ставится в соответствие некоторое число вес ребра).Дерево - связный граф, не содержащий циклов.Остов - остовный подграф, являющийся деревом.

Остовный подграфсодержит все вершины графа G.Вершины А и В называются концевыми вершинами (или просто концами) ребра u= {А,В}. Ребро, в свою очередь, соединяет эти вершины. Двеконцевые вершины одного и того же ребра называются соседними.В графе допускаются кратные ребра. Граф с кратными ребрами называют также мультиграфом.Смежными называются различные дуги (ребра), имеющие общую граничную точку.

Две вершины А и В смежны, если они различны и существуетдуга, идущая от одной из них к другой.Вершина называется изолированной, если она не соединена дугами сдругими вершинами графа.Два ребра называются смежными, если они имеют общую концевуювершину.Два ребра называются кратными, если множества их концевых вершинсовпадают.Ребро называется петлёй, если его концы совпадают, то есть u= {A,A}.При расчете степени вершины петли считаются дважды.Вершина называется изолированной, если она не является концом нидля одного ребра.Вершина называется висячей(или листом), если она является концомровно одного ребра.4Ориентированный граф (кратко орграф) — граф, рёбрам которого присвоено направление.

В этом случае ребра принято называть дугами.Таким образом, можно сформулировать, что ориентированный граф— это упорядоченная пара G=(V, U),гдеV— это непустое множество вершин или узлов,U— это множество пар различных ребер, называемых дугами или ори-ентированными рёбрами.1BA2C34DE5Рисунок 1.2 – Ориентированный граф.В этом случае дуга является упорядоченной парой вершин {x,y}, в которой вершина x является началом, вершина y – концом дуги.

Таким образом,дуга A Bведет от вершины A к вершине B.Смешанный графG— это граф, в котором некоторые рёбра могут бытьориентированными, а некоторые — неориентированными.1BA2C34DE5Рисунок 1.3 – Смешанный граф.Ориентированный и неориентированный графы являются частнымислучаями смешанного.5Сетью называется конечный граф G(V,U) , без циклов и петель, ориентированный в одном общем направлении от вершин A, являющимися входами графа, к вершинам Z, являющимися выходами.Если множество U ребер графа пусто, граф называется пустым.BACEDРисунок 1.4 – Пустой граф.Если пусто не только множество U ребер, но и множество V вершинграфа, граф называется нуль-графом.

Пустой граф, имеющий лишь однувершину, называется тривиальным графом.Рисунок 1.5 – Тривиальный граф (изолированная вершина).Каждому неориентированному графу соответствует ориентированныйграф с тем же множеством вершин, в котором каждое неориентированноеребро исходного графа заменено двумя противоположно направленными дугами.

Такое соответствие между неорграфом и орграфом называют каноническим.а) неориентированныйб) ориентированный6графграфРисунок 1.6 – Каноническое соответствие неорграфа и орграфаГраф может содержать одновременно как ребра, так и дуги. Получениеканонического представления такого графа сводится к замене ребер двумяпротивоположно направленными дугами без изменения имевшихся дуг.Например, графом такого типа будет изображение вершинами населенныхпунктов и развилок дорог, а ребрами и дугами – дорог, соответственно, сдвусторонним и односторонним движением.Если дуга x исходит из вершины Aили заходит в A, то дуга x называетсяинцидентной вершине A, а вершинаA - инцидентной дуге x. Общее число дуг,инцидентных вершине A, называется степенью вершины A и обозначаетсяdegA.

Вершины, степень которых degA>2, называются узлом, а со степеньюdegA<2 - антиузлом.В орграфах используются также понятия «полустепень исхода» и «полустепень захода» для обозначения числа исходящих из вершины дуг и заходящих в нее, соответственно. Вершину степени 0 называют изолированной, авершину степени 1 - висячей. Висячим называют и ребро, инцидентное висячей вершине.Теорема. Сумма степеней вершин графа равна удвоенному числу егоребер.Доказательство.

Каждое ребро графа инцидентно двум вершинам.Следовательно, каждое ребро добавляет 2 в сумму степеней вершин графа,что соответствует утверждению теоремы.Следствие. Число вершин нечетной степени в любом графе четно.Доказательство. Согласно теореме, сумма степеней вершин графачетна. Так как сумма четных степеней вершин тоже четна, то для четностисуммы степеней всех вершин число вершин нечетной степени должно бытьчетно.7Граф называется однородным, если все его вершины имеют одинаковую степень.Однородный граф степени 0 не имеет ребер (пустой граф). Однородный граф степени 1 имеет одно ребро в каждой компоненте.

Однородныйграф степени 2 имеет в качестве компонент циклы. Однородные графы степени 3 принято называть кубическими. На рисунке 1.7 приведены примерыкубических графов.Рисунок 1.7 – Кубические графы.Каждый кубический граф имеет четное число вершин.2. СПОСОБЫ ЗАДАНИЯ ГРАФОВСуществует ряд способов задания графов.Наиболее наглядным является способ задания графов с помощью рисунка.Еще одним способом является задание графа списками смежности, вкоторых каждый i-ый список содержит номера вершин, смежных i-ой вершине.

Списки смежности удобны для программного использования и ввода вкомпьютер, экономят память, но не могут использоваться в случае взвешенного графа. Этот способ задания графов подразумевает, что для каждой вершины будет указан список всех смежных с нею вершин (для орграфа - списоквершин, являющихся концами исходящих дуг).Иерархический список - это способ представления графов, являющийсявсего лишь внутренней реализацией списка смежности: в одном линейном8списке содержатся номера «начальных вершин», а в остальных - номерасмежных вершин или указатели на эти вершины.Матрица смежности - матрица размеромn×n, элементы которой равны1, если i-ая вершина смежна с j-ой, и 0 в противном случае. В ней как столбцы, так и строки соответствуют вершинам графа.Для неориентированного графа матрица смежности является симметричной. Для случая взвешенного графа вместо 1 используется значение весовой функции, и такая матрица называется матрицей весов.ПустьG = (V, U) – орграф, где V={v1, v2, …,vn}, U={x1, x2, …, xm}.Матрицей смежности орграфа G называется квадратная матрица A(G)=[aij] порядка n, у которойМатрица инцидентности- матрица размером n  m (n- число вершин, mчисло ребер), элементы которой равны 1, если i-я вершина инцидентна j-муребру, и 0 в противном случае.Матрица инцидентности она не несет прямой информации о ребрах.Матрицей инцидентности неориентированного графа G называетсяматрица размерности n×m –матрица B(Ш)=[bij], у которойМатрицей инцидентности орграфа D называется матрица размерностиn×m –матрица B(D)=[bij], у которойС помощью введенных матриц удобно задавать графы для обработкина компьютере.

Используя матрицу смежности, легко определить локальные9степени вершин графа: сумма элементов матрицы по строке равна локальнойстепени соответствующей вершины. Для орграфов по строке определяютсяполустепени исхода, по столбцам – полустепени захода.Пример.Построить матрицы смежности и инцидентности для графа G = (V, U),изображённого на рисунке 2.1.Решение.Рисунок 2.1 – Неориентированный граф.Матрица смежности имеет вид:.Поскольку граф не имеет петель, то на главной диагонали стоят все нули.