Некоторые задачи перечисления помеченных связных графов

• Автор: Воблый, Виталий Антониевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 138 с.

ОГЛАВЛЕНИЕ.
ВВЕДЕНИЕ

ГЛАВА I. Графы с заданным числом точек сочленения

§ 1. Решение уравнения Селкова

§2. Комбинаторный вывод формулы для производящей функции

§3. Асимптотика для числа графов с большим количеством вершин

ГЛАВА II. Гомеоморфно несводимые графы

§1. Метод сжатия-разжатия

§2. Разреженные гомеоморфно несводимые графы

ГЛАВА III. Графы с заданным количеством висячих вершин

§ 1. Перечисление по числу вершин и ребер

§2. Асимптотика
§3. Графы-гусеницы
ГЛАВА IV. Асимптотика решения квадратичного разностного уравнения и ее применение.
§1. Связные разреженные графы и блоки
§2. 3-связные кубические графы
§3. Общее квадратичное разностное уравнение
ГЛАВА V. Регулярные графы.
§ 1. Кубические графы
§2. (2, к) - бирегулярные графы
§3. Максимальное число,остовов регулярных графов
ГЛАВА VI. Асимптотика числа карт.
§ 1. Общие кубические планарные карты
§2. g - существенные карты на поверхностях с малым родом
§3. Эйлеровы карты на проективной плоскости
§4. Условия хроматичности многочлена
ЛИТЕРАТУРА

ВВЕДЕНИЕ
Важным разделом теории графов является теория их перечисления, имеющая многочисленные приложения не только в математической кибернетике, но и в таких областях естествознания, как например, структурная химия и статистическая физика [30]. У истоков теории графов лежат работы А. Кэли по перечислению помеченных деревьев и связанных с ними химических структур, опубликованные в 1857-1889 гг. Однако только во второй половине двадцатого столетия бурный прогресс вычислительной техники и кибернетики обусловил интенсивное развитие всей дискретной математики и в том числе теории перечисления графов.
Комбинаторика тесно связана с теорией вероятностей. В настоящее время теория вероятностей далеко ушла от своих комбинаторных истоков, превратившись в могучую математическую реку со своим мощным аппаратом исследования. Однако «комбинаторные ключи» постоянно подпитывают эту реку. Во многих работах по теории случайных графов используются комбинаторные построения [22, 52,66].
Если на множестве исследуемых графов задано равномерное распределение вероятностей, то числовые характеристики этих графов можно рассматривать как случайные величины и анализировать их с помощью хорошо развитого аппарата теории вероятностей . Однако возможен и другой подход, когда, как в начале развития теории вероятностей , с помощью комбинаторики получаются утверждения для случайных графов. Во многих случаях из решения перечислительной задачи теории графов можно вывести следствия, характеризующие свойства и структуру соответствующих случайных графов.
Перечисление помеченных графов необходимо при непосредственном перечислении непомеченных графов с помощью леммы Бернсайда [26], а также используется для получения асимптотики непомеченных

графов [105]. Результаты перечисления помеченных графов применяются для их случайной генерации и анализа эффективности алгоритмов].
Хотя теория перечисления помеченных связных графов интенсивно развивается уже в течение 50 лет, интерес к этой области перечислительной комбинаторики не пропал, о чем говорят многочисленные работы зарубежных исследователей последних лет [58, 70, 82, 54, 59].
Помеченные графы используются в ряде физических задач [17-20] и поэтому перечисление таких графов является актуальной задачей.
Диссертация состоит из введения, шести глав и списка литературы. Ссылки в тексте за пределами главы содержат в качестве первого индекса номер главы, а второй индекс - номер утверждения или формулы. Ссылки внутри главы содержат только номер утверждения (формулы).
В первой главе исследуются помеченные связные графы с заданным числом вершин и точек сочленения [117, 119]. Обозначим через Зпт - число помеченных связных графов с П вершинами, из которых т точки сочленения, а через «5,„ (л) - соответствующую
Пусть £(Х 2) - У! Вт{г)хт , а В(2) - X! -®« —Г, где Вп -число 0 /1=2 И!
помеченных блоков с п вершинами.
Очевидно, З'оС2) = В (г) . Селков [88] и Йинг-Ли Джин [104] нашли,
экспоненциальную производящую функцию: Вт(г)

что ад = *(гП0-Д'(*)-1).
Селков [88] вывел следующее уравнение для В(х, г) ;

ГЛАВА II. ГОМЕОМОФНО НЕСВОДИМЫЕ ГРАФЫ §1. МЕТОД СЖАТИЯ-РАЗЖАТИЯ
1. Рассматривается несколько задач перечисления помеченных графов, которые могут быть решены с помощью единого подхода, предложенного Г.Н.Багаевым в ряде статей [1-4]. Идея метода проста и неявно встречается уже у Муна [60, 61]. Его суть состоит в следующем.
Для перечисления помеченных графов заданного вида в каждом графе выделяется порожденный подграф с определенными структурными свойствами, который сжимается в особую вершину. Образовавшиеся графы, содержащие фиксированную (особую) вершину с заданной степенью, а также сжатые подграфы независимо перечисляются известными методами перечисления. Перечисление исходных графов завершается суммированием по всем возможным степеням особой вершины произведений числа сжатых подграфов, числа графов, образовавшихся после сжатия, и числа способов восстановления (разжатия) исходного графа.
Рассмотрим на примерах перечисление графов методом сжатия-разжатия.
2. Напомним, что гладкий граф — это связный граф без висячих вершин. Назовем вершину графа внутренней, если она принадлежит гладкому графу, который получается из связного графа после многократного последовательного удаления висячих вершин вместе с инцидентными им ребрами до тех пор, пока такие вершины существуют. Очевидно, что любой связный граф, не являющийся деревом, состоит из гладкого графа и деревьев, корни которых являются вершинами гладкого графа. Пусть Ур~ число помеченных гладких графов с р вершинами, а Ср(п)— число помеченных связных графов с п вершинами, из которых р внутренние.