WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


На правах рукописи

Ерусалимский Яков Михайлович

Нестандартная достижимость на ориентированных графах и сетях

Специальность 01.01.09 – дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Ярославль – 2012

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего профессионального образования «Южный федеральный университет» Официальные оппоненты:

Сапоженко Александр Антонович, доктор физикоматематических наук, профессор, Московский государственный университет, профессор Соколов Валерий Анатольевич, доктор физикоматематических наук, профессор, Ярославский государственный университет, заведующий кафедрой Язенин Александр Васильевич, доктор физикоматематических наук, профессор, Тверской государственный университет, заведующий кафедрой

Ведущая организация: Воронежский государственный университет

Защита состоится «25» мая 2012 г. в 14 ч. 00 мин. на заседании диссертационного совета Д 212.002.03 при Ярославском государственном университете им. П.Г. Демидова по адресу: 150008, г. Ярославль, ул. Союзная, 144, аудитория 4

С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета им. П.Г. Демидова Автореферат разослан «___» _________ 2012 г.

Ученый секретарь диссертационного совета Яблокова С.И.

Общая характеристика работы

Настоящая работа посвящена ориентированным графам с нестандартной достижимостью и некоторым смежным вопросам дискретной математики. Ключевых слов в этом предложении несколько. Во-первых, «ориентированным» - автор не разделяет суждения о том, что по-настоящему математическими объектами являются неориентированные графы. Действительно, если к графам подходить как к объектам, изучаемым методами алгебраической топологии, то этот так и есть, но в приложениях чаще встречаются и более естественны для использования именно ориентированные графы. Класс ориентированных графов более широк и интересен, в большинстве случаев неориентированный граф можно считать симметрическим ориентированным графом. Вторым ключевым словом или фразой в первом предложении является «граф с нестандартной достижимостью». Именно эти объекты мы в основном и будем рассматривать в нашей работе.

В прикладных задачах, как правило, изучается не сам граф, а процессы на нем. Большинство из них связано с перемещениями по путям на графе. В классическом определении путь – это последовательность дуг графа, в которой каждая следующая дуга начинается в вершине, в которой заканчивается предыдущая дуга пути. Соединимость одной вершины путм, ведущим из другой вершины, называется достижимостью одной вершины из другой. Три основных задачи прикладной теории графов и не только прикладной, а точнее сказать, алгоритмической теории графов связаны с достижимостью на графах. Это сама задача о достижимости и нахождении кратчайшего пути, задача о случайных блужданиях по вершинам графа и задачи о потоках в сетях. Поток можно считать перемещением (транспортировкой) вещества (материи, товаров, жидкости, энергии и т.п.) из источника в сток по путям, ведущим из источника в сток.

Когда мы говорим о графе с нестандартной достижимость, то это означает, что допустимыми на нм являются не все пути, а пути, удовлетворяющие определенному условию (это условие называется типом или видом нестандартной достижимости). Как правило, тип нестандартной достижимости возникает после того, как задано некоторое разбиение множества дуг графа, а ограничения на достижимость формулируются с помощью (в терминах) этого разбиения. Почему мы считаем, что графы с нестандартной достижимостью являются по существу новыми объектами, по сравнению с обычными графами? Во-первых, графы можно считать графами с нестандартной достижимостью (тривиальной), но главное не в этом. Как оказалось ([12]), для большинства известных видов нестандартной достижимости задача о максимальном целочисленном потоке в сети с нестандартной достижимостью в отличие от этой задачи в обычных графовых сетях является NPполной.

Актуальность. Родившаяся при решении головоломок и занимательных задач теория графов стала мощным средством исследования во многих отраслях науки и техники1. Е широкая применимость стала и мощным стимулом развития. Посылая сообщение по электронной почте, мы пользуемся теорией графов, поскольку вся навигация в ИНТЕРНЕТе основана на решении задачи о кратчайшем маршруте, соединяющем заданные узлы сети, пользуясь JPS-навигаторами, мы невольно используем теорию графов.

Новый этап развития теории графов можно назвать алгоритмическим, поскольку широкая применимость всегда связана с алгоритмами, позволяющими решать массовые задачи. Прикладная направленность сделала сам термин «теория графов» неудачным. Его стали заменять термином «Прикладная теория графов» или «Алгоритмическая теория графов»2. Всюду в дальнейшем в нашей работе под «теорией графов» мы понимаем этот термин именно в этом смысле.

Среди алгоритмов на графах следует особо выделить алгоритм Е.Дейкстры3 нахождения кратчайших путей на графах, фактически первый динамический алгоритм, и алгоритм Д. Краскала4 нахождения легчайшего покрывающего дерева.

Ещ одним выдающимся достижением алгоритмической теории графов стала теория потоков в сетях, созданная Л. Фордом и Д. Фалкерсоном5.

В настоящий момент теория потоков в сетях находит все большее применение в связи с развитием телекоммуникаций (INTERNET, мобильная связь, глобальные компьютерные сети6 и т.п.), логистики, теории нейронных сетей, биоинформатики7). Вот что говорится во введении в книгу М.Ньюмана8:

Химические приложения топологии и теории графов/под. ред. Р.Кинга//М.: Мир, 19Применение теории графов в химии/под ред. Н.С. Зефирова и С.И. Кучанова//Новосибирск: Наука, 19 Кристофидес Н. Теория графов. Алгоритмический подход. // –М.:Мир, 1978. – 432с.

Dijkstra E.W. A Note in two problems in connection with graphs, Numtrische Mathematic,1959, #1, p.2 Kruskal J.B. On the shortes spannig subtree of a graph and the traveling salesman problem, Proc. American Mathematical Soc., 1956, #7, p. Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир, 19 Самуйлов К.Е., Чукарин A.B. К расчету плана маршрутизации сети системы сигнализации №7 // Системы телекоммуникаций и моделирование сложных систем. -М.: ПАИМС, 20 Ерусалимский Я.М. Дискретная математика для биоинформатиков//Ростов н/Д: Изд-во ЮФУ.

2011, 122с.

Newman M. Networks: an Introduction//Oxford University Press, Inc., New York, NY,2010.

p.7 «Современная теория сетей стала прототипом междисциплинарных исследований: социология, компьютерные науки, химия, экономика, энергетика, транспорт, управление бизнесом и, сравнительно недавно, социальные сети и биоинформатика. Целям и задачам все этих наук служит эта теория». Современное состояние теории сетей изложено в книге Т. Левиса 9. Следует отметить, что с точки зрения общих подходов к теории сетей, то они мало изменились по сравнению с подходом основоположников этой теории Л. Форда и Д. Фалкерсона. В основном е развитие связано с разработкой и совершенствованием алгоритмов решения потоковых задач в сетях10. Среди учных, внесших основной вклад в развитие этого направления, необходимо назвать Г. Данцига, Е. Диница, Дж. Эдмонтса, Х. Габова, А. Гольдберга, Р. Карпа, В.

Кинга, Р. Тарьяна, С. Рао. Если говорить о развитии общих подходов к теории сетей, то следует особо выделить работу А. Гольдберга и С. Рао11.

Следует отметить то различие, которое имеется в понимании и подходах к теории сетей, которое существует. С точки зрения дискретной математики теория сетей занимается изучением транспортной способности сетей (классическая теория Форда-Фалкерсона, основанная на понятии допустимый поток). Второй подход к теории сетей – изучение побудительных причин наличия потока в сети, изучение закономерностей динамики таких потоков, связан в основном с приложениями сетей в других науках: теория электрических цепей, берущая свое начало от работ Г. Кирхгофа, теория гидравлических сетей, сетевая логистика, сетевые методы в экономике и финансахи т.п. Среди последних работ по применению теории гидравлических сетей в Lewis T. Network Science: Theory and Applications// Wiley Publ., Hoboken, NJ, 2009. p. 5 Helmberg C. Network Models with Convex Cost Structure like Bundle Methods. / C. Helmberg // Models and Algorithms for Optimization in Logistics, Dagstuhl Seminar Proceedings.

http://drops.dagstuhl.de/opus/volltexte/2009/21Karp R.M. Reducibility among Combinatorial Problems. / Karp R.M. // Complexity of Computer Computations; R.

E. Miller and J. W. Thatcher (editors). –New York: Plenum, 1972. – pp.85–103.

Karzanov, A.V. Determining the maximal flow in a network by the method of preflows. / A.V. Karzanov // Sov.

Math. Dokl. –1974. –No.15. – pp.434-474.

King V. A faster deterministic maximum flow algorithm. / V. King, S. Rao, R. Tarjan. // In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, Fla., Jan. 27-29). ACM, New York, 1992. – pp.157-164.

King V. A faster deterministic maximum flow algorithm. / V. King, S. Rao, R. Tarjan. // J.

Algorithms. –1994. –No.17. – pp.447-474.

Goldberg A.V. Beyond the Flow Decomposition Barrier/ A.V. Goldberg, S. Rao/ Journal of the ACM. –Vol.45.

–No. 5. –1998. – pp.783-797.

Nugurney A. A Supply Chain Network Economics. Dynamics of Prices, Flows and Profits//EE Publishing Ltd., 2006, pp.4 экономике следует отметить докторскую диссертацию А.Г. Коваленко13. В нашей работе под теорией потоков в сетях мы понимаем е как соответствующий раздел дискретной математики.

Цель исследования. Настоящая работа посвящена, в основном, нестандартной достижимости на ориентированных графах и задачам поиска кратчайших путей, случайным блужданиям и потокам в сетях. Нестандартная достижимость на графах естественным образом возникает именно в прикладных задачах.

Поясним сказанное примером. Рассмотрим телекоммуникационную сеть. Будем интерпретировать е как граф, вершины которого соответствуют пунктам приема/ передачи информации. Дуги соответствуют каналам связи, по которым передается информация между пунктами. Известно, что в процессе передачи сигнала по каналу связи с ним могут происходить изменения – сигнал может затухать и если его уровень понизится до уровня естественного шума, то возникает его потеря. Имеется два типа основных средств борьбы с этим: пассивные и активные. Пассивные средства предполагают улучшение физических характеристик каналов, что обеспечивает более низкий уровень затухания сигнала и снижение уровня естественного шума в канале. Последним достижением в этой области являются оптоволоконные каналы связи, получившие в настоящее время широкое распространение. Активные средства предполагают повышение уровня сигнала с помощью разного рода усилителей, которые комбинируются со средствами фильтрации. Такая комбинация позволяет отфильтровать сигнал от шума и повысить его уровень. Таких активных улучшений сигнала во время его передачи по каналам связи может быть несколько, а может и не быть вовсе, все зависит от трассы, по которой передается сигнал (имеются ли на ней активные участки).

Активные средства улучшения качества сигнала последнее время получили широкое распространение. Переломным моментом в развитии активных средств явился переход от аналоговых систем передачи информации к цифровым системам. Цифровые системы позволяют лучше и легче решать задачу Коваленко А.Г. Развитие математических моделей и методов теории гидравлических сетей и их применение для моделирования рассредоточенного рынка// автореферат диссертации на соискание ученой степени доктора ф.-м. наук, Москва, 20 фильтрации сигналов от шума, а также позволяют поднимать его уровень (усиливать), не внося искажений в отфильтрованный поток информации.

В нашей модели телекоммуникационной сети возникает естественное разбиение множества дуг на три типа: пассивные или нейтральные, прохождение сигнала по которым не влияет на его качество, активные («хорошие»), прохождение сигнала по которым улучшает его качество, регрессивные («плохие»), прохождение сигнала по которым существенно снижает его уровень.

Если бы мы находились на первоначальном этапе развития телекоммуникационных сетей, то все дуги следовало бы рассматривать как плохие.

Ясно, что в этом случае минимальный ущерб качеству передачи будет получен в случае использования кратчайшей трассы, из имеющихся трасс между пунктами передачи и приема информации.

Современный этап развития телекоммуникаций характерен тем, что большинство дуг являются либо нейтральными, либо активными, однако полное избавление от регрессивных дуг в ближайшее время не представляется возможным. Более того – требования к качеству передачи информации возрастают. Это приводит к тому, что часть дуг из первых двух категорий приходится «переводить» в третью (моральный износ), такой перевод может быть связан и с неизбежным физическим износом.

В случае наличия дуг трех типов далеко не всегда лучшей для передачи информации является кратчайшая трасса. Действительно, если она состоит только из регрессивных дуг, то затухание сигнала может оказаться таким, что он утонет в естественном шуме. Ясно, что задача выбора оптимальной трассы для передачи информации становится нетривиальной. Речь идет о выборе кратчайшего пути не из всего множества путей, имеющихся на нашем графе, а из некоторого подмножества путей. Эти пути нельзя рассматривать как пути на некотором частичном графе, т.е. когда, например, регрессивные дуги просто удалены.

Существенным при определении того, какой путь можно рассматривать, а какой путь нельзя, является не то - какие дуги участвуют в его формировании, и не то - какие дуги не участвуют. Определяющим, в нашем случае, является следующее: в какой комбинации дуги разных типов встречаются в последовательности дуг пути (улучшенный сигнал можно пропустить и через регрессивные дуги; регрессивные дуги не могут встречаться в последовательности дуг пути таким образом, что уровень сигнала понижается до недопустимого для дальнейшего прохождения уровня).

Характерной особенностью задач на графах с нестандартной достижимостью является неприменимость напрямую классических алгоритмов, поскольку все они предполагают, что все возможные пути на графе являются допустимыми. Это относится и к задаче о кратчайших путях, и к задаче о случайных блужданиях по графу, и к задаче о максимальном потоке в сети.

Графы с нестандартной достижимостью – первый известный пример, когда мультиграфы (графы с кратными дугами) приходится рассматривать по существу. Задача, исходно поставленная на мультиграфе, не может быть сведена к задаче на обычном графе заменой кратных дуг на кратчайшую из них (в задаче о кратчайших путях), дугой с суммарной вероятностью перехода (в задаче о случайных блужданиях) или дугой с суммарной пропускной способностью (в потоковых задачах). Это связано с тем, что кратные дуги могут быть разных типов. В связи со сказанным мы можем определить:

Цель и задача исследования. Разработать общую теорию графов и сетей с нестандартной достижимостью, которая позволяла бы решать задачи о кратчайших путях, случайных блужданиях и потоковые задачи в тех ситуациях, когда классические алгоритмы неприменимы. Эта теория должна существенно расширить класс возможных приложений теории графов.

Объект исследования – ориентированные графы и сети с нестандартной достижимостью.

Предмет исследования – задачи о кратчайших путях и случайных блужданиях и потоковые задачи на таких графах и сетях.

Гипотеза исследования. Круг приложений теории графов и класс рассматриваемых задач настолько расширились, что необходимо расширить и наши представления об исходных объектах: графах и сетях. Такое расширение должно позволить рассматривать и решать задачи, к которым раньше аппарат теории графов был неприменим.

Методы исследований. В работе использованы методы дискретной математики, в том числе методы теории графов, комбинаторного анализа, дискретной оптимизации, а также методы алгебры и математического анализа.

Степень разработанности проблемы и новизны. Изучение графов с нестандартной достижимостью началось сравнительно недавно, первые ра боты в этой области принадлежат Я.М.Ерусалимскому и Е.О.Басанговой ([25, 27-29]). В работах [25, 27] рассматривались частично-ориентированные графы, т.е. такие, которые содержат ориентированные дуги и неориентированные ребра.

Рассмотрение частично-ориентированных графов в этих работах было вызвано задачей, связанной с теорией базисов в пространствах Кте. Существенным моментом в этих работах было ограничение на множество рассматриваемых путей – неориентированные рбра не могли встречаться на путях подряд, они должны были прореживаться дугами графа. В работе [28] было впервые сформулировано понятие «ориентированный граф со смешанной достижимостью», состоящее в следующем – множество дуг такого графа представляет собой объединение попарно непересекающихся множеств U и N UZ. Смешанным путем на таком графе называется путь, на котором по дугам из множества UZ нельзя проходить более одного раза подряд. Граф, на котором рассматриваются только смешанные пути, мы назвали графом со смешанной достижимостью. Основным методом для решения задач на таких графах оказалось построение развртки - вспомогательного графа, путям на котором соответствуют допустимые пути на графе со смешанной достижимостью. В последующем нами (автором настоящей работы и его учениками) было введено более широкое понятие – граф с нестандартной достижимостью.

Полученным в этой области результатам и посвящена диссертационная работа. В не мы вынесли только наиболее общие вопросы этой теории, не рассматривая алгоритмы решения задач о кратчайших путях, случайных блужданиях и потоках, поскольку разработке и обоснованию алгоритмов для конкретных видов нестандартной достижимости были посвящены кандидатские диссертации учеников автора: Е.О. Басанговой, С.Ю. Логвинова, В.А.

Скороходова, А.Г. Петросяна, М.В. Кузьминовой, Н.Н. Водолазова. Таким образом, все известные в настоящее время результаты в этой области принадлежат либо лично автору настоящей работы, либо получены им совместно с учениками.

Теоретическая и практическая значимость. Работа носит теоретический и прикладной характер, поскольку в ней рассматриваются по существу новые математические объекты – графы и сети с нестандартной достижимостью и динамические графы и сети. Одновременно с этим на них ставятся и решаются классические задачи о кратчайших путях, случайных блуждани ях и потоках в сетях. Широкая практическая применимость этих задач общеизвестна, поэтому результаты, полученные в работе, могут расширить класс известных приложений теории графов и сетей, поскольку позволят учесть факторы, которые классическая теория не описывает.

Апробация работы и внедрение результатов. Основные результаты диссертации докладывались и обсуждались на семинаре кафедры алгебры и дискретной математики Южного федерального университета, на семинаре кафедры математического моделирования Южного федерального университета, на семинаре математического департамента Средне-Восточного технического университета (METU, Анкара, Турция), на семинаре института математических наук университета г. Халл (HIMSA, University of Hull, UK), международном конгрессе математиков (Мадрид, 2006), на Кишинвском и Одесском семинарах по графам и гиперграфам проф. А.А.Зыкова, на международной конференции «Математическое моделирование в экологии и численные методы» (EMMNA 99, Ростов-на-Дону, 1999), III всероссийской школе-семинаре «Математическое моделирование и биомеханика в современном университете» (Ростов н/Д, 2007), на весенней Воронежской математической школе «Понтрягинские чтения – ХХ (Воронеж, 2009), на весенней Воронежской математической школе «Понтрягинские чтения – ХХI (Воронеж, 2010), на заседаниях Ростовского математического общества, на весенней Воронежской математической школе «Понтрягинские чтения – ХХII (Воронеж, 2011), на IV-й Международной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования» (Воронеж, 2011), на семинаре кафедры математической кибернетики ВМК МГУ (ноябрь, 2011).

Исследования по графам и сетям с нестандартной достижимостью были поддержаны грантом конкурсного центра Минобразования РФ по разделу естественные науки (проект Е02-01-231 Нестандартная достижимость на ориентированных графах) и грантом ведомственной программы Минобрнауки РФ «Развитие научного потенциала высшей школы» (подпрограмма №3, раздел 3.3 – поддержка исследований, проводимых молодыми учеными, проект 7857 – Графы и сети с нестандартной достижимостью). Последние два года работа выполнялась в рамках НОЦ «Биоинженерия и биоинформатика» ЮФУ и поддержана ФЦП «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы», госконтракт №14.740.11.0006 «Создание биоинформационной технологии поиска взаимосвязанных сценариев организации в геномах животных и человека некодирующей ДНК и кодирующей белок ДНК».

Результаты работы включены в спецкурс «Алгоритмы на графах и сетях», читаемый на факультете математики, механики и компьютерных наук ЮФУ и в учебное пособие [15, 16].

Основные положения, выносимые на защиту:

1. Новые объекты – графы и сети с нестандартной достижимостью.

2. Общая теория графов и сетей с нестандартной достижимостью, основанная на построении разверток графов и сетей с нестандартной достижимостью.

3. Методы решения задач о кратчайших путях и случайных блужданиях на графах с нестандартной достижимостью.

4. Теория потоков в сетях с нестандартной достижимостью.

5. Новые объекты - динамические графы и сети, структура которых меняется в дискретном времени и графы со связанными дугами, т.е. такими для которых нельзя говорить о пропускной способности дуги, а только о суммарной пропускной способности связанных дуг.

6. Новые результаты о динамических потоках в сетях, в том числе о всплеске потока и его связи со средним значением потока, емкостью сети и пропускной способностью ближайшего к стоку разреза.

7. Теория семейств функций Гранди ориентированных и неориентированных графов.

8. Аддитивное представление факториала и тождества для степеней натуральных чисел и их полиномиальные аналоги.

Основные результаты, полученные в работе:

1. Конструкции разверток для различных видов нестандартной достижимости и теоремы о сводимости задачи о кратчайшем пути на графе с нестандартной достижимостью к соответствующей задаче о кратчайшем пути во множество вершин на развртке.

2. Доказана сводимость немарковского процесса случайного блуждания частицы по вершинам графа с нестандартной достижимостью к марковскому процессу случайного блуждания по вершинам развертки (теоремы 2.1, 2.2, 2.3).

3. Найден предел последовательности величин максимальных потоков семейства сетей с барьерной достижимостью при неограниченном росте высоты барьеров (теоремы 3.1, 3.2).

4. Теорема о разложении динамического потока на временном интервале в сумму потоков специального вида (теорема 4.1), позволившая получить оценку сверху величины динамического потока на промежутке через величину максимального стационарного потока и длину временного промежутка (теорема 4.2).

5. Оценка сверху средней величины динамического потока через величину максимального стационарного потока в этой сети (теорема 4.3) 6. Установлена связь между максимальным всплеском динамического потока в сети, емкостью сети, пропускной способностью разреза, прилежащего к стоку в виде набора неравенств (теорема 4.4) 7. Необходимые и достаточные условия того, что функция Гранди частичного орграфа является функцией Гранди исходного орграфа (теоремы 6.1, 6.2) и теорема о бесконтурной ориентации неориентированного графа, сохраняющей функцию Гранди (теорема 6.3).

8. Аддитивное представление факториала и тождества для степеней натуральных чисел и их полиномиальные аналоги (прил. 1).

Степень достоверности полученных результатов. Достоверность и обоснованность полученных в диссертационном исследовании теоретических результатов обеспечивается корректным применением математического аппарата и строгим математическим обоснованием предложенных методов и алгоритмов. Во всех случаях, когда полученные результаты являются обобщением известных, имеет место корректное вложение.

Публикации по теме исследования. Всего по теме диссертации опубликовано 36 работ, из них в изданиях из списка ВАК, рекомендованных для опубликования результатов диссертационных исследований – 12 наименований, статей в международных реферируемых изданиях – 1, монографий – 2, учебных пособий – Личный вклад автора. Все результаты, изложенные в диссертации, получены либо автором самостоятельно, либо при его непосредственном ак тивном творческом участии. В совместных работах, опубликованных со своими учениками, автору принадлежит постановка и решение общих задач теории графов с нестандартной достижимостью и осуществление непосредственного руководства. Диссертационные работы учеников (Басангова Е.О., Логвинов С.Ю., Скороходов В.А., Петросян А.Г., Кузьминова М.В., Водолазов Н.Н.) посвящены в основном алгоритмам решения задач о кратчайших путях, случайных блужданиях, потоках в сетях на графах и сетях с конкретными видами нестандартной достижимости. В настоящей работе рассмотрена общая теория графов и сетей с нестандартной достижимостью.

Структура и объм диссертации. Работа состоит из введения, шести глав и приложения на 144 стр., список литературы содержит 90 наименований.

Содержание работы Во введении обоснована актуальность работы, сформулирована цель работы и аргументирована научная новизна исследования, его теоретическая и практическая значимость. Представлены выносимые на защиту положения, сделан краткий обзор содержания работы.

В главе I «Нестандартная достижимость различных видов. Кратчайшие пути на графах с нестандартной достижимостью» мы определили несколько видов нестандартной достижимости на графах, описали построение разврток – вспомогательных графов, позволяющих решать задачу о кратчайших путях на графах с нестандартной достижимостью.

Первый вид нестандартной достижимости – смешанная достижимость.

Графы со смешанной достижимостью Пусть G(X,U, f ) - орграф. Множество дуг графа представлено следующим образом: U UR UZ,UR ,UZ . Дуги множества UR будем называть нейтральными, а множества UZ - запрещенными.

Определение 1.2. Смешанным путем на графе G(X,U UR UZ, f ) будем называть путь :[1;n]N U, удовлетворяющий условию:

i ([1;n 1]N )((i)UZ (i 1)UR ). Определение 1.3. Графом со смешанной достижимостью будем называть граф G(X,U UR UZ, f ), на котором допустимыми являются только смешанные пути (см. определение 1.2).

На графах со смешанной достижимостью нарушается основное свойство путей на обычных графах, которое мы называем аддитивным: «Если существует путь xy, соединяющий вершину x с вершиной y, и существует путь yz, соединяющий вершину y с вершиной z, то существует путь xz, соединяющий вершину x с вершиной z, получаемый склейкой имеющихся путей». На этих графах также нарушается экстремальное свойство кратчайшего пути: «Любой отрезок кратчайшего пути соединяющего две вершины графа является кратчайшим путем между вершинами, которые он соединяет». Это не позволяет напрямую применять для графов со смешанной достижимостью алгоритмы нахождения кратчайших путей.

Для преодоления возникших сложностей строится вспомогательный граф (развртка) и устанавливается соответствие между множеством допустимых путей на графе со смешанной достижимостью и множеством путей на развертке.

Заметим, что «геометрия» графа со смешанной достижимостью существенно отличается от «геометрии» этого графа без ограничения на достижимость.

Опишем построение развртки для графа со смешанной достижимостью G(X,U UR UZ, f ). Множеством вершин этого графа является мно - дубликат множества X, т.е. каждой вершине x X жество X X, где X соответствует x X. Если u UR, f (u) (x, y), на развртке ей соответствует две дуги, первая соединяет вершину x с вершиной y, а вторая дуга на чинается в вершине x и заканчивается в вершине y. Если uUz, f (u) (x, y), на развртке ей соответствует дуга, которая соединяет вершину x с вершиной y.

Пример 1.1. Рассмотрим граф, изображенный на рис. 1.1.

2 3 5 Рис. 1.1.

На рисунке запрещенные дуги обозначены пунктиром. Ясно, что путь, проходящий через вершины 1-7-5-6 не является смешанным, также не является смешанным путем 1-2-3-4-5-6. Единственный смешанный путь, соединяющий вершину 1 с вершиной 6 проходит через вершины1-8-4-5-6.

На рис. 1.2 приведена развртка - G для графа рис.1.1:

1 2 3 4 5 6 7 1 2 3 4 5 6 7 Рис. 1.2.

Имеют место теоремы:

Теорема 1.1. Вершина y достижима из вершины x на графе со смешанной достижимостью G(X,U UR UZ, f ) тогда и только тогда, когда на развртке G существует путь из вершины x во множество вершин {y, y }.

Справедливость этой теоремы следует из конструкции развртки. Если на исходном графе заданы длины дуг, то развртку тоже считаем взвешенным графом, полагая длины е дуг равными длинам породивших их дуг исходного графа.

Теорема 1.2. Длина кратчайшего пути из вершины x в вершину y на графе со смешанной достижимостью G(X,U UR UZ, f ) равна длине кратчайшего пути из вершины x во множество вершин {y, y }на развртке G. Этот кратчайший смешанный путь может быть восстановлен по крат чайшему пути из вершины x во множество вершин {y, y }на развртке G.

Ясно, что этот кратчайший путь на графе G может быть найден с помощью алгоритма Дейкстры.

В этой главе рассмотрен ещ один вид нестандартной достижимости - магнитная, которая сильно отличается от смешанной достижимости, поскольку ограничения на множество рассматриваемых (допустимых) путей на таком графе носят уже не локальный, а глобальный характер.

Графы с накоплением неубывающей магнитности G(X,U,) U UН UМ Определение 1.4. Пусть дан граф,, UН UМ UМ. Множество называется множеством магнитных дуг, а UН n – множество немагнитных дуг. Пусть – путь, состоящий из дуг. С [i; j]N (1 i j n) каждым отрезком пути свяжем числовую характеристику j (i, j) |{(m)}UМ | , (2) mi равную количеству магнитных дуг этого отрезка, при этом каждая магнитная дуга считается столько раз, сколько раз она встречается в пути. Характери (i, j) называется величиной накопленной неубывающей намагнистика [i; j]N пути ченности на отрезке Определение 1.5. Путь называется магнитно-накопительным пуk(1) n (n N) тем порядка состоящим из дуг с неубывающей намагниG ченностьюностью на графе, если выполняется следующее условие:

m( (m) k)(U (( p2 f )(m)) UМ ) ((m 1) UМ ).

i Другими словами, если к -му шагу от своего начала путь накопил (i) k намагниченность, большую либо равную, и среди дуг, выходящих i из концевой вершины -й дуги, есть хотя бы одна магнитная, то следующая (i 1) k -я дуга магнитно-накопительного пути порядка обязана быть дугой UМ из множества.

G(X,U,) Определение 1.6. Граф,U UН UМ на котором расk сматриваются только магнитно-накопительные пути порядка, будем наk зывать графом с накоплением неубывающей намагниченностью порядка.

Для графов с накоплением неубывающей намагниченности порядка k построена развертка.

G Пример 1.2. Рассмотрим граф, изображенный на рис. 1.6. МножеUM {(a,b),(b,c)} ство магнитных дуг (помечены буквой «М»), множество UН {(a,c),(b,d),(c,d)} немагнитных дуг (помечены буквой «Н»). ПоряG k 1 G' G док магнитности графа равен. Развртка для графа изображена на рис. 1.7.

b Н М М a d Н Н c G Рис. 1.6. Граф bbadad ccG' Рис. 1.7. Граф {(a,b),(b,c)} При отсутствии условия намагниченности путь является допустимым, однако, на рис. 1.7 видно, что с добавлением условия намагниченности такой путь становится недопустимым.

Ясно, что имеют место теоремы аналогичные теоремам 1.1 и 1.2.

Завершает главу I рассмотрение ещ одного типа нестандартной достижимости – барьерной достижимости. Она также как и магнитная достижимость определяется не локально, а глобально (на отрезках пути).

Барьерная достижимость на графах U U0 U UB UG(X,U, f ) U Пусть, множества, и - граф, UUB попарно не пересекаются. Множество - множество нейтральных U дуг, – множеством дуг, увеличивающих барьерный показатель (множестUB во увеличивающих дуг), – множество дуг барьерного перехода (множество барьерных дуг).

[0;i]Z 0 i n Определение 1.7. С каждым отрезком ) пути (где из n дуг свяжем числовую характеристику (i), определенную индуктивно следующим:

1. (0) 0.

(i), если (i)U0;

2. (i 1) (i) 1, если (i)U;

0, если (i)UB.

(i) Характеристика называется величиной накопленной энергии [0;i]Z на отрезке пути. Определение 1.8. Графом с барьерной достижимостью высоты G(X,U U0 U UB, f ), все пути h (h N) будем называть граф на котором удовлетворяют условию:

(i)UB (i 1) h (3) m Другими словами, если к -му шагу путь от своего начала нако (m 1) h пил величину барьерного показателя, большую либо равную, то на последующем шаге становятся допустимыми для прохождения дуги из UB множества.

Пример 1.3. На рис. 1.8 изображен граф с барьерной достижимостью.

U UB Знаком «+» помечена дуга множества, буквой b- дуга множества.

Будем считать, что h 1.

+ 5 1 2 3 b Рис. 1.8.

Ясно, что на этом графе путь 1 2 3 4 отсутствует, а путь 1 2 3 6 5 2 3 4является барьерным путем с высотой барьеров равной единице. Если взять барьерный показатель h 2, то этот путь уже не является допустимым. Допустимым барьерным путем с высотой барьера является путь 1 2 3 6 5 2 3 6 5 2 3 4.

Для графов с барьерной достижимостью построена развртка. Ясно, что справедливы теоремы аналогичные теоремам 1.1 и 1.2.

В гл. II. «Случайные блуждания на графах с нестандартной достижимостью» мы определяем ещ несколько видов нестандартной достижимости и рассматриваем задачу о случайных блужданиях по вершинам графов с нестандартной достижимостью. Специфика решенных задач состоит в том, что на исходном графе с нестандартной достижимостью они не являются Марковскими. Переход к вспомогательным графам позволяет сводить немарковский процесс к Марковскому. Роль памяти о предыстории блуждания выполняет сам вспомогательный граф.

В § 2.1 рассмотрена задача о случайном блуждании по вершинам графа со смешанной достижимостью.

Пример 2.1. Рассмотрим граф, изображенный на рис. 2.1. Пунктиром на нем обозначены запрещенные дуги. Будем считать, что вероятность перехода на каждой дуге u, выходящей из вершины x, определена формулой:

p(u) (4) U (x) 2 3 5 Рис. 2.1.

Развртка графа, изображенного на рис. 2.1 приведена на рис. 2.2.

1 2 3 4 5 6 7 1 2 3 4 5 6 7 Рис.2.2. Развертка графа рис.2.1.

Если на дуги вспомогательного графа перенести вероятности перехода с исходного графа, то произойдт нарушение основного вероятностного соотношения:

p(u) 1 (5) uU (x) (например, в вершине 1’), на этом графе появились и тупиковые вершины (например, вершина 3 ). Осуществим перенормировку полученных переходных вероятностей так, чтобы выполнялось соотношение (5), для этого будем считать, что переходные вероятности p на дугах, выходящих из вершины x на вспомогательном графе, определены формулой:

p(u) p (u) . (6) p(u) uU (x) Ясно, что для графа рис. 2.2. p (1,2) p (1,8 ) p (1,7), p (5,1)1; p (1,7) p (1,2).

Построение развртки и указанный выше перенос на не переходных вероятностей с исходного графа позволяет доказать следующую теорему:

Теорема 2.1. Вероятность попасть из вершины x в вершину y на графе G со смешанной достижимостью за n шагов равна вероятности попасть из вершины x во множество вершин {y, y } за n шагов на развртке G.

В § 2.2. определен новый тип нестандартной достижимости - монотонная достижимость.

Графы с монотонной достижимостью Определение 2.1. Пусть GX,U, f ) - граф и U U0 U1 U2 Um, множества Ui - непустые попарно непересекающиеся. Множество U0 будем называть нейтральным, а множества Ui, i 1,2,,m- монотонными уровня i.

Определение 2.2. Пусть путь :[1;n]N U на графе GX,U U0 U1 U2 Um, f . Свяжем с ним числовую последоваn тельность ai ()i1, ai () j (i)U, т.е. последовательность номеров j множеств, которым принадлежат дуги пути.

Определение 2.3. Путь :[1;n]N U на графе GX,U U0 U1 U2 Um, f будем называть монотонным, если подпоследовательность положительных элементов последовательности n ai ()i1 является неубывающей. Таким образом, монотонность пути означает следующее, если он на каком-то шаге прошел по дуге из множества с номером k, то на любом из последующих шагов он не может проходить по дугам множеств с номерами 1,2,,k 1. Определение 2.4. Граф GX,U U0 U1 U2 Um, f , на котором допустимыми считаются только монотонные пути, будем называть графом с монотонной достижимостью. Пример 2.2. Рассмотрим граф, изображенный на рис. 2.4.

1 Рис. 2.4.

На рис 2.4. сплошными линиями обозначены дуги из множества U0, пунктиром – дуги множества U1, точечными линиями – дуги множества U2.

Ясно, что путь 1-2-3-5-6 не является монотонным путм, а путь 1-2-4-5-6 таковым является.

Для графов с монотонной достижимостью построена развртка, позволяющая сводить задачу о случайных блужданиях на графе с монотонной достижимостью к соответствующей задаче на развртке.

В § 2.3. введн в рассмотрение ещ один вид нестандартной достижимости, которую мы назвали вентильной.

Графы с вентильной достижимостью Определение 2.5. Пусть GX,U, f ) - граф иU U0 U1 U2 Um, множества Ui - непустые попарно непересекающиеся. Множество U0 будем называть нейтральным, а множества Ui, i 1,2,,m вентильными уровня i. Определение 2.6. Путь :[1;n]N U на графе GX,U U0 U1 U2 Um, f будем называть вентильным, если выполнено условие (i)Uk 1;i 1N Uk 1 , k 1,,m. (7) Таким образом, вентильность пути означает следующее, если он на каком-то шаге прошел по дуге из множества с номером k -1, то на любом из по следующих шагов он может проходить по дугам множеств с номерами 1,2,,k.

Определение 2.7. Граф GX,U U0 U1 U2 Um, f , на котором допустимыми считаются только вентильные пути, будем называть графом с вентильной достижимостью. Пример 2.2. Рассмотрим граф, изображенный на рис. 2.14.

1 2 Рис. 2.14.

На рис 2.14 сплошными линиями обозначены дуги из множества U0, пунктиром – дуги множества U1, точечными линиями – дуги множества U2.

Ясно, что путь 1-2-3-5-6 не является вентильным путм, а путь 1-2-4-5-6 таковым является.

Для графов с вентильной достижимостью построена развртка, позволяющая сводить задачу о случайных блужданиях на графе с вентильной достижимостью к соответствующей задаче на развртке.

Завершает главу II пример бесконечного графа с вентильной достижимостью, представляющий собой конструкцию, которую мы назвали пространственно-временным фракталом. Ниже на рис 2.21 приведен пример такой структуры. Цифры около дуг – номера множеств, которым они принадлежат, дуги множества U не имеют надписей, на малых фрагментах соответствующие надписи опущены. Вероятности перехода по дугам, выходящим из вершины, равны в каждый момент времени единице, деленной на количество дуг, которые доступны для прохождения в данный момент времени из данной вершины. Штриховая кривая справа означает «продолжение» конструкции вправо.

Рис. 2.21. Пространственно-временной фрактал Процесс случайного блуждания частицы по такому графу с вентильной достижимостью разворачивается не только во времени, но и в пространстве, при этом вероятности перехода также меняются во времени.

В главе III «Потоки в сетях с нестандартной достижимостью» мы начинаем изучение потоков в сетях с нестандартной достижимостью и динамических потоков в сетях. Основные трудности рассмотрения этих задач возникают из-за наличия так называемых связанных дуг, т.е. таких для которых нельзя говорить о пропускной способности дуги, а приходится говорить об их суммарной пропускной способности. Более того, нам пришлось пересмотреть базовые понятия теории потоков в сетях (поток, величина потока и т.п.), поскольку они никак не учитывали особенностей, связанных с рассмотрением графов и сетей, на которых допустимыми являются не все пути.

Приведем соответствующий пример:

2 4 Рис.3.1.

Граф со смешанной достижимостью изображн на рис. 3.1. Будем считать, что пропускная способность любой дуги равна единице, пунктирные дуги – запрещенные.

Построим развртку этого графа.

1 2 3 4 5 6 Рис. 3.2. Развртка графа рис.3.1.

Перенесем на полученный граф пропускные способности дуг исходного графа. Добавим фиктивный источник (0) и фиктивный сток (8). Получим сеть, изображенную на рис. 3.3.

0 1 2 3 4 5 6 Рис. 3.3.

Ясно, что максимальный поток на этом графе имеет величину 2. Если «вернуть» этот поток на исходный граф, то мы получим поток, который не является допустимым, поскольку на дуге, соединяющей вершину 3 с вершиной 7, этот поток имеет величину 2, а пропускная способность этой дуги равна 1.

Нейтральным дугам на развртке соответствует по две дуги, у каждой из которых пропускная способность равна пропускной способности породившей их дуги. Это приводит к возникновению на развртке потоков, которые не являются потоками на исходном графе. Выход из сложившейся ситуации был предложен в [16]. В этой работе введено понятие графов со связанными дугами. Связанными являются такие подмножества дуг, для каждой из которых не определена пропускная способность, вместо этого определена суммарная пропускная способность дуг из подмножества связанных между собой дуг. В нашем случае связанными являются пары дуг, полученных на вспомогательном графе из одной нейтральной дуги исходного графа. Их суммарная пропускная способность равна пропускной способности породившей их дуги. Если бы мы заранее знали – как распределить суммарную пропускную способность между связанными дугами, то задача поиска максимального потока была бы тривиальной – е нужно было бы решить на развртке и перенести полученное решение на исходный граф.

В работе Я.М. Ерусалимского и А.Г. Петросяна [17] был предложен эвристический алгоритм «прорыва», который в большинстве случаев позволяет определить – как должны быть розданы пропускные способности по связанным дугам, чтобы возникал максимальный поток. Этот алгоритм состоит в следующем: на вспомогательном графе находится простой путь из источника в сток. Этот путь насыщается потоком, после чего пропускные способности обычных дуг, принадлежащих этому пути, уменьшаются на величину потока, также уменьшаются суммарные пропускные способности связанных дуг, по которым проходит найденный путь. Затем дуги нулевой пропускной способности удаляются из графа, и вс повторяется заново.

Ещ более ярко указанные особенности проявляются на графах с барьерной достижимостью. Рассмотренные в § 3.1 примеры показали, что необходимо четко разобраться с понятием «поток» на графе с нестандартной достижимостью. Классическое определение потока как функции, определенной на множестве дуг, не содержит в себе никаких требований на пути, по которым транспортируется поток и, значит, не учитывает нестандартную достижимость. Определение потока на сети с нестандартной достижимостью как потока на развертке в силу наличия на ней связанных дуг тоже не совсем корректно. Приведем определения, которые лежат в основе нашего подхода к теории потоков в сетях с нестандартной достижимостью.

Определение 3.1. Пусть G(X,U, f,c) - сеть с нестандартной достижимостью, c – пропускная способность дуг, т.е. c :U (0,). – допустимый путь из источника в сток. C каждой дугой u, через которую проходит путь свяжем характеристику (u) – кратность дуги u на пути , опре делнную равенством:

(u) 1u. (8) Определение 3.2. Пусть G(X,U, f,c) – сеть с нестандартной достижимостью, – допустимый путь из источника в сток. Потоком по пути будем называть такую постоянную (0,), которая удовлетворяет условию (u) cu (9) для любой дуги пути . Определение 3.3. Поток по пути называется насыщающим этот путь, если существует такая дуга пути , для которой в соотношении (9) выполнено равенство.

Определение 3.4. Пусть G(X,U, f,c) – сеть с нестандартной достижимостью. Потоком в такой сети будем называть множество , элементами которого являются пары вида ; , где – допустимый путь из источника в сток, – поток по пути , при этом для каждой дуги графа выполнено условие (u) c(u) . (10) u,; Определение 3.5. Пусть G(X,U, f,c) – сеть с нестандартной достижимостью, – поток в такой сети. Величиной потока на дуге u будем называть величину (u), определенную равенством:

def.

(u) . (11) u,; Определение 3.6. Пусть G(X,U, f,c) – сеть с нестандартной достижимостью, s – источник, t – сток, – поток в такой сети. Величиной потока будем называть характеристику (u), (12) uU (t) равную суммарному потоку по всем дугам, заканчивающимся в стоке. Определение 3.7. Максимальным потоком в сети с нестандартной достижимостью называется такой поток max, для которого выполнено max max (13) В случае графов и сетей с нестандартной достижимостью меняется не только такое базовое понятие как «поток», но и понятие «разрез».

Определение 3.8. Пусть G(X,U, f,c) – сеть с нестандартной достижимостью, s – источник, t – сток, max – максимальный поток в такой сети. Разрезом сети будем называть такое подмножество дуг графа, удаление которого разрывает все пути потока max. Пропускной способностью разреза будем называть величину потока через этот разрез Заметим, что таким образом определенный разрез может вообще не являться разрезом в обычном понимании, поскольку пути, которые не являются допустимыми, он может и не разрывать.

Завершает главу параграф 3.3, в котором рассмотрено семейство сетей с барьерной достижимостью (h – высота барьеров сети):

G(X,U U0 U UB, f,h), h N, s источник, t сток, X , U .

Для каждой сети семейства можно говорить о е максимальной пропускной способности max(h), тогда мы имеем числовую последовательность max(h), h N. Доказаны теоремы:

Теорема 3.1. Для любого семейства сетей с барьерной достижимостью имеет место:

max(1) max(2) max(i) (14) Теорема 3.2.

Пусть GX,U UO U UB, f,h,h N,s источник, t сток - семейство сетей с барьерной достижимостью, тогда 0, если множество безбарьерных путей пусто;

limmax(h) h.

максимальному потоку в сети, протекающему через безбарьерные пути.

В главе IV «Динамические потоки в сетях» мы рассматриваем задачи о динамических потоках, т.е. таких, которые могут меняться в дискретном времени. В ней речь не идет о нестандартной достижимости, но техника рассмотрения динамических потоков (временная развертка графа) очень похожа на технику, используемую в случае нестандартной достижимости. В этой главе нами доказана теорема о разложении динамического потока:

Теорема 4.1. Пусть (u,t) динамический поток в сети G(X,U, f,c), равный нулю на всех дугах сети при t 0, тогда для произвольного T N, существуют такие потоки 1(u,t), 2(u,t), для которых выполнены следующие условия:

1. Потоки 1(u,t), 2(u,t) равны нулю на всех дугах сети при t 0;

2. Поток 1(u,t) равен нулю на всех дугах графа при t T ;

3. V,tV1,t,t [0;T];

4. V2,t 0,t [0;T];

5. (u,t) 1(u,t) 2(u,t), t Z.

TЗдесь V (,[T1;T2]) = (e,t), т.е. суммарный поток t =T1uU (r) приходящий в сток за временной промежуток [T1;T2 ].

Обозначим через vmax величину максимального стационарного потока сети. Доказана оценка величины динамического потока:

Теорема 4.2. Пусть (u,t) динамический поток в сети G(X,U, f,c) равный нулю на всех дугах сети при t 0, тогда для произвольного T N имеет место оценка V,[0;T] vmax T. (14) Всплеском потока будем называть такое значение потока, которое превосходит vmax. Обозначим через w(G) - максимальный всплеск в сети, а через (G) - емкость сети, т.е. максимальное количество «вещества», которое может находиться в сети одновременно в результате действия какого-то динамического потока, тогда справедлива теорема:

Теорема 4.3. Имеют место следующие оценки:

1. w(G) vmax ;

2. w(G) c(u) ;

uU (r) 3. w(G) (G);

4. (G) c(u).

uU В главе V «Динамические графы и сети» мы вводим в рассмотрение новые объекты – динамические графы, структура которых меняется в дискретном времени. В определении динамического графа присутствует функция активности дуг, которая и определяет изменяющуюся во времени структуру графа. Показано, что динамические графы также являются графами с нестандартной достижимостью. Этот вид нестандартной достижимости принципиально отличается от рассмотренных до этого тем, что для него отсутствует разбиение множества дуг графа. Вспомогательный граф для этого вида достижимости представляет собой временную развртку и уже по этой причине является бесконечным графом. Завершает эту главу рассмотрение периодических динамических графов, для которых временная развертка является лишь формально бесконечным графом.

В Главе VI «Функции на графах» мы рассмотрели семейства функций Гранди ориентированных и неориентированных графов. Доказанные в этой главе утверждения являются необходимыми и достаточными и позволяют находить эти семейства. Они являются обоснованием алгоритмов нахождения этих семейств.

Теорема 6.1. Пусть g - функция Гранди графа G(X,), содержащего контуры, тогда существует такой бесконтурный частичный граф G(X, ), имеющий туже самую функцию Гранди g.

Следствие из теоремы 6.1. Пусть g - функция Гранди графа G(X,), содержащего контуры, тогда существует максимальный по вложению бесконтурный частичный граф G(X, ), имеющий ту же самую функцию Гранди g.

Теорема 6.2. Пусть g - функция Гранди частичного графа G(X, ) графа G(X,). Для того, чтобы g была функцией Гранди графа G(X,) необходимо и достаточно, чтобы для любых двух вершин x, y несоединен ных дугой на графе G(X, ) и соединенных дугой на графе G(X,) выполнялось условие:

g(x) g(y).

Следствие из теоремы 6.1 и теорема 6.2 позволяют находить семейство функций Гранди ориентированного графа с помощью перебора максимальных по вложению частичных графов, не содержащих контуров.

Теорема 6.3. Пусть G(X,) - неориентированный граф, g - его функция Гранди, тогда существует такая ориентация его дуг, что полученный ориентированный граф не содержит контуров и g является функцией Гранди полученного ориентированного графа (причм единственной).

В приложении 1 «Некоторые сведения о конечных множествах в Z и N» содержатся сведения о строении конечных множеств в Z и N необходимые для рассмотрения динамических периодических графов, а также некоторые тождества для степеней чисел и факториалов, содержащие биномиальные коэффициенты, в том числе аддитивное представление для факториала.

Теорема П. 1. Пусть a b, a,bZ (N), тогда a;b a;b a;b [a 1;b 1]Z Z Z Z. (15) a;b a;b a;b [a 1;b 1]N N N N Теорема П. 1 означает, что в Z и N, фактически, не существует открытых или полуоткрытых промежутков.

Теорема П. 2. Любое непустое ограниченное подмножество A в Z ( N) представляет собой замкнутый промежуток или конечное объединение попарно непересекающихся замкнутых промежутков, т.е.

I ( A) A ai;biZ. (16) iОпределение П. 1. Характеристику IA, фигурирующую в формуле (16) назовем числом связности множества А.

Теорема П.3. Для любого A - ограниченного подмножества ( A mA;nA ) множества Z (N) справедлива оценка:

Z nA mA I(A) 1 (17) Теорема П.4. Для любых ограниченных попарно непересекающихся подмножеств Ai, i 1,2,,K множества Z (N) имеет место равенство:

K K I . (18) Ai IAi i1 i Теорема П.5. Для любого n N имеют место равенства:

ni1 i nm (1) Cn (n i)m, 1 m n 1.

iТеорема П.6. Для любого n N имеет место:

ni n! nn (1)i1Cn(n i)n.

i Теорема П.7. Для любого n N и любого k Z имеет место равенство:

n! (n k)n C1 (n k 1)n Cn (n k 2)n n (19) n n i (1)n Cn (k 1)n (1)i Cn (n k i)n.

iУтверждению теоремы П.7 можно придать следующий «функциональный» смысл. Рассмотрим многочлены, In(x), заданные формулами:

n i i In (x) (1) Cn (x i)n, (20) iтогда имеет место следующая теорема.

Теорема П. 8. Многочлен In(x) принимает в точках n, n 1, n 2, одно и тоже значение равное n!, т.е.

n! In (n) In (n 1) In (n 2) . (21) Из этой теоремы следует, что имеет место, тождество:

n i i n ! (1) Cn (x i)n x.

iТеорема П. 9. Для любых n,k N, xR (C) имеет место равенство:

n 1 2 nk xn Cnk (x 1)n Cnk (x 2)n (1)nk 1 Cnk x (n k). (22) Теорема П.10. Для любых z Z, m,k N, 1 k m 1 имеет место равенство:

k 1 2 m zk Cm (z 1)k Cm (z 2)k (1)m1 Cm z m). (23) Публикации автора по теме диссертации Публикации в изданиях из перечня ВАК РФ российских рецензируемых научных журналов:

1. Ерусалимский Я.М, Логвинов С.Ю. Некоторые задачи достижимости на графах с ограничениями на прохождения по дугам// Известия вузов. Северо- Кавказский регион. Ест.науки.1996.№2(94).С. 14- 2. Ерусалимский Я.М. Общий метод решения задач о достижимости на ориентированных графах// Известия вузов. Северо-Кавказский регион. Ест. Науки. 2000. №3. С. 62-3. Ерусалимский Я.М. Отображения конечных множеств и треугольник Паскаля// Известия вузов. Северо-Кавказский регион. Ест. Науки.

2001. Математическое моделирование. С. 68-4. Ерусалимский Я.М., Скороходов В.А. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях// Известия вузов. Северо-Кавказский регион. Ест. Науки. 2003. №3. С. 3-5. Ерусалимский Я.М., Скороходов В.А. Достижимость на графах с условиями затухания и усиления// Известия вузов. Северо-Кавказский регион. Ест. Науки. 2004. Математика и механика сплошной среды.С.110-16. Ерусалимский Я.М., Скороходов В.А. Общий подход к нестандартной достижимости на ориентированных графах// Известия вузов. СевероКавказский регион. Ест. Науки. 2005.Псевдодифференциальные уравнения и некоторые проблемы математической физики. С. 64 -7. Ерусалимский Я.М. Биномиальные коэффициенты в тождествах для натуральных чисел, факториалов и многочленов// Известия вузов. Северо-Кавказский регион. Ест. Науки. 2008. №5(147). С. 27-8. Ерусалимский Я.М., Светлов Г.Г. Бимосты, библоки, точки бисочленения орграфов //Кибернетика. 1980. №1. С. 37-9. Ерусалимский Я.М. Натанзон Л.В. Графы бимостов, библоков и точек бисочленения //Известия вузов. Северо-Кавказский регион. Ест.науки.

1998. №4. С. 9-12;

10. Ерусалимский Я.М., Водолазов Н.Н. Нестационарный поток в сети/ /Вестник ДГТУ. 2009. т.9, №3. С. 402-411. Ерусалимский Я.М., Водолазов Н.Н. Максимальный всплеск в сети и максимальный объм сети// Известия вузов. Северо-Кавказский регион. Ест. науки. 2010. № 6. С. 9-13;

12. Ерусалимский Я.М. Потоки в сетях с нестандартной достижимостью// Известия вузов. Северо-Кавказский регион. Ест. науки. 2012. № 1.

С.5-Статьи в реферируемых международных изданиях:

13. Erusalimsky I.M. Family of Grandy functions for oriented graphs// Turkish Journal of Mathematics. 1995. v.19, №3. P.269-2Монографии, учебники и учебные пособия:

14. Ерусалимский Я.М. Графы с нестандартной достижимостью: задачи, приложения/Скороходов В.А., Петросян А.Г. Кузьминова М.В.

/Ростов н/Д: Южный федеральный ун-т, 2009.-195 с.

15. Ерусалимский Я.М. Нестандартная достижимость на ориентированных графах. Модели и алгоритмы/Скороходов В./ LAMBERT Academic Publishing (LAP, Saarbrcken, Germany), 2010. 188 р., ISBN 9783-8433-0592-16. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения//М.: «Вузовская книга», 1998.- 280 с.

17. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения/ 5-е изд. перераб. и дополн. //М.: Вузовская книга, 2002,-268 с.

Статьи в приложениях к изданиям из перечня ВАК РФ российских рецензируемых научных журналов:

18. Ерусалимский Я.М., Скороходов В.А. Прибыль от потоков с обратной связью в орсетях с ограничениями на достижимость// Известия вузов.

Северо-Кавказский регион. Ест. науки. 2003. Приложение №8. С.3-19. Ерусалимский Я.М, Скороходов В.А. Потоки в сетях со связанными дугами// Известия вузов. Северо-Кавказский регион. Ест. науки. 2003.

Приложение №8. С. 9-20. Ерусалимский Я.М., Петросян А.Г. Случайные процессы в сетях с биполярной магнитностью//Известия вузов. Северо-Кавказский регион. Ест. науки. 2005. Приложение №11. С.10-Материалы международных и всероссийских конференций:

21. Ерусалимский Я.М. Биномиальные коэффициенты в тождествах для натуральных чисел// Современные методы теории краевых задач. Материалы воронежской весенней математической школы «Понтрягинские чтения – XVII»,- Воронеж: ОАО «Центральное Черноземное книжное издательство», 2006. С. 63-22. Erusalumskiy Y.M. Binomial Coefficients in Equalities for Natural Numbers // International Congress of Mathematicians, Madrid 2006, Abstracts.

p.423. Ерусалимский Я.М., Кузьминова М.В. Динамические периодические графы // Математическое моделирование и биомеханика в современном университете. Труды III всероссийской школы-семинара, Из-во «Терра Принт», Ростов н/Д, 2007. С.39-24. Ерусалимский Я.М., Водолазов Н.Н. Нестационарный и случайный поток в сети// Материалы Воронежской весенней математической школы «Понтрягинские чтения – ХХ, Из-во ВГУ, Воронеж, 2009. С.

56-25. Ерусалимский Я.М., Водолазов Н.Н. NP-полнота задачи нахождения максимального потока в графах с дополнительными ограничениями на достижимость// Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения – ХХI», Воронеж: ВГУ, 2010 (доп. выпуск). С.14-26. Ерусалимский Я.М., Водолазов Н.Н. Полиномиальные алгоритмы нахождения максимального потока в сетях с некоторыми видами нестандартной достижимости// Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения – ХХII», Воронежский государственный университет, Московский государственный университет им. М.В. Ломоносова, математический институт им. В.А. Стеклова РАН, - Воронеж:

Издательско-полиграфический центр Воронежского государственного университета. 2011. С. 62-27. Ерусалимский Я.М. Пространственно-временные фракталы //материалы IV международной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования», Воронеж: Издательско-полиграфический центр Воронежского государственного университета. 2011. С. 62-Другие публикации:

28. Ерусалимский Я.М., Басангова Е.О. Смешанная достижимость на частично-ориентированных графах/ /Деп. В ВИНИТИ, № 5892-29. Ерусалимский Я.М. О функции Гранди графа// Деп в ВИНИТИ, № 1576-30. Ерусалимский Я.М., Басангова Е.О. Смешанная достижимость на частично-ориентированных графах// Вычислительные системы и алгоритмы, Ростов н/Д.: ИРУ, 83. С. 19-31. Ерусалимский Я.М., Басангова Е.О. Частично-ориентированные графы и различные виды смешанной достижимости // Алгебра и дискретная математика, Элиста.:1985. С. 70-32. Ерусалимский Я.М. Эйлеровость графов со смешанной достижимостью// Модели, графы и алгебраические структуры, Элиста, 1989.

С. 45- 33. Ерусалимский Я.М. Смешанная достижимость на графах (общий подход). Эйлеровость графов со смешанной достижимостью // ВИНИТИ, № 2640-В34. Ерусалимский Я.М. Пути с задержками в вершинах на орграфах// Дискретные модели и структуры, Элиста, 91, - С. 57-35. Ерусалимский Я.М.,Гаряева С.А. О функции Гранди орграфов и ядрах его подграфов// Модели и дискретные структуры, Элиста, 93. С.

32-36. Ерусалимский Я.М., Водолазов Н.Н. Поток на графах с ограничениями на достижимость// Труды научной школы И.Б.Симоненко. Ростовна-Дону: Изд-во ЮФУ, 2010. С. 44-







© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.