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

Эйлеровы графы

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

Пусть W_p – число помеченных четных графов порядка p. Тогда справедлива следующая теорема:

Теорема. Число помеченных четных графов порядка p равно числу помеченных графов порядка p-1:

W_p= .

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

Чтобы доказать этот результат, мы сейчас установим взаимно однозначное соответствие между этими двумя графов. Рассмотрим произвольный граф порядка p-1. Граф G должен иметь четное число вершин нечетной степени. Добавим к нему вершину v, которой припишем пометку p. Наконец, из графа G и вершины v строим граф G′, имеющей нечетную степень. Этот граф G′ является помеченным четным графом порядка p. Легко видеть, что описанное соответствие является взаимно однозначным и что каждый помеченный четный граф порядка p может быть получен таким способом из некоторого помеченного графа порядка p-1.

Чтобы получить формулу для числа помеченных эйлеровых графов, мы будем использовать производящие функции. Итак, пусть W(t) – экспоненциальная производящая функция для помеченных четных графов, такая что

W(t) = t^p/p! (10)

Далее, пусть U_p – число помеченных эйлеровых графов порядка p, так что

U(t) = t^p/p! (11)

является соответствующей экспоненциальной производящей функцией.

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

U(t) =ln(W(t)+1) (12)

и

U_p= - U_k. (13)

Формула (12) следует из того факта, упомянутого после равенства (8), что если известна производящая функция для произвольного класса графов, то производящая функция для соответствующих связных графов получается с помощью формального логарифмирования первого ряда. Рекуррентное соотношение (13) для U_p является следствием формул (12) и (9).

Для нескольких первых членов ряда U(t) имеем равенство

U(t)=t+t³/3!+ 3t⁴/4!+ 38t⁵/5!+… (14)

Упражнение. Проверьте справедливость равенства (14).

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

Теорема [7]. Многочлен w_p(t), у которого коэффициент при t^q равен числу помеченных графов имеющих p вершин четной степени и q ребер, задается формулой

w_p(t)= . (15)

Для малых значений p находим, что (проверьте):

W₁(t)= w₂(t)=1 w₃(t)=1+t³ w₄(t)=1+4t³+ 3t⁴.