Математические модели и алгоритмы на графах с нестандартной достижимостью. Динамические графы

Теорема 1.4.1. Пусть – динамический граф, . Пусть – путь из вершины в вершину , – путь из вершины в вершину . Тогда для того, чтобы существовал путь из вершины в вершину , необходимо и достаточно выполнения условия . Также рассмотрены периодические динамические графы , для дуг которых промежутки активности отличаются на некоторое натуральное число , называемое периодом. Во второй главе описаны алгоритмы построения вспомогательных графов для графов с ограниченными магнитными, монотонными достижимостями и для периодических динамических графов. Построение вспомогательного графа является методом сведения достижимости на графах с ограничениями к достижимости на обыкновенных ориентированных графах. Вспомогательный граф имеет больше вершин и дуг, но его можно рассматривать как обычный орграф со стандартной достижимостью. Для графов с ограниченными магнитными достижимостями доказаны теоремы о взаимнооднозначном соответствии между допустимыми путями на исходном графе с ограничениями и путями на вспомогательном графе: Теорема 2.1.1. Пусть ­– граф с магнитной достижимостью, – граф, построенный по графу . На графе существует допустимый путь из вершины в вершину тогда, и только тогда, когда на графе существует путь из вершины в одну из вершин или . Теорема 2.2.1. На графе с монотонной достижимостью существует допустимый путь из вершины в вершину тогда, и только тогда, когда на графе существует путь из вершины в подмножество вершин . Для периодических динамических графов получена теорема о соответствии между дугами на исходном и вспомогательном графах: Теорема 2.3.1. На вспомогательном графе дуге в момент времени соответствует дуга , такая, что , если ; , если ; , если . Справедливость теоремы следует из правила построения вспомогательного графа . Из алгоритма построения вспомогательного графа следует, что в случае периодических динамических графов дискретное время можно разделить на два промежутка: конечный «подготовительный», и бесконечный периодический. Третья глава посвящена задаче о максимальном потоке для графов с введенными типами ограничений. Для таких графов введено понятие сети, потока, магнитного и монотонного разрезов. Доказаны теоремы, являющиеся аналогами теоремы Форда-Фалкерсона для графов с ограниченными магнитными и монотонными достижимостями: Теорема 3.2.1. Величина максимального потока в сети равна пропускной способности минимального магнитного разреза, т.е. существует поток , такой что . Теорема 3.3.1. Величина максимального потока в сети равна пропускной способности минимального монотонного разреза, т.е. существует поток , такой что . На графах с ограниченными магнитными и монотонными достижимостями не все пути являются допустимыми, поэтому классические алгоритмы поиска максимального потока к таким графам неприменимы. Для решения потоковой задачи на таких графах предлагается искать максимальный поток на вспомогательном графе. Для каждого вида достижимости приведены соответствующие алгоритмы. В процессе построение вспомогательного графа возникает вопрос о переносе пропускной способности дуги исходного графа на порожденные ею дуги вспомогательного графа. Если положить пропускную способность каждой порожденной дуги равной пропускной способности исходной дуги, то возможна ситуация, когда по дуге исходного графа проходит поток, величина которого больше, чем пропускная способность данной дуги. Для решения этой проблемы введено понятие множества связанный дуг (т.е. дуг, порожденных одной и той же дугой исходного графа), и вместо пропускных способностей отдельных дуг рассматривается суммарная пропускная способность множества связанных дуг. Для решения задачи о максимальном потоке для графов со связанными дугами описан алгоритм прорыва. Показано что алгоритм поиска максимального потока с применением вспомогательного графа является более эффективным, чем поиск максимального потока без использования вспомогательного графа. Для периодических динамических графов введены определения периодической динамической сети и динамического потока. Определена величина динамического потока, исходящего из источника в момент времени и величина динамического потока, приходящего в сток к моменту времени . Определение 3.4.3. В периодической динамической сети величиной динамического потока, исходящего из источника в момент времени , в сток называется . Максимальным динамическим потоком, исходящим из источника в момент времени , в сток называется динамический поток, для которого величина максимальна (обозначим ее ). Определение 3.4.4. В периодической динамической сети величиной динамического потока из источника , приходящего в сток в момент времени , называется . Максимальным динамическим потоком из источника , приходящим в сток в момент времени , называется динамический поток, для которого величина максимальна (обозначим ). Различие между этими величинами заключается в том, что в первом случае источник рассматривается в одно и то же время , тогда как в сток динамический поток может «прийти» в любой момент времени . Во втором случае, наоборот, известен момент , в который динамический поток «приходит» в сток, но начальные моменты времени при этом могут быть различными. Описаны модифицированные алгоритмы Форда-Фалкерсона для поиска указанных величин максимальных потоков на исходном динамическом графе, а также алгоритм нахождения этих величин на вспомогательном графе. Получены теоремы о постоянстве величин максимальных потоков на периодическом участке: Теорема 3.4.1. Пусть – периодическая динамическая сеть с характеристикой , – источник и сток в сети . Тогда . Теорема 3.4.2. Пусть выполняются условия теоремы 3.4.1. Тогда . Введено понятие суммарных максимальных потоков и формулируются теоремы о постоянстве этих величин на периодическом участке. В четвертой главе рассмотрена задача о кратчайших путях для периодических динамических графов и графов с ограниченными магнитными и монотонными достижимостями. Так как не все пути на графах с указанными видами ограничений являются допустимыми, предлагается искать кратчайшие пути на вспомогательном графе, который можно рассматривать как обыкновенный ориентированный граф. Доказаны теоремы о соответствии между кратчайшими путями на исходных графах с ограничениями и путями на соответствующих им вспомогательных графах. Теорема 4.1.1. Кратчайшему пути длины на графе из вершины в вершину соответствует кратчайший путь из вершины в подмножество вершин на вспомогательном графе . Приведены алгоритмы поиска кратчайших путей на вспомогательном графе для каждого вида ограничений. Показано, что кратчайшие пути на графах с описанными ограничениями, вообще говоря, не обладают свойством экстремальности и транзитивности. Показано что алгоритм поиска кратчайшего пути с применением вспомогательного графа является более эффективным, чем поиск кратчайшего пути без использования вспомогательного графа. Сформулировано и доказано условие экстремальности кратчайшего пути на периодическом динамическом графе: Теорема 4.2.1. Пусть – кратчайший путь из некоторой вершины в некоторую вершину с началом в момент времени на периодическом динамическом графе . Рассмотрим отрезок этого пути , соединяющий вершины и . Для того, чтобы отрезок являлся кратчайшим путем из в , необходимо и достаточно выполнение условия . Для периодических динамических графов введены понятия кратчайшего пути из вершины в вершину с началом в момент времени и кратчайшего пути из вершины в момент времени в вершину в момент времени . Доказана теорема о постоянстве длины кратчайшего пути с начальным моментом времени, принадлежащим периодическому участку.

Похожие:

	Математические методы и модели Габрин К. Э., Математические методы и модели: Семестровое задание и методические рекомендации к решению задач. – Челябинск: Издательство...		Программа по формированию навыков безопасного поведения на дорогах... Закрепить представление о графах и умение строить графы по словесному описанию отношений между предметами и существами
	Васильев е. П. Экономико математические методы и модели часть I Лукинова С. Г., Шатохина Л. В., Васильев Е. П. Экономико-математические методы и модели Часть I. Учебно-методический комплекс. –...		План чтения лекции по учебной дисциплине «Математические методы» Раздел №2 Учебные и воспитательные цели: изучить основные виды задач линейного программирования, их математические модели
	Тема: «Математические расчеты семейного бюджета» Математическая экономика – теоретическая и прикладная наука, предметом которой являются математические модели экономических объектов...		Горюшкин А. А., Хуторецкий А. Б. Математические модели и методы исследования... Горюшкин А. А., Хуторецкий А. Б. Математические модели и методы исследования операций: курс лекций: Учеб пос. Новосиб национ иссл...
	Методические рекомендации по изучению дисциплины «экономико-математические... Методические рекомендации по изучению дисциплины «экономико-математические методы и модели»		Реферат на тему: Нечетко-логические модели и алгоритмы
	Урок №5 Тема: Разрезы, их назначение и правила Оборудование: Учебник, чертёжные инструменты, динамические модели предметов, плакаты, мультимедийный проектор, компьютер		Программа дисциплины «Экономико-математические методы и модели в... ...
	Отчет о проведении недели естественно-математического цикла Ребята 5 – 11 классов заранее получили задания, готовясь к этой неделе, сочиняли математические сказки, составляли ребусы, кроссворды....		Рабочая программа учебной дисциплины теоретическая механика направление... Целью дисциплины является формирование у студентов знаний в области теоретической механики. Задачей изучения дисциплины является...
	Примерная программа наименование дисциплины Дифференциальные уравнения... Он должен успешно использовать математические модели различных физических, механических и экономических процессов, уметь правильно...		Фгбоу впо «сгэу» от 09. 11. 2012г. № Решение ученого совета Самарского... «Математическое моделирование», «Математические модели в финансовых операциях», «Методы оптимизации», «Экономико-математические методы...
	Системы линейных уравнений с двумя переменными как математические модели реальных ситуаций Системы двух линейных уравнений с двумя переменными как математические модели реальных ситуаций		Тема реферата История возникновения математического моделирования и простейшие математические модели