Определение 1 (см.[4 с. 118]) Цикломатическим числом связного графа называется увеличенная на единицу разность между числом ребер графа и числом его вершин.
Определение 2 —Циклический граф это граф с цикломатическим числом, равным
Определение 3 (см.[7]) Граф называется последовательно—параллельным, если он не содержит подразбиения полного графа .
Последовательно—параллельные графы применяются при поcтроении надежных коммуникационных сетей (см. [9]).
В [3] получена явная формула для числа помеченных последовательно—параллельных —связных графов с заданным числом вершин. В данной заметке из этой формулы выведены два комбинаторных тождества, a также приведено не зависящее от перечисления графов доказательство полученных тождеств.
Теорема 1. Верны следующие комбинаторные тождества:
, (1)
(2)
Доказательство. В [3] для числа помеченных последовательно—параллельных —циклических —связных графов с вершинами при получено выражение
(3)
Так как полный граф является трициклическим, то все унициклические и бициклические —связные графы не содержат в качестве подграфа подразбиения и потому являются последовательно—параллельными графами.
Унициклический —связный граф это простой цикл с помеченными вершинами. Число таких циклов известно (см. [8, с. 20]); следовательно, , и при из (3) получим
(4)
Э. Райт доказал (см. [10]), что число помеченных бициклических блоков с вершинами равно ; при из (3) получим
(5)
Преобразуем тождества (4) и (5). Заменим на ; поскольку
тождество (4) эквивалентно тождеству (1), а тождество (5) эквивалентно тождеству (2).
Дадим теперь не зависящее от перечисления графов доказательство тождеств (1) и (2).
Обозначим левую часть тождества (1) через . Поскольку при , то нижний индекс во внутренней сумме можно заменить на . С помощью метода коэффициентов (см. [5, с. 8]) имеем
В силу комбинаторного тождества
, (6)
(см. [6, с. 625]) имеем
Введем обозначение
Функция аналитична в нуле, и по формуле для вычета в полюсе первого порядка имеем
Используем теперь комбинаторное тождество
, (7)
(см. [8, с. 619]). Так как в под знаком суммы второй биномиальный коэффициент равен нулю при , то окончательно получим
Для тождества (2) опять с помощью метода коэффициентов имеем
В силу комбинаторного тождества (6) найдем
Введем обозначение
Функция аналитична в нуле, и по формуле для вычета в полюсе второго порядка найдем
Еще раз применим комбинаторное тождество (7):
Так как , в силу тождества (7) имеем
Окончательно получим
Отметим, что для чисел помеченных последовательно—параллельных трициклических и тетрациклических блоков известны выражения в виде многочленов от числа вершин графа (см. [1] и [2], соответственно). Поэтому из формулы (3) при и можно получить еще два тождества типа (1). Однако степень многочленов от в правой части тождеств быстро растет; при она равна .
Автор благодарит профессора В. К. Леонтьева за обсуждение работы.