На правах рукописи
Кузьминова Марина Валерьевна
МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ НА ГРАФАХ С НЕСТАНДАРТНОЙ ДОСТИЖИМОСТЬЮ. ДИНАМИЧЕСКИЕ ГРАФЫ
05.13.18 – Математическое моделирование, численные методы и комплексы программ
05.13.17 – Теоретические основы информатики
АВТОРЕФЕРАТ
диссертация на соискание ученой степени
кандидата физико-математических наук
Ростов-на-Дону
2008
Работа выполнена
на кафедре алгебры и дискретной математики факультета математики, механики и компьютерных наук Южного Федерального Университета в г.Ростове-на-Дону.
Научный руководитель: кандидат физико-математических наук,
профессор Ерусалимский Яков Михайлович
Официальные оппоненты: доктор физико-математических наук,
профессор Соколов Валерий Анатольевич
кандидат физико-математических наук,
доцент Басангова Елена Одляевна
Ведущая организация: Воронежский Государственный Университет,
г. Воронеж.
Защита диссертации состоится “ 22 ” января 2009 года в ч. мин. на заседании диссертационного совета Д212.208.22 Южного Федерального Университета по адресу: Таганрог, пер. Некрасовский, 44, ауд. Д-406.
С диссертацией можно ознакомиться в Зональной научной библиотеке ЮФУ по адресу: Ростов-на-Дону, ул. Пушкинская, 148.
Автореферат разослан “ ” 2008 года.
Просим Вас прислать отзыв на автореферат, заверенный гербовой печатью учреждения, по адресу: 347928, Таганрог, пер. Некрасовский, 44, диссертационный совет Д212.208.22.
Ученый секретарь
диссертационного совета Д212.208.22
доктор технических наук, профессор  А.Н. Целых
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Теория графов предоставляет эффективные средства формализации задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управления производством, сетевого и календарного планирования, информационных систем, и многих других. Одним из таких средств является ориентированный граф. Существует большое количество задач, решаемых на орграфах. Чаще всего рассматриваются задачи о достижимости (т.е. о существовании пути, связывающем две заданные вершины), о нахождении путей, обладающих какой-либо экстремальной характеристикой (например, кратчайший, или наиболее надежный путь), о случайных блужданиях, потоковая задача. Все они хорошо изучены и разработаны эффективные алгоритмы их решения. При этом предполагается, что все пути на графе являются допустимыми, т.е. не накладывается никаких ограничений на достижимость. Наиболее известные работы в этой области принадлежат Кристофидесу Н., Басакеру Р.Д., Харари Ф., Бержу К., Дейкстре Э., Флойду Р., Замбицкому Д.К., Оре О., Саати Т., Фалкерсону Д.Р., Форду Л.Р.
В отличие от классического подхода, Басанговой Е.О. и Ерусалимским Я.М. было введено понятие ориентированных графов с нестандартной достижимостью, т.е. орграфов, в которых на допустимые пути накладываются какие-либо ограничения. В обычном ориентированном графе, для того чтобы одна вершина была достижима из другой, необходимо существование пути, связывающего две эти вершины. В случае же орграфов с нестандартной достижимостью требуется, кроме того, чтобы этот путь удовлетворял некоторому условию (ограничению). Понятно, что в этом случае классические алгоритмы решения задач на графах непосредственно неприменимы.
В работах Ерусалимского Я.М., Басанговой Е.О., Логвинова С.Ю., Скороходова В.А., Петросяна А.Г. описаны различные виды ограничений на достижимость. Так, Ерусалимским Я.М. и Басанговой Е.О. рассмотрено несколько видов достижимости на частично-ориентированных графах, на которых присутствуют ориентированные и неориентированные ребра. Введено понятие смешанной цепи, на дуги и звенья которой накладываются различные условия, в зависимости от вида ограничений. Например, рассмотрены случаи, когда в смешанной цепи два неориентированных ребра не могут следовать непосредственно друг за другом, или дуги и звенья строго чередуются.
В работах Скороходова В.А. рассмотрены орграфы с накоплением неубывающей магнитности  - го уровня. На таких графах допустимым является магнитно-накопительный путь порядка с неубывающей магнитностью, т.е. такой путь, что если на  - м шаге величина накопленной магнитности не меньше и среди выходящих дуг есть хотя бы одна магнитная, то  - я дуга пути должна быть магнитной. Другой вид достижимости – вентильно-накопительная. В этом случае множество дуг графа представляется в виде  . В допустимом пути прохождение по дуге множества  делает доступными для прохождения дуги множества  . Также рассмотрены условия накопления-исчезания и возрастания-убывания магнитности, вентильная достижимость с возрастанием-убыванием доступа и энергии на пути, механическая достижимость.
Петросяном А.Г. определена барьерная достижимость, при которой множество дуг разбивается на три попарно непересекающихся подмножества: дуг, увеличивающих барьерный показатель, дуг барьерного перехода и нейтральных дуг. С каждым отрезком пути связана числовая характеристика – барьерный показатель частицы. Путь допускает барьерный переход уровня  , если к некоторому шагу он накопил величину барьерного показателя, не меньшую  . Еще один вид ограничений – биполярная магнитность. В этом случае определяется величина накопления биполярной магнитности. Путь считается допустимым, если он удовлетворяет условию биполярной магнитности уровня .
Общим подходом к решению задач на орграфах с ограничениями на достижимость является построение вспомогательного графа, имеющего большее количество вершин, и обладающего следующим свойством: допустимому пути на исходном графе с ограничениями соответствует некоторый путь на вспомогательном графе, а недопустимому пути не соответствует ни один путь. Алгоритм построения такого графа зависит от вида вводимых ограничений. На вспомогательном графе, таким образом, все пути являются допустимыми, а дуги – равноправными, и его можно рассматривать как обычный ориентированный граф. Для графов с нестандартными достижимостями описанных видов рассмотрены классические задачи о кратчайшем пути из вершины в вершину, о максимальном потоке в сети с нестандартной достижимостью и о случайных блужданиях на таких графах. Наибольшую сложность вызывают две последние задачи, так как при построении вспомогательного графа увеличивается не только количество вершин, но и количество дуг. При этом необходимо правильно распорядится весами дуг, по которым строится несколько дуг на вспомогательном графе. Серьезного осмысления каждый раз требует и перенос соответствующего результата с вспомогательного графа на основной граф.
В настоящей работе рассмотрены ориентированные графы с различными типами ограничений на достижимость и решаются задачи о случайных блужданиях, о кратчайших путях и о максимальном потоке на таких графах. В частности, введено четыре типа магнитной достижимости: на начальном и конечном отрезках пути с параметром  , на отрезке  и магнитная достижимость, возникающая после шагов. Описаны орграфы с монотонной достижимостью, которая является обобщением магнитной. Кроме того, рассмотрены динамические и периодические динамические графы, т.е. такие ориентированные графы, для которых вводится дискретное время и задается функция активности дуг – дуги на графе существуют не в любой момент времени, а только в свои промежутки активности. Ясно, что такие задачи могут рассматриваться как математические модели транспортных или информационных сетей, в которых в определенные моменты времени функционируют не все участки сети. Для каждого вида ограничений разработаны алгоритмы построения вспомогательного графа, что позволяет свести решение указанных выше задач на исходном графе к задачам на вспомогательном графе без ограничений на достижимость. Доказаны теоремы о взаимнооднозначном соответствии между исходным и вспомогательным графами. Применимость данных моделей к решению логистических задач делает данную работу актуальной.
Цели и задачи работы. Цель состоит в изучении графов с нестандартными достижимостями, разработке алгоритмов решения задач на таких графах, описании нового класса динамических графов, программной реализации полученных алгоритмов.
В работе рассмотрены и решены следующие задачи:
Определены и исследованы новые виды достижимости на орграфах.
Разработаны и описаны алгоритмы решения задач о кратчайших путях, случайном блуждании и максимальном потоке на графах с рассмотренными ограничениями на достижимость.
Рассмотрен новый класс задач о максимальном потоке в периодической динамической сети.
Для периодической динамической сети введены определения максимального динамического потока, исходящего из источника в момент времени  , и максимального динамического потока из источника, приходящего в сток в момент времени  и разработаны алгоритмы их нахождения.
Полученные алгоритмы реализованы в виде комплекса программ.
Методы диссертационного исследования основываются на использовании теории графов, теории вероятностей и теории случайных процессов.
Научная новизна диссертационной работы состоит в следующих результатах, полученных автором:
Определены и изучены магнитная и монотонная достижимости с четырьмя видами ограничений: на начальном и конечном отрезках пути, ограничения, возникающие после  шагов и на отрезке  .
Предложены алгоритмы построения вспомогательного графа для указанных ограничений на достижимость.
Определен новый класс динамических графов, на которых некоторые дуги доступны для прохождения не в любой момент времени, а лишь в период их активности.
Для описанных видов ограничений разработаны алгоритмы решения задач о кратчайших путях, максимальном потоке и случайных блужданиях.
Построена математическая модель периодической динамической сети, введены понятия максимального динамического потока, исходящего из источника и приходящего в сток в фиксированные моменты времени и разработаны алгоритмы их нахождения.
Алгоритмы, предложенные в работе, реализованы в виде комплекса программ, приведенного в приложении.
Практическая ценность работы состоит в том, что введенные и изученные новые виды достижимости на орграфах расширяют класс возможных приложений и могут быть использованы для исследования новых дискретных математических моделей. Периодические динамические графы могут быть использованы для моделирования процессов в транспортных и информационных сетях. На основании теоретических результатов диссертационной работы было создано программное обеспечение в среде программирования C++ Builder 6.0, реализующее разработанные алгоритмы.
Апробация работы.
Результаты диссертации докладывались на Воронежской весенней математической школе «Понтрягинские чтения XVIII» (г. Воронеж, 2007).
По результатам работы сделан доклад на III всероссийской школе-семинаре «Математическое моделирование и биомеханика в современном университете» (пос. Дивноморское, 2007).
Сделан доклад на 5-й всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь XXI века – будущее российской науки» (г. Ростов-на-Дону, 2007).
Результаты работы неоднократно обсуждались на научном семинаре кафедры алгебры и дискретной математики факультета математики, механики и компьютерных наук ЮФУ.
Результаты работы вошли в отчеты по проектам «Нестандартная достижимость на ориентированных графах» (Грант конкурсного центра Минобразования РФ по разделу естественные науки, проект Е02-01-231) и «Графы и сети с нестандартной достижимостью» (Ведомственная программа Минобрнауки РФ «Развитие научного потенциала высшей школы», подпрограмма №3, раздел 3.3.- поддержка исследований проводимых молодыми учеными, проект 7857).
По материалам диссертации опубликовано 7 печатных работ.
Публикации. По материалам диссертации опубликовано 7 работ [1]-[7].
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, приложения и списка литературы. Объем основного текста диссертационной работы составляет 119 страниц, включая 47 рисунков, библиографический список изложен на 5 страницах и содержит 51 наименование, приложение содержит 16 страниц.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы, сделан обзор существующих видов нестандартной достижимости на ориентированных графах, сформулированы цели работы, выделена ее научная новизна и дана краткая аннотация всех глав диссертации.
В первой главе введено три типа нестандартной достижимости на ориентированных графах: ограниченные магнитные достижимости, ограниченные монотонные достижимости и периодические динамические графы.
Ограниченные магнитные достижимости. Рассматриваются ориентированные графы, множество дуг которых представляет собой объединение двух непустых непересекающихся подмножеств, которые называются множеством магнитных и множеством немагнитных дуг. Такие графы называются графами с магнитными ограничениями (или с магнитной достижимостью). Путь на таком графе является допустимым при выполнении условия: если предыдущая дуга пути была магнитной и есть исходящие магнитные дуги, то следующая дуга пути также должна быть магнитной.
В настоящей работе рассмотрены случаи, когда магнитные ограничения действуют не на всем протяжении пути, а лишь на некотором его отрезке. Такие достижимости названы ограниченными магнитными достижимостями. Рассмотрены три вида достижимостей – на начальном отрезке пути длины  , на конечном отрезке пути длины , магнитная достижимость, возникающая после шагов и магнитная достижимость на отрезке натурального ряда  . Соответствующие графы обозначаются  ,  ,  и  .
Ограниченные монотонные достижимости. Монотонная достижимость является обобщением магнитной достижимости на случай, когда множество дуг графа разбивается на  попарно непересекающихся подмножеств  . Путь на графе с монотонной достижимостью является допустимым, если подпоследовательность индексов дуг пути (не учитывая дуги множества  ) не убывает (индекс дуги – номер подмножества дуг, которому она принадлежит).
Рассмотрено четыре типа монотонной достижимости: на начальном и конечном отрезках пути длины , монотонная достижимость, возникающая после шагов, и монотонная достижимость на отрезке . Графы с соответствующим типом достижимости обозначаются  ,  ,  и  . Сформулирована теорема о связи достижимости на графах  и  .
Периодические динамические графы. Для обыкновенных ориентированных графов вводится дискретное время  , и рассматриваются динамические графы. Динамическим графом называется ориентированный граф вида  , множество дуг которых представляет собой объединение двух непустых непересекающихся подмножеств, которые называются множеством обычных и множеством временных дуг,  – функция активности. Временные дуги графа доступны для прохождения не в любой момент времени, а только в периоды активности. Путь на динамическом графе является допустимым, если все его дуги активны в момент прохождения их путем.
Пути на динамических графах, в отличие от путей на обыкновенных орграфах, не обладают, вообще говоря, свойством транзитивности. Сформулировано и доказано условие транзитивности пути на динамическом графе.
|
