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

• Автор: Лашева, Мария Игоревна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 93 с.

Содержание
Введение
Глава 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] как различных возможных структурных моделей данной органической молекулы, восстанавливаемых по ее формуле. Он описывает способ восстановления мультиграфа по степенной последовательности и использует операцию «б-элементарного преобразования» ребер для дальнейшего преобразования этого мультиграфа

Свойство 4. G2 может иметь кратные дуги (кратности не выше 2), причем если ei, е2 - кратные дуги Gu, то е4 £ Е, е2 Е Е2 или е Е Е2, е2 Е Е4.
Рассмотрим некоторое подмножество A(d'(n)) множества
ориентированных мультиграфов M{d'{n)) с занумерованными вершинами, обладающих степенной последовательностью, равной удвоенной степенной последовательности d'(n), и удовлетворяющих свойствам 3 и 4. Определим операцию
ш(А{<И(п))) = {G[21 3 Gn = {Vn,En) Е M(d(n)), 3 v1,v2,v3,v4 E V12, (vhv2), (v3,v4) E Eh (vuv4), (v3,v2) i- El (или (vhv2), (V3,v4) E E'2, (vi,v4), (v3,v2) i E'2),
G'12 = (V12, {El U { (vu v4), (v3l v2)) }) { (vi, v2), (v3, vA) })
(или G'12 = (V12, {E'2 U{ (vi,v4), {V3,v2) }) { (vi,v2), (v3, v4) }))}.
Будем говорить, что операция и> эффективно применима в ориентированном мультиграфе G2 к некоторой паре дуг (гд, гд) €
Ei,(vj1}Vj2) € Ei (или {vh,vк) Е Е2, {vjuvj2) Е Е2), если в G42 не существует дуг (vi^VjJ Е Е1, (гддд) Е El {(vh,vh) Е Е'2, (гд, щ2) Е Е2), и при удалении ДУГ К>и*2) G Eu{vh,vh) Е Ei ((vh,vh) Е E^{vh,vj2) Е Е'2) и добавлении дуг (u^ufc Е Еь(-уд,'ц2} Е Ei ((vh,vj2) Е Е'2, (пд,щ2) Е Е'2) в полученном ориентированном мультиграфе G'12 количество кратных дуг увеличивается.
Докажем следующие леммы.
Лемма 1.6. Если существуют не кратные дуги (нд,ид) Е Е1; (уд,гд) £ гд) Е -Е^, mo в ориентированном мулътиграфе Gi2 = (Vi2,Ei2) существуют две дуги, к которым эффективно применима операция и.
Доказательств о.
Шаг 1. По свойству 3 ориентированного мультиграфа G2 существует не кратная дуга (уд,гд) Е Е.
Если не существует дуги (гд, нд) £ Д, то к дугам (пд,уд), (vk,vj3) эффективно применима операция со. Получаем пару кратных дуг (vj2,Vj3). Остановка.
Если существует дуга {vk,vh) Е то к дугам (г>д,нд) Е E'2,{vh,vh) эффективно применима операция со. Получаем две пары кратных дуг (уд,Уд) и (нд, уд). Остановка.