Теорема 3. Хроматическая функция f (q) конечного графа  с n вершинами является многочленом степени не более, чем n.

Доказательство.По индукции по числу реберm. Приm=0 получаемf_ (q)=qⁿ . Пусть граф имеетm+1ребер (иnвершин). Выбросим произвольное ребро . Получится граф’, хроматическая функция которого – многочлен степениnсогласно предположению индукции. Чтобы получить число раскрасок исходного графа, нужно из этого числа вычесть число раскрасок, при которых концы удаленного ребра окрашены в одинаковый цвет. Это число раскрасок будет хроматической функцией графа’’, полученного удалением ребра и отождествлением концов этого ребра. Отсюда разность

f_(q)= f_’(q) – f_{ ’’} (q)– это разность многочленов степени не более, чем n.

4.4. Деревья

Определение 1. Дерево, имеющееnвершин, называетсянумерованным, если каждой из его вершин присвоен индивидуальный номерk{1, 2,,n}.

Теорема 1.(Кэли) Число нумерованных деревьев сnвершинами равноn^n-2.

Доказательство. Сопоставим каждому нумерованному дереву последовательностьn-2чисел принадлежащих{1, 2, ,n}. Эта последовательность называется кодом Прюфера и строится следующим образом. В цикле находится висячая вершина с наименьшим номером. Номер вершины смежной с найденной записывается в последовательность. Цикл повторяетсяn2раза. Наоборот, по последовательностиnчисел из{1, 2, ,n+2}можно построить нумерованное дерево с помощью следующих действий:

Выписываем множество B={1, 2, 3, ∙ ∙ ∙, n+2}. Устанавливаем начальное множество ребер дереваT= . Далее выполняются действия:

for (i=1; i<n1; i++)

{

b= min { kB: ka_j  j ≥ i};

добавить к Tребро{b,a_i} ;

B = B \ {b} ;

}

Число последовательностей из n-2чисел принадлежащих множеству{1, 2, ∙ ∙ ∙, n}равноnn-2, значит число нумерованных деревьев равноnn-2.

Доказательство следующего утверждения можно найти в [3].

Пусть Г – граф. Егоподдеревом T называется подграф, который является деревом. В этом случае мы будем говорить так же, чтоTсодержитсяв графеГ. ПоддеревоTграфаГназываетсямаксимальным, если оно не содержится ни в каком отличном от него поддеревеT’графаГ.

Теорема 2.Число максимальных поддеревьев связного графа равно абсолютной величине алгебраического дополнения произвольного элемента матрицы

,

где d_i– степени вершин графа,A() =( a_{i j} )– матрица смежности

Пример 1. Рассмотрим граф , изображенный на рис. 4.5. Вычислим количество его максимальных поддеревьев.

Рис. 4.5. Простой граф

Найдем матрицу M().

.

Отсюда число максимальных поддеревьев равно |A₃₁| = 3.

4.5. Числа Каталана

Рассмотрим задачу перечисления бинарных деревьев. Введем определения.

Определение 1. Дерево с выделенной вершиной называетсякорневым, а выделенная вершина – его корнем (рис. 4.6). Для каждой вершиныqсуществует единственный элементарный путь, соединяющий ее с корнем. Длина этого пути называетсявысотойвершиныq. Смежные сqвершины, высота которых больше высоты вершиныqна 1, называютсядетьмивершиныq. На рис. 4.6 показано дерево с корнем 3.

Определение 2. Корневое дерево, каждая вершина которого имеет не более двух детей, называетсябинарным, если детям приписан дополнительный признак «левой» или «правой» смежной вершины. Вершина не может иметь две левые или две правые смежные вершины. Бинарное дерево вместе с функцией, сопоставляющей каждой вершине некоторое число, называетсябинарным деревом чисел.

Рис. 4.6. Корневое дерево

Бинарное дерево чисел можно определить по индукции:

1. Пустое дерево является бинарным деревом чисел.

2. Если T₁иT₂– бинарные деревья чисел, то (T₁, число,T₂) – бинарное дерево чисел.

Определим отношение эквивалентности на множестве бинарных деревьев чисел S~Tследующим образом.

1. Если S=T=, тоS~T.

2. Если S=(S₁, m, S₂), T=(T₁, n, T₂) , S₁~ T₁ и S₂~ T₂ , то S~T.

Число классов эквивалентности бинарных деревьев имеющих nвершин называетсяn-м числом Каталана и обозначается черезc_n.

На рис. 4.7 показаны классы эквивалентности бинарных деревьев, имеющих nвершин, приn=0, 1, 2, 3:

Рис. 4.7. Бинарные деревья

Пример 1. Число расстановок скобок. Пусть ‘*’  бинарная операция на множестве A, которая не предполагается ни коммутативной, ни ассоциативной. Введем определение для алгебраических выражений, составленных с помощью этой операции, скобок и букв. Такие выражения определим с помощью индукции и будем называть их термами: