Переключательные алгоритмы преобразования графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА

Механико-математический факультет

На правах рукописи УДК 519.713; 519.171.4

Лашева Мария Игоревна ПЕРЕКЛЮЧАТЕЛЬНЫЕ АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ ГРАФОВ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 9 МАЙ 2011

Москва — 2011

4846717

Работа выполнена на кафедре Математической .теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М.В. Ломоносова.

Научный руководитель — кандидат физико-математических наук, доцент

Часовских Анатолий Александрович

Официальные оппоненты:

доктор физико-математических наук, профессор Гашков Сергей Борисович кандидат физико-математических наук, доцент Карташов Сергей Иванович

Ведущая организация — Московский энергетический институт (Технический университет)

Защита диссертации состоится 2011 г. в 16 ч. 45 м. на

заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М.В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ имени М.В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан "27" апреля 2011 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор

А.О. Иванов

Общая характеристика работы Актуальность темы

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

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

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

Задача преобразования графов с сохранением степенной последовательности возникает при перечислении всех графических реализаций заданной степенной последовательности. Подобные задачи появились одними из первых в теории графов. Так, например, в 1875 г. А. Кэли, изучая проблему построения изомеров насыщенных углеводородов по их формуле, перечислял различные возможные деревья со степенями вершин 1 и 42.

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

'Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Изд-во Наука, 1990.

2А. Cayley. Brit. Assoc. Adv. Sei, Reports, p. 275,1875.

3R. B. Egglton, D. A. Holton. Graphic sequences. Lecture Notes in Mathematics, vol. 748, Springer, Berlin, p. 1-10,1978.

свойствами соответствующих графов. Исторически, в первую очередь исследуются способы определения возможных псевдографических реализаций1 заданной степенной последовательности. Для этого в своей работе 1951 г. при построении конструктивных доказательств Дж. Сениор определяет и использует операцию «передачи» ребер, сохраняющую степенную последовательность псевдографа. Затем в 1962 г. С. Хакими формулирует задачу построения всех мультиграфов с заданной степенной последовательностью5 как различных возможных структурных моделей данной органической молекулы, восстанавливаемых по ее формуле. Он описывает способ восстановления мультиграфа по степенной последовательности и использует операцию «d-элементарного преобразования» ребер для дальнейшего преобразования этого мультиграфа к любому другому с той же степенной последовательностью. При этом несколько ранее, в 1955 г., В. Гавел решает теоретическую задачу построения всех возможных неориентированных графов по заданной степенной последовательности и описывает алгоритм, при помощи которого можно восстановить неориентированный граф по его степенной последовательности, а затем, используя операцию переключения ребер, получить любой другой неориентированный граф с той же степенной последовательностью6. Процедура восстановления графа получила в литературе название процедуры Гавела-Хакими, а алгоритм преобразования от одного графа с заданной степенной последовательностью к любому другому с той же степенной пследовательностью стал называться алгоритмом Б. Гавела. Итак, алгоритм В. Гавела осуществляет преобразования неориентированных графов без петель и кратных ребер путем последовательного выполнения операций переключения ребер, не допускающих возникновения кратных ребер и петель. Важно, что существенным ограничением этого алгоритма является необходимость знания глобальных характеристик задаваемых графов, а следовательно, расширения либо оперативной, либо внешней памяти алгоритма.

Однако это ограничение преодолимо: если для вычисления необходимой цепочки операций переключения ребер использовать конечный автомат7, блуждающий по графу, ту же задачу можно решать алгоритмом специального вида с фиксированной оперативной и внешней памятью. Такие алгоритмы названы в диссертации переключательными. Использование переключательного алгоритма, в отличие от алгоритма В. Гавела, не потребует изучения глобальных характеристик графов, а только лишь знания их локальных свойств [1]. Более того, переключательный алгоритм для решения задачи преобразования неориентированных графов без петель и кратных ребер с п вершинами, степень

4Senior J. К. Partitions and their Representative Graphs. Amer. Jour. Math., vol.73, p. 663 - 689,1951.

5Hakimi S. L. On readability of a set of integers аз degrees of the vertices of a linear graphs. I.J. Soc. Indust. Appl. Math. 1962. 10, N 3., p. 496 - 506.

'Гавел В.Заметка о существовании конечных графов. Cas. Pest. Mat. 1955. 80, N 4., p. 477 - 481.

7Кудрявцев В- Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.:Наука. 1985.

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

Такой подход позволил автору решить подобные задачи построения переключательных алгоритмов преобразования ориентированных графов и гиперграфов8 [1]. При этом под степенной последовательностью для ориентированных графов понимается конечная последовательность пар полустепеней входящих и исходящих ребер, лексикографически упорядоченная по невозрастанию. Отметим, что в 1957 г. Г. Райзер рассматривал операцию замены, при которой в орграфе без кратных ориентированных ребер возможно переключение ребер с сохранением степенной последовательности, допуская при этом возникновение ориентированных петель. Он доказал, что, используя эту операцию, любой орграф без кратных ориентированных ребер может быть переведен в любой другой такой орграф, имеющий ту же степенную последовательность9. В диссертации введена операция переключения для орграфов, не допускающая образования петель и кратных ориентированных ребер. Используя введенную операцию переключения, построен переключательный алгоритм, который для орграфов без петель и кратных ребер с п вершинами, сумма полустепеней по входящим и исходящим ребрам каждой из которых не превосходит к, дает возможность осуществить переход от одного ориентированного графа с к другому с сохранением степенной последовательности за время не более 0(fc2n2). Затем введено обобщение операции переключения гиперребер в гиперграфе и построен переключательный алгоритм, который для гиперграфов с п вершинами, степень каждой из которых не больше к, и гиперребрами, каждое из которых содержит не болеет вершин, по порядку не превосходит 0((гпах(к,т))222п). Таким образом, переключательные алгоритмы могут быть использованы для оптимизации свойств компьютерных сетей с заданным множеством провайдеров и ограничениями на коммутационные возможности каждого из них, и их использование не потребует изучения глобальных характеристик всей сети, а только лишь знания ее локальных свойств.

В 1978 г. Р. Эгглтоном и Д. Холтоном10 введено понятие графа реализаций степенной последовательности d(n) = (di, ...,dn),di > •■■ > dn > 0. Граф реализаций £H(d(n)) - непустой неориентированный граф, имеющий своими вершинами различные отмеченные графические реализации, при этом ребро между двумя вершинами существует тогда и только тогда, когда существует операция переключения ребер, переводящая одну вершину (т. е.

8А. А. Зыков. Гиперграфы. Успехи математических наук, 6,180,1972.

'Ryser H. J. Combinatorial Properties of Matrices of Zeros and Ones. Canadian Journal of Mathematics, 9, p. 371 -377,1957.

10R. B. Egglton, D. A. Holton. Graphic sequences. Lecture Notes in Mathematics, vol. 748, Springer, Berlin, p.

1-10,1978.

отмеченный граф) в другую. Из результатов, полученных В. Гавелом, вытекает связность графа реализаций для любого п. В приложениях теории графов, как правило, изучаются статистические характеристики множества всех графических реализаций заданной степенной последовательности11. В диссертации автором исследованы некоторые метрические характеристики графа реализаций, такие как порядок роста диаметра графа12 и максимальной степени вершины [1]. А именно, построены последовательности степенных последовательностей d(4), d(5),..., d(n),..., графы реализаций R(d(n)) которых имеют диаметр, равный Cjn2 для некоторого С\, а также построены последовательности степенных последовательностей d'(4), d'(5),..., d'(n),графы реализаций R(d'(n)) которых имеют максимальную степень вершин, равную С2п4 для некоторого Съ-

При изучении расположения графических реализаций в графе реализаций в зависимости от их свойств возникает задача определения переключательно-полных свойств графов13. А именно, пусть Р есть некоторое непустое графовое свойство. Обозначим üK(d(n),P) порожденный подграф14 графа реализаций Dt(d(n)), образованный всеми вершинами со свойством Р. Свойство Р, для которого граф Ü\(d(n),P) связен, называется переключательно-полным.

Приведем примеры некоторых переключательно-полных свойств. В 1977 г. Ч. Колборн показал переключательную полноту свойства быть деревом15. В 1982 г. М. Сислоу построил алгоритм перехода от одного уницикла к любому другому с сохранением степенной последовательности и свойства уницикличности16. В те же годы Р. Тэйлор доказал, что свойства связности и вершинной двусвязности графов являются переключательно-полными17'18. Отметим, что для описанных переключательно-полных свойств существуют алгоритмы восстановления графа по степенной последовательности с заданным свойством19. В перечисленных работах доказательства переключательной полноты основаны на построении алгоритмов, осуществляющих переход с помощью операции переключения ребер от произвольного графа с заданным свойством к любому другому графу с таким свойством, причем применение операции переключения сохраняет заданное свойство. Алгоритмы эти, как

"A. Sinclair. Algorithm} for Random Generation and Counting. A Markov Chain Approach. Birkhauser Boston, 1993.

I50. Ope. Теория графов. M., Изд-во Наука, 1980.

13 А. А. Черняк. Переключательно-полные свойства графов. Изв. АН БССР. Сер. физ.-мат. наук., N 1, стр. 29 - 35,1985.

14А. А. Зыков. Основы теории графов. М., Изд-во Наука, 1987.

15Colboum С. J. Research Report Сс-77-37, University of Waterloo, p. 200,1977.

"Syslo M. M. On tree and unicychc realizations of degree sequences. Demonstratio Mathematica, v.15, N4, 1982. Warsaw Technical University Institute of Mathematics.

17Taylor R. Constrained switchings in graphs. Mathematics Research Report, N 27, 1980. Department of Mathematics, University of Melbourne.

18Taylor R. Switchings Constrained to ¡-Connectivity in Simple Graphs. SIAM J. Algebraic Discrete Methods, 3, N 1, p. 114-121,1982.

18D. L. Wang, D. J. Kleitman. On the existence of n-connected graphs with prescribed degrees. The journal of

mathematics and physics, v.55, N1,1976.

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

Известно, что существуют свойства графов, не являющиеся переключательно-полными21. Поскольку некоторые органические молекулы могут быть представлены как плоские графы22, в диссертации был исследован вопрос переключательной полноты свойства планарности. Автором показано, что свойство планарности переключательно-полным не является.

Цель работы

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

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

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

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

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

30А. А. Черняк. Связность графов с предписанным степенным множеством и порядком. ДАН БССР, N 5, 29,1984.

21Colbourn С. J. Research Report Сс-77-37, University of Waterloo, p. 200,1977.

г2Р. Басакер, Т. Саати. Конечные графы и сети. М.; Изд-во Наука, 1974.

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

Структура и объем диссертации

Диссертационная работа изложена на 93 страницах и состоит из введения и

3 глав, разделенных на параграфы. Библиография включает 30 наименований.

Научная новизна

1. Построен переключательный алгоритм для преобразования неориентированных графов с сохранением степенной последовательности. Доказано, что такой алгоритм при естественном ограничении на степень вершины имеет более оптимальные временные характеристики и характеристики памяти по сравнению с ранее известным алгоритмом В. Гавела.

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

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

4. Решены задачи построения переключательных алгоритмов для преобразования неориентированных графов с сохранением степенной последовательности и заданного переключательно-полного свойства для следующих свойств: свойства «быть деревом», свойства уницикличности, свойства связности и двусвязности. Исследовано свойство планарности на переключательную полноту.

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

Основные методы исследования

В диссертации использованы методы теории автоматов, теории графов и теории алгоритмов.

Теоретическая и практическая ценность работы

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

Апробация работы

Результаты диссертации докладывались на конференциях и семинарах механико-математического факультета МГУ имени М. В. Ломоносова: на семинаре «Теория автоматов» под руководством академика, профессора В. Б. Кудрявцева (неоднократно в 2007-2011 гг.), на семинаре «Нейронные сети» под руководством доцента А. А. Часовских (неоднократно 2004-2011 гг.), на семинаре «Математические вопросы кибернетики» под руководством профессора О. М. Касим-Заде (2011 г.), на семинаре «Дискретный анализ» под руководством профессора В. А. Буевича и С. В. Алешина (2006 г.), на семинаре «Вопросы сложности алгоритмов поиска» под руководством профессора Э. Э. Гасанова (2006 г.). Также результаты докладывались на следующих конференциях:

IX международная конференция «Интеллектуальные системы и компьютерные науки» (Москва, МГУ имени М. В. Ломоносова, 2006 г.);

IX Международный семинар «Дискретная математика и ее приложения», посвященный 75-летию со дня рождения академика О. Б. Лупанова (Москва, МГУ имени М. В. Ломоносова, 2007 г.);

третья и четвертая научная конференция студентов и аспирантов кафедры МаТИС механико-математического факультета МГУ (Москва, МГУ имени М. В. Ломоносова, 2007 и 2008 гг.);

международная конференция «Современные проблемы математики, механики и их приложений», посвященная 70-летию ректора МГУ академика В. А. Садовничего (Москва, МГУ имени М. В. Ломоносова, 2009 г.);

научная конференция «Ломоносовские чтения» (Москва, МГУ имени М. В. Ломоносова, 2008 и 2009 гг.);

международная научная конференция «Ломоносов-2009» (Москва, МГУ имени М. В. Ломоносова, 2009 г.).

Публикации по теме диссертации

Основные результаты работы опубликованы в пяти статьях[1-5]. Краткое содержание работы

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

Глава 1

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

В параграфе 1.1 даются основные определения и формулируется постановка задачи преобразования неориентированных графов без петель и кратных ребер с сохранением степенной последовательности, а также вводится операция ш следующим образом. Пусть d(n)— графичная последовательность23. Через M(d(n)) обозначим множество всех графов со степенной последовательностью d(n). Положим M(d(n)) = {G : граф G получен нумерацией вершин некоторого графа из M(d(n)), последовательность степеней вершин которого, выписанная в порядке возрастания номеров, совпадает с d(n)}.

Пусть A{d{n)) С M(d(n)).

При п > 4 определим операцию

w(A(d(n))) = {G'| 3 G = (V,E) e A(d{n)), 3 6 V,

{ui,v2},{u3,M € E, i E,

G' = (V, (E U { {,*,.*}, Vi} }) \ { {vhv2}, {v3, V4} })}.

Операция ш не меняет степенную последовательность.

Таким образом, k>(A(d(n))) состоит из всех графов, которые могут быть получены из элементов множества A(d(ri)) однократным применением операции переключения ребер.

Будем говорить, что операция переключения применима в графе G = (V, Е) к некоторой паре ребер {1^,1^}, {vjít vj2}, если в графе G не существует ребер

23Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Изд-во Наука, 1990.

{u»i>47i)>{u¿3i4»}' или если в гРаФе G не существует ребер {^,1),,},{'^.Ч?',}-Если операция переключения применима к паре ребер {и^, t'¿s}, {vjlt u,-2}, то будем также говорить, в первом случае, что ребра {t^, {vjnvj2} переключаются на ребра {fíp v^}, {t>i2, Vj,}, или, во втором случае, на ребра {v^, Vj3}, Vj,}.

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

Зафиксируем натуральное число Р, Р > 4, и рассмотрим конечное множество

L{P) = ЕР+1 х ЕР+1 ■х.Е2хЕгхЕ3.

Рассмотрим множество матриц 00

м(р) = = (mtfW.>my е L{P),i = T¡ñ,j = T7ñ>.

n=4

Обозначим через Г2 множество пар {Gi,^} неориентированных графов с занумерованными вершинами, у которых совпадают степенные последовательности.

Зафиксируем п и отобразим взаимно однозначно множество пар

(Gb G2) 6 Г2, Gi = (Vi, Wi), = «,» = 1,2,

в некоторое подмножество множества

{М = (TOij)„,n)m„ 6 L(P),i = Tji,j = T~ñ};

обозначим этот образ и зададим множество

00

п=4

Зададим инициальный конечный автомат

Г = {L{P),Em,L{P) х Et,<p,il>,qo).

Конечный автомат Т применяется к матрице М € М^ в следующем смысле.

1) Обозначим М = М<°> = (

mij )п,п• В момент времени 0 автомат Т находится в состоянии 5о, и на вход ему поступает элемент т^. Выходом является некоторый элемент из множества L(P); обозначим его m'n. Автомат переходит в состояние Яг-

2) Обозначим М(1) = (m¡f)n,n, где = т'и и m¡f = m¡f для любых г = 2= 2,..., п. Автомат Т в момент времени 1 находится в состоянии qi, и на вход ему поступает некоторый элемент € {m^m^}- Выходом является

некоторый элемент из множества Ь(Р)\ обозначим его т'ы. Автомат Т переходит в состояние

3) I > 2.

Определим окрестность Ы(тпу) элемента ту для любого 4 > 2 :

ЛГ(гг$) = {т^тЗ+^т^^ш« ¿.тЦ^} при 1 < г < п, 1 < 3 < п;

Щт(ф = {т^т^т^т^} при 1<з< п;

= , т«-1,; 1 тп1 } при 1 < з < щ

Щгг$) = при 1 < » < п;

^Къ) = при 1 < г < п;

ЛГ(т«) = {т<(> т$,т<?};

Положим р = к,г = I. Обозначим М® = (ту )„,„, где = Гоу_1) для

любых г = 1,...,п,г ф V,0 — 1>—Ф г, и ^рт = гп'ы. В момент времени I автомат Т находится в некотором состоянии и на вход ему поступает элемент из окрестности

например, , Выходом является некоторый элемент из множества Ь(Р); обозначим его т'ы. Автомат Т переходит в состояние qt+l.

4) Работа автомата Т заканчивается, когда он переходит в конечное состояние д* = q3. Полученную при этом матрицу М'8-1' обозначим через Т(М).

Определение. Переключательный алгоритм 21 - это пара (Т,МР), такая что для любого натурального п > 4 и для любой матрицы М € выполнено Т{М) €

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

Алгоритм 211 реализует следующую идею. Вершины графов С?;, г — 1,2, с одинаковыми степенными последовательностями нумеруются в порядке невозрастания их степеней. Матрица М^ = (а®)пхп определяется парой этих графов, а по элементам ау' определяется наличие ребер между г-й и 3-й вершинами как в графе С?1, так и в графе С?2- Исходя из пары занумерованных графов Сг, автомат Т находит два ребра, принадлежащие либо С\. либо <?2, такие что, применив к ним операцию ш, получим пару занумерованных графов с большим числом соответствующих ребер. При этом соответствующими называем ребра занумерованных графов ©1,62, соединяющие вершины с одинаковыми номерами. Эта процедура продолжается до тех пор, пока автомат Т не

преобразует исходную матрицу к матрице, соответствующей паре изоморфных залумерованных графов. Итак, в параграфе 1.2 доказаны следующие теоремы.

Теорема 2. Для любой пары занумерованных графов <3ь С?2 с одинаковой степенной последовательностью переключательный алгоритм Щ строит пару изоморфных занумерованных графов Сц С2.

Теорема 3. Время работы переключательного алгоритма 21х для пары занумерованных графов с п вершинами, степень каждой из которых не более к, не превосходит 0(к2п2).

При фиксированном к эта оценка лучше, чем оценка 0(n2log2n) для алгоритма В. Гавела.

Размер задачи определим' как количество элементов квадратной матрицы М® = (40))пхп, т. е. п2.

Теорема 5. Объем внешней памяти, необходимый для работы переключательного алгоритма Щ, равен размеру задачи.

В параграфе 1.3 изучается задача преобразования орграфов без петель и кратных дуг с сохранением степенной последовательности. В этом случае под степенной последовательностью понимается конечная последовательность пар входящих и исходящих ребер, лексикографически упорядоченная по не возрастанию. Вводится операция переключения для орграфов, не допускающая образования петель (в отличие от операции, ранее рассмотренной Райзером) и кратных дуг. Далее обобщается операция и>, не меняющая такую степенную последовательность, строится переключательный алгоритм 21' и доказываются следующие теоремы.

Теорема 7. Для любой пары занумерованных орграфов Су. с одинаковой степенной послеовательностью переключательный алгоритм Щ строит пару изоморфных занумерованных орграфов С^С^.

Теорема 8. Время работы переключательного алгоритма 21г для пары занумерованных графов с п вершинами, степень каждой из которых не более к, не превосходит 0(к2п2).

Теорема 10. Объем внешней памяти, необходимый для работы переключательного алгоритма 21г, равен размеру задачи.

В параграфе 1.4 обобщается операция переключения для гиперграфов, а затем строится взаимно однозначное отображение д из множества гиперграфов в некоторое подмножество ориентированных графов следующим образом. Построим ориентированный граф д(Н) = Нд = (Уд,Ед) для гиперграфа Н = (У,Е) : пусть \У\ = т, |£| = п, V = {ы, ...,ут} ,Е = {еъ...,еп}, тогда Уд = У и {ц, ...,!„}, Ед = Е1и...иЕп,гдеЕг= и < » < п.

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

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

Теорема 12. Для любой пары занумерованных гиперграфов (?1, Сг с одинаковой степенной послеовательностью переключательный алгоритм 21з строит мру изоморфных занумерованных орграфов С2.

Теорема 13. Время работы переключательного алгоритма 21з для пары занумерованных графов с п вершинами, степень каждой из которых не более к, и гиперербрами, каждое из которых содержит не более т вершин, не превосходит 0((тах(к,т))222п).

Теорема 14. Объем внешней памяти, необходимый для работы переключательного алгоритма 213, равен размеру задачи.

Глава 2

Во второй главе изучаются основные метрические свойства графа реализаций степенной последовательности с1(п).

Рассмотрим неориентированный граф б = (V, Е),\У\ = п, обозначим ¿(п) степенную последовательность графа в. Занумеруем некоторым образом все его вершины и получим занумерованный граф, например Рассмотрим множество всех занумерованных графов {С1,...,С7т}, имеющих степенную последовательность <1{п).

Графом реализаций для данной степенной последовательности ё(п) называется непустой неориентированный граф Л(й(п)) = {Уц. Ея), такой что = {Сь..., Ст}, {в,, € Ец тогда и только тогда, когда в графе С?; существует пара ребер, к которым применима операция шив результате ее применения получается граф С^-.

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

Теорема 15. Граф реализаций обладает следующими свойствами:

Свойство 1. Существует последовательность степенных последовательностей

таких что диаметры графов реализаций сИат(11((1(п))) х п2.

Свойство 2. Существует последовательность степенных последовательностей <¿(4),<¿(5), ...,й(п),..., таких что такйеду х п4.

Глава 3

При изучении расположения графических реализаций в графе реализаций в зависимости от их свойств возникает задача определения переключательно-полных свойств графов. Пусть Р есть некоторое непустое графовое свойство, то есть Р С Уд. Обозначим Щд,(п),Р) порожденный подграф графа 9Я(с[(п)), образованный всеми вершинами со свойством Р. Свойство Р, для которого граф ¡Я(а!(п), Р) связен, называется переключательно-полным.

В третьей главе рассматриваются задачи построения переключательных алгоритмов преобразования графов с сохранением степенной последовательности и заданного переключательно-полного свойства для известных переключателько-полных свойств.

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

Параграф 3.2 посвящен решению задачи построения переключательного алгоритма, преобразующего деревья с сохранением степенной последовательности и свойства "быть деревом". Рассмотрим некоторое подмножество Т(е((п)) множества деревьев 1(с1(п)). При п > 4 определим операцию

ы*(ВДп))) = {Т е ЗДп))| 3 Т = (V, Е) 6 т№)), Зу1,У2,У3,Уа в V, {иьЧгЫ^з,^} 6 Е, {VI, 1*}, £ Е, Г = {V, (Е и { К К "4} }) \ { К М, К «4} })}• Операция ш* не меняет степенную последовательность и сохраняет свойство "быть деревом".

Будем говорить, что операция ограниченного переключения применима в дереве Т = (V, Е) к некоторой паре ребер {1>;1,«;2},{'-|.>1>г;л}> если в Дереве Т не существует ребер {и^, г^}, {«¿2, г^2}, и граф

Т' = (V, (Е и { Н,ил}, {«ь, }) \ { {«,,,««}, })

является деревом, или если в дереве Т не существует ребер {г^^ЛД^Чп}! 15 граф

Т' = (V, (Е и { К, К, }) \ { К,«,,}, К,г;;2} })

является деревом.

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

Теорема 17. Для любой пары занумерованных деревьев Ti, с одинаковыми степенными последовательностями переключательный алгоритм 01т строит пару изоморфных занумерованных деревьев Т{, Т2.

Теорема 19. Временная сложность работы переключательного алгоритма Я1Т для пары занумерованных деревьев сп вершинами, не превосходит О(п2).

Теорема 20. Объем внешней внешней памяти переключательного алгоритма 21г совпадает с размером задачи.

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

Теорема 22. Для любой пары занумерованных унициклов U\, U2 с одинаковыми степенными последовательностями переключательный алгоритм 21 г; строит пару изоморфных занумерованных унициклов U[, U2.

Теорема 24. Временная сложность работы переключательного алгоритма 21и для пары занумерованных унициклов сп вершинами, не превосходит 0(п2).

Теорема 25. Объем внешней внешней памяти переключательного алгоритма 21ц совпадает с размером задачи.

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

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

Теорема 28. Для любой пары занумерованных связных графов Су,С2 с одинаковыми степенными последовательностями переключательный алгоритм 2tc строит пару изоморфных занумерованных связных графов С[, С'2.

Теорема 30. Временная сложность работы переключательного алгоритма 21р для пары занумерованных связных графов с п вершинами, не превосходит 0(п2).

Теорема 31. Объем внешней памяти переключательного алгоритма 21 с совпадает с размером задачи.

Теорема 33. Для любой пары занумерованных двусвязных графов ВСу, BCi с одинаковыми степенными последовательностями переключательный алгоритм 21 вс строит пару изоморфных занумерованных двусвязных графов ВС[,ВС'2.

Теорема 35. Временная сложность работы переключательного алгоритма 21 вс для пары занумерованных двусвязных графов с п вершинами, степень каждой из которых не более к, не превосходит 0(fc2n2).

Теорема 36. Объем внешней памяти переключательного алгоритма 21 вс совпадает с размером задачи.

Благодарности

Автор благодарит своего научного руководителя кандидата физико-математических наук, доцента Часовских Анатолия Александровича за постановку задачи и помощь в работе. Автор выражает глубокую благодарность заведующему кафедрой академику, профессору Кудрявцеву Валерию Борисовичу, доктору физико-математических наук, профессору Буевичу Вячеславу Александровичу, доктору физико-математических наук, профессору Гасанову Эльяру Эльдаровичу, доктору физико-математических, наук, профессору Подколзину Александру Сергеевичу и всем сотрудникам кафедры Математической теории интеллектуальных систем за постоянное внимание и творческую атмосферу, способствующую работе.

Работы по теме диссертации

[1] Лашева М.И. Об алгебраических операциях на графах, сохраняющих степенную последовательность. М., Интеллектуальные системы том 11, выпуск 1-4, 2007. Стр. 551-592.

[2] Лашева М.И. Об алгебраических операциях на графах, сохраняющих степенную последовательность. М., Материалы 9 Международного семинара "Дискретная математика и её приложения посвященного 75-летию со дня рождения академика О. Б. Лупанова, 2007. Стр. 331-333.

[3] Lasheva M.I. Оп graph transformation algorithms keeping the same degree sequence. Tashkent, Uzbekistan, Fifth World Conference on Intelligent Systems for Industrial Automation. November 25-27, 2008. Proceedings: 455-456.

[4] Лашева М.И. Об алгебраических операциях на графах, сохраняющих степенную последовательность. М., Вестн. Моск. Ун-та. Сер.1, Математика. Механика. 2009. №5, стр. 48-50.

[5] Лашева М.И. Об алгебраических операциях на графах, сохраняющих степенную последовательность. М., Материалы международной

конференции "Современные проблемы математики, механики и приложений посвященная 70-летию ректора МГУ академика В. Садовничего, 2009. Стр. 363-364.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ¡РОэкз. Заказ № 23

Введение.

Глава 1. Использование переключательных алгоритмов для преобразования графов с сохранением степенной последовательности

1.1. Операция переключения ребер.

1.2. Постановка задачи преобразования графов с сохранением степенной последовательности. Описание алгоритма

1.3. Теорема о построении переключательного алгоритма для преобразования неориентированных графов с сохранением степенной последовательности.

1.4. Теорема о построении переключательного алгоритма для преобразования ориентированных графов с сохранением степенной последовательности.

1.5. Теорема о построении переключательного алгоритма для преобразования гиперграфов с сохранением степенной последовательности

Глава 2. О метрических свойствах графа реализаций.

2.1. Понятие графа реализаций.

2.2. Теорема о некоторых метрических свойствах графа реализаций

Глава 3. О переключательных алгоритмах преобразования графов с сохранением переключательно-полного графового свойства и степенной последовательности.

3.1. Понятие переключательно-полного графового свойства. Примеры переключательно-полных свойств

3.2. Теорема о построении переключательного алгоритма преобразования деревьев с сохранением степенной последовательности

3.3. Построение переключательного алгоритма преобразования унициклов с сохранением степенной последовательности

3.4. Пример графового свойства, не являющегося переключательно-полным.

3.5. Построение переключательного алгоритма преобразования связных графов с сохранением степенной последовательности

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

Степенной последовательностью неориентированного графа называется набор степеней всех его вершин [2], упорядоченный по невозрастанию. В общем случае существует несколько неизоморфных графов, обладающих заданной степенной последовательностью. Связь между ними можно установить с помощью подходящей цепочки операций переключения ребер, сохраняющих степенную последовательность [23].

Задача преобразования графов с сохранением степенной последовательности возникает при перечислении всех графических реализаций заданной степенной последовательности. Подобные задачи появились одними из первых в теории графов. Так, например, в 1875 г. А. Кэли, изучая проблему построения изомеров насыщенных углеводородов по их формуле, перечислял различные возможные деревья со степенями вершин 1 и 4 [9].

Для произвольного конечного набора натуральных чисел, упорядоченных по невозрастанию, можно определить, существует ли графическая реализация со степенной последовательностью, совпадающей с этим набором [15]. При этом в качестве графических реализаций рассматриваются различные графовые структуры: неориентированные графы, орграфы, мультиграфы, псевдографы. Такой выбор типа изучаемых графов обусловлен их приложениями в решении теоретических задач органической химии, так как многие свойства моделируемых органических молекул часто объясняются структурными свойствами соответствующих графов. Исторически, в первую очередь исследуются способы определения возможных псевдографических реализаций [10] заданной степенной последовательности. Для этого в своей работе 1951 г. при построении конструктивных доказательств Дж. Сениор определяет и использует операцию «передачи» ребер, сохраняющую степенную последовательность псевдографа. Затем в 1962 г. С. Хакими формулирует задачу построения всех мультиграфов с заданной степенной последовательностью [11] как различных возможных структурных моделей данной органической молекулы, восстанавливаемых по ее формуле. Он описывает способ восстановления мультиграфа по степенной последовательности и использует операцию «(¿-элементарного преобразования» ребер для дальнейшего преобразования этого мультиграфа к любому другому с той же степенной последовательностью. При этом несколько ранее, в 1955 г., В. Гавел решает теоретическую задачу построения всех возможных неориентированных графов по заданной степенной последовательности и описывает алгоритм, при помощи которого можно восстановить неориентированный граф по его степенной последовательности, а затем, используя операцию переключения ребер, получить любой другой неориентированный граф с той же степенной последовательностью [12]. Процедура восстановления графа получила в литературе название процедуры Гавела-Хакими, а алгоритм преобразования от одного графа с заданной степенной последовательностью к любому другому с той же степенной пследовательностыо стал называться алгоритмом В. Гавела. Итак, алгоритм В. Гавела осуществляет преобразования неориентированных графов без петель и кратных ребер путем последовательного выполнения операций переключения ребер, не допускающих возникновения кратных ребер и петель. Более точно, эта задача формулируется следующим образом. Пусть С = (V, Е) - граф, а, 6, с, в, - четыре различные его вершины такие, что {а, Ь},{с, с!,} е Е, {а,с},{Ь,с1} ф. Е. Тогда говорят, что граф допускает переключение {{а, 6}, {с, б?}}, а результатом применения операции переключения {{а, &}, {с, с/}} является граф С = (У:Е'),Е' = (Е и {{а,с},{М}}) \ {{а,Ь},{с,с1}}. Важно, что существенным ограничением алгоритма В. Гавела является необходимость знания глобальных характеристик задаваемых графов, а следовательно, расширения либо оперативной, либо внешней памяти алгоритма.

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

Автором построен переключательный алгоритм, решающий для всех графов ту лее задачу с фиксированной оперативной и внешней памятью. А именно, в Главе 1 введено понятие переключательного алгоритма и построен такой переключательный алгоритм, который для решения описанной задачи для неориентированных графов без петель и кратных ребер с п вершинами, степень каждой из которых не превосходит /с, дает возможность осуществить указанный переход за время не более 0(к2п2). При фиксированном к эта оценка лучше, чем оценка 0(п21о^2п), вытекающая из описания алгоритма В. Гавела.

Далее построены переключательные алгоритмы, обобщающие задачу В. Гавела на случай ориентированных графов и гиперграфов [б]. При этом под степенной последовательностью для ориентированных графов понимается конечная последовательность пар полустепеней входящих и исходящих ребер, лексикографически упорядоченная по невозрастанию. Отметим, что в 1957 г. Г. Райзер рассматривал операцию замены, при которой в орграфе без кратных ориентированных ребер возможно переключение ребер с сохранением степенной последовательности, допуская при этом возникновение ориентированных петель. Он доказал, что, используя эту операцию, любой орграф без кратных ориентированных ребер может быть переведен в любой другой такой орграф, имеющий ту же степенную последовательность [13], [14]. Автором была введена операция переключения для орграфов, не допускающая образования петель и кратных ориентированных ребер. Используя введенную операцию переключения, построен переключательный алгоритм, который для орграфов без петель и кратных ребер с п вершинами, сумма полустепеней по входящим и исходящим ребрам каждой из которых не превосходит дает возможность осуществить переход от одного ориентированного графа с к другому с сохранением степенной последовательности за время не более 0(к2п2). Затем введено обобщение операции переключения гиперребер в гиперграфе и построен переключательный алгоритм, который для гиперграфов с п вершинами, степень каждой из которых не больше к, и гиперребрами, каждое из которых содержит не более т вершин, по порядку не превосходит 0((тах(к, т))222п).

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

В 1978 г. Р. Эгглтоном и Д. Холтоном в работе [15] вводится понятие графа реализаций для степенной последовательности (¿(п) = (<¿1,., в,п), >

• •• > > 0. Граф реализаций 9\(с1(п)) - непустой неориентированный граф, имеющий своими вершинами различные отмеченные графические реализации, при этом ребро между двумя вершинами существует тогда и только тогда, когда существует операция переключения ребер, переводящая одну вершину (т. е. отмеченный граф) в другую. Из результатов, полученных В. Гавелом [12], вытекает связность графа реализаций для любого п. В приложениях теории графов, как правило, изучаются статистические характеристики множества всех графических реализаций заданной степенной последовательности [24]. В Главе 2 автором исследованы некоторые метрические характеристики графа реализаций, такие как порядок роста диаметра графа [8] и максимальной степени вершины. А именно, построены последовательности степенных последовательностей ¿(4), <¿(5),., б?(п),графы реализаций Я(с1(п)) которых имеют диаметр, равный С\п2 для некоторого С\, а также построены последовательности степенных последовательностей <¿'(4), ¿2'(5),., (1'{п),., графы реализаций которых имеют максимальную степень вершин, равную Сгп4 для некоторого С2.

Другими словами, граф реализаций описывает множество графических реализаций произвольной степенной последовательности, эффективным инструментом исследования которого является операция переключения ребер. При изучении расположения графических реализаций в графе реализаций в зависимости от их свойств возникает задача определения переключательно-полных свойств графов [16]. А именно, пусть Р есть некоторое непустое графовое свойство. Обозначим Ж(с1(п), Р) порожденный подграф [4] графа реализаций £Н(с2(п)), образованный всеми вершинами со свойством Р. Свойство Р, для которого граф *Я(с1(п),Р) связен, называется переключательно-полным.

Приведем примеры некоторых переключательно-полных свойств. В 1977 г. Ч. Колборн показал переключательную полноту свойства быть деревом [21]. В 1982 г. М. Сислоу построил алгоритм перехода от одного уницикла к любому другому с сохранением степенной последовательности и свойства уницикличности [18]. В те же годы Р. Тэйлор доказал, что свойства связности и вершинной двусвязности графов являются переключательно-полными, соответственно в [19] и [20]. Отметим, что для описанных переключательно-полных свойств существуют алгоритмы восстановления графа по степенной последовательности с заданным свойством [25]. В перечисленных работах доказательства переключательной полноты основаны на построении алгоритмов, осуществляющих переход с помощью операции переключения ребер от произвольного графа с заданным свойством к любому другому графу с таким свойством, причем применение операции переключения сохраняет заданное свойство. Алгоритмы эти, как и алгоритм В. Гавела, обладают ограничением: для их работы необходимо знание глобальных характеристик задаваемых графов, а следовательно, расширение либо оперативной, либо внешней памяти алгоритмов. В Главе 3 автором решена задача построения соответствующих переключательных алгоритмов, преобразующих графы с сохранением заданного переключательно-полного свойства и степенной последовательности. Вопросы переключательной полноты различных свойств, касающихся связности графов, могут быть применимы в теории надежности сложных систем [17].

Известно, что существуют свойства графов, не являющиеся переключательно-полными [21]. Поскольку некоторые органические молекулы могут быть представлены как плоские графы [22], в работе был исследован вопрос переключательной полноты свойства планарности. Автором показано, что свойство планарности не является переключательно-полным.

Автор благодарит своего научного руководителя кандидата физико-математических наук, доцента Часовских Анатолия Александровича за постановку задачи и помощь в работе. Автор выражает глубокую благодарность заведующему кафедрой академику, профессору Кудрявцеву Валерию Борисовичу, доктору физико-математических наук, профессору Буевичу Вячеславу Александровичу, доктору физико-математических наук, профессору Гасанову Эльяру Эльдаровичу, доктору физико-математических наук, профессору Подколзину Александру Сергеевичу и всем сотрудникам кафедры Математической теории интеллектуальных систем за постоянное внимание и творческую атмосферу, способствующую работе.

1. Кудрявцев В. В.,Алешин С. В., Подколзин А. С. Введение в теорию автоматов. - М.: Изд-во Наука, 1985.

2. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р- И. Лекции по теории графов. М.: Изд-во Наука, 1990.

3. Яблонский С. В. Введение в дискретную математику. М.: Изд-во Наука, 1979.

4. А. А. Зыков. Основы теории графов. М.: Изд-во Наука, 1987.

5. А. А. Зыков. Гиперграфы. Успехи математических наук, 29:6 (180), стр. 89 154, 1974.

6. С. Berge. Graphs and Hypergraphs. North Holland Publishing Company, 1973.

7. Харари Ф. Теория графов. M.: Мир, 1973.

8. О. Оре. Теория графов. М.: Изд-во Наука, 1980.

9. A. Cayley. Brit. Assoc. Adv. Sci. Reports, p. 275, 1875.

10. Senior J. K. Partitions and their Representative Graphs. Amer. Jour. Math., vol.73, p. 663 689, 1951.

11. Hakimi S. L. On readability of a set of integers as degrees of the vertices of a linear graphs, I. J. Soc. Indust. Appl. Math. 1962. 10, N 3., p. 496 506.

12. Гавел В. Заметка о существовании конечных графов. Cas. Pest. Mat. 1955. 80, N 4., p. 477 481.

13. Ryser H. J. Combinatorial Properties of Matrices of Zeros and Ones. Canadian Journal of Mathematics, 9, p. 371 377, 1957.

14. Haber R. M. Term Rank of (0,1) Matrices. Rendiconti del Seminario Math-ematico della reale Universita di Padova, 30, p. 24 - 51, 1960.

15. R. В. Egglton, D. A. Holton. Graphic sequences. Lecture Notes in Mathematics, vol. 748, Springer, Berlin, p. 1-10, 1978.

16. А. А. Черняк. Переюночательно-полные свойства графов. Изв. АН БССР. Сер. физ.-мат. наук., N 1, стр. 29 35, 1985.

17. А. А. Черняк. Связность графов с предписанным степенным множеством и порядком. ДАН БССР, N 5, 29, 1984.

18. Syslo М. М. On tree and unicyclic realizations of degree sequences. Demon-stratio Mathematica, v.15, N4, 1982. Warsaw Technical University Institute of Mathematics.

19. Taylor R. Constrained switchings in graphs. Mathematics Research Report, N 27, 1980. Department of Mathematics, University of Melbourne.

20. Taylor R. Switchings Constrained to 2-Connectivity in Simple Graphs. SI AM J. Algebraic Discrete Methods, 3, N 1, p. 114 121, 1982.

21. Colbourn C. J. Research Report Cc-77-37, University of Waterloo, p. 200, 1977.

22. P. Басакер, Т. Саати. Конечные графы и сети. М.: Изд-во Наука, 1974.

23. Р. И. Тышкевич, А. А. Черняк, Ж. А. Черняк. Графы и степенные последовательности. I. Кибернетика, Киев, Наукова Думка, N 6, стр. 12 19, 1987.

24. A. Sinclair. Algorithms for Random Generation and Counting. A Markov Chain Approach. Birkhauser Boston, 1993.

25. D. L. Wang, D. J. Kleitman. On the existence of n-connected graphs with prescribed degrees. The journal of mathematics and physics, v.55, N1, 1976Работы автора по теме диссертации

26. Лашева М.И. Об алгебраических операциях на графах, сохраняющих степенную последовательность. Интеллектуальные системы, 2007, Т. 11, вып.1-4. стр. 551-592.

27. Лашева М.И. Об алгебраических операциях на графах, сохраняющих степенную последовательность. Вестник Московского Университета. Серия 1, Математика, Механика. Москва, 2009, N 5, стр. 48-50.

28. Лашева М.И. Об алгебраических операциях на графах, сохраняющих степенную последовательность. Материалы IX Международного семинара "Дискретная математика и ее приложения". Москва, 2007, стр. 331-334.

29. Lasheva M.I. On graph transformation algorithms keeping tha same degree sequence. Fifth World Conference on Intelligent System for Industrial Au-tomati on. Tashkent, Uzbekistan, 2008, pp. 455-456.

30. Лашева М.И. Об алгебраических операциях на графах, сохраняющих степенную последовательность. Материалы международной конференции "Современные проблемы математики, механики и их приложений". Москва, 2009, стр. 363-364.