Основы дискретной математики - Методичка

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ САНКТ-ПЕТЕРБУРГСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ СЕРВИСА И ЭКОНОМИКИ КАФЕДРА «МАТЕМАТИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ В ЭКОНОМИКЕ»В работе рассмотрены основные понятия теории графов и ее приложения к исследованию линейных систем и задачам минимизации и сетевого планирования. Рассмотрены с подробными объяснениями примеры решения задач различной сложности. Имеются задачи для самостоятельной работы. Данные методические указания предназначены для самостоятельной работы студентов всех специальностей дневной и заочной форм обучения.§2. ДЕРЕВЬЯ, ОСТОВЫ, РАЗРЕЗЫ...............................................5ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ Графом называется совокупность точек, называемых вершинами, и соединяющих их линий, которые называются ребрами. 1 изображен граф, у которого 5 вершин и 7 ребер. Вершина и ребро называются инцидентными друг другу, если вершина является для этого ребра концевой точкой. Две вершины, являющиеся концевыми для некоторого ребра, называются смежными вершинами. Граф называется полным, если любые две его различные вершины соединены ребром, и он не содержит параллельных ребер.Граф называется ориентированным, или орграфом, если на каждом ребре задано направление, т. е. у каждого ребра фиксируются начало и конец. Цепью в орграфе называется такая последовательность дуг, в которой каждые две соседних дуги имеют общую вершину и никакая дуга не встречается более одного раза. Если направление цепи совпадает с направлением всех принадлежащих ей дуг, то цепь называется путем. 3 дуги (e1, e4, e5) образуют цепь, а дуги (e1, e2, e5) - путь. Элемент aij, соответствующий вершине vi и 7 ребру ej, равен 1, если вершина является начальной для ребра,-1 - если конечной, 2 - если и то и другое (т.е. если ej - петля в вершине vi), 0 - в остальных случаях.Узлы связаны направленными линиями, по которым они могут принимать или передавать сигналы другим узлам. Каждая линия характеризуется величиной, которая называется передачей, и определяется как отношение сигнала на выходе линии к сигналу на ее входе. Узел называется зависимым, если имеет одну или несколько входящих линий. Наличие выходящих линий из узла i не влияет на сигнал этого узла xi (они влияют на сигналы других узлов). Такую систему можно представить в виде некоторого орграфа (сети), в котором узлам системы соответствуют вершины, линиям связи - дуги, направление которых соответствует направлению передачи сигнала.Исключению зависимых переменных из системы уравнений соответствуют преобразования орграфов, позволяющие заменить последовательные и параллельные пути отдельными ветвями и, таким образом, упростить орграф. 11. 5.Исключение петли, когда к узлу подходит и из него отходит по одной ветви (рис. Пусть, например, надо удлинить вершину 2 графа, приведенного на рис. В результате получим граф, изображенный на рис. Соответствующий ему граф показан на рис.Например, для вершины k : N xk aki xi , (1) i 1 где N - число вершин графа, aki - передачи входящих в вершину k ребер (если в ней нет входящего ребра от какой-то вершины i, то соответствующая передача aki считается равной нулю). 16 дом узле переменная определяется формулой (1), то граф соответствует системе линейных уравнений xj N aji xi , где j 1,?,N . (Здесь i - номер строки, j - номер столбца, т.е. в стро-i, j 1 ки записываются передачи к данному узлу от всех вершин, а в столбцы - от данного узла ко всем узлам). Однако чтобы задать в матрице А определенное расположение строк и столбцов, первым по порядку n точкам сопоставляются зависимые узлы, а оставшимся m точкам - независимые (если необходимо составлять матрицу А). Передачи ребер графа по заданной системе можно определять двумя способами, каждый из которых приводит к своему графу, которые являются равносильными.Расстоянием d(u,v) от вершины u до вершины v называется длина кратчайшего пути из u в v. На множестве пар вершин (u,v) введем функцию L(u,v) следующим образом: L(u,v)= ?(e), если e - дуга с началом в u и концом в v, ? - если такой дуги не существует. Выбрать в S вершину w, для которой величина d(v) минимальна, и положить S:=S\{w}, т.е. окрасить вершину w. Окрасить дугу, ведущую в вершину w из вершины, которая была взята в качестве y последний раз, когда в менялось значение d для вершины w . 37, найти расстояния от вершины v0 до остальных вершин и построить дерево кратчайших путей с корнем в v0 .Использование этого метода позволяет сравнительно просто выяснить, когда необходимо начинать и заканчивать выполнение отдельных операций, как задержка хода выполнения некоторой операции влияет на время завершения всего проекта. Временем наступления события считают время, когда завершено выполнение всех операций, входящих в соответствующую вершину. Ранним сроком начала работы называют наименьшее допустимое время, когда работа может быть начата. Если из вершины vi выходит несколько работ, то ранние сроки начал этих работ совпадают и называются ранним сроком наступления события vi.