Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Связные графы.

Читайте также:
  1. Автографы.

Пусть G – граф и v0, v1, v2,…, vn – последовательность вершин графа G, такая, что вершина vi смежна с вершиной vi+1 при i = 0, 1, …,n-1. Такая последовательность вместе с n ребрами { vi, vi+1}, 0≤i≤n-1, называется маршрутом длины n. Если ребра в маршруте различные, то он называется цепью. Если в маршруте различны все вершины (а следовательно, и ребра), то называется простой цепью. Связным графом называется граф, в котором любые две различные вершины простой цепью.

Число помеченных связных графов порядка 4 может быть вычислено тривиальным образом и равно 38.(Проверьте!).

Подграф H графа G имеет V(H)ÍV(G) и X(H)ÍX(G). Компонента графа представляет собой максимальный связный подграф. Граф с корнемкорневой граф) имеет одну выделенную вершину, называемую корнем. Два корневых графа называют изоморфными, если существует взаимно однозначная функция, отображающая множество вершин одного графа на множество вершин другого графа, которая сохраняет не только смежность вершин, но и корни [6]. Аналогичное требование накладывается и при описании корневых помеченных графов. Это понятие можно сейчас использовать для получения следующей рекурсивной формулы. Пусть Сp – число связанных помеченных графов порядка р.

Теорема. Число Сp связанных помеченных графов удовлетворяет соотношению

Сp= - Ck. (5)

Доказательство.

Заметим, что если в помеченном графе делать корнями разные вершины, то получатся разные корневые помеченные графы. Следовательно, число корневых помеченных графов, в которых порядка p равно pGp. число корневых помеченных графов, в которых корень находится в компоненте, содержащей в точности k вершит равно kCk .

Суммируя эти произведения по k от 1 до p, мы опять получаем выражение для корневых помеченных графов, а именно

СkGp-k.

 

Для дальнейших построений нам потребуется важное свойство экспоненциальных производящих функций для графов:

Для всякого к =1,2,3…обозначим через аk число способов, которым можно пометить все графы порядка k, обладающие некоторым свойством P(a), пусть a(t)= экспоненциальная производящая последовательности аk. Предположим также, что b(t)= другая экспоненциальная производящая функция для класса графов, удовлетворяющих свойству P(b).

Следующая лемма дает полезную интерпретацию коэффициентов произведения а(t)∙b(t) этих двух производящих функций.

Лемма пересчета помеченных графов. Коэффициент при tk/k! в а(t)∙b(t) равен числу упорядоченных пар (G1,G2) двух непересекающихся графов, где G1 обладает свойством P(a), где G2 обладает свойством P(b), k – Число вершин в G1ÈG2 и пометки от 1 до k распределены на графе G1ÈG2.

Для иллюстрации этой леммы положим, что С(t) – экспоненциальная производящая функция для помеченных связных графов: C(t)=

Тогда С(t)∙С(t) является производящей функцией для упорядоченных пар связных графов. Разделив этот ряд на 2, получаем производящую функцию для помеченных графов, имеющих в точности две компоненты. Аналогично, Сn(t)/n! имеет при tk/k коэффициент, равный числу помеченных графов порядка k, содержащих в точности n компонент. Если через G(t) обозначим экспоненциальную производящую функцию для помеченных графов, то

G(t)= . (6)

Таким образом, мы имеем следующее экспоненциальное соотношение между

G(t) и С(t), найденное Риделлом (1951).

Теорема. Экспоненциальные производящие функции G(t) и С(t) для помеченных графов и для помеченных связных графов удовлетворяют соотношению

1+ G(t)=eС(t). (7)

Замечание. 1. Это равенство остается справедливым и для мультиграфов.

 

Риордан получил следующее рекуррентное соотношение для Ср:

Сp= (2k-1)CkCp-k. (8)

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

Поэтому мы можем сформулировать следующий общий результат.

Следствие. Если =exp(), то для m≥1

am=Am akAm-k. (9)

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

2.найти перечислительную формулу для помеченных (p,q)-графов, не имеющих изолированных вершин.




Дата добавления: 2015-09-11; просмотров: 21 | Поможем написать вашу работу | Нарушение авторских прав

Конкретная математика | Производящие функции для сочетаний. | Производящие функции для перестановок. | Решение линейных рекуррентных уравнений. | Числа Стирлинга первого и второго рода. | Представление перестановок в циклической форме. | Цикловые классы (типы). | Перестановки без единичных циклов | Композиции чисел. | Принцип включения и исключения. |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав