• Для всякого элемента aa слово a есть терм;

• если t₁иt₂– термы, то (t₁* t₂) – терм.

В нормальной форме Бэкуса-Наура определение будет следующим:

Терм ::= a | (Терм*Терм)

Здесь aA– произвольный элемент. Например, термами являются слова:(a*a)*b, a*(b*c), и т.д. Число термов, содержащихnопераций *, равноc_n .

Изображенным на рисунке бинарным деревьям соответствуют термы:

1. a ,

2. (a*b) ,

3. ((a*b)*c), (a*(b*c)),

4. (a*((b*c)*d)), (a*(b*(c*d))), ((a*b)*(c*d)), (((a*b)*c)*d), ((a*(b*c))*d) .

Пример 2.Деревом поисканазывается бинарное дерево, вершинам которого соответствуют элементы некоторого линейно упорядоченного множества. Причем для каждой вершины значение в ней не меньше значений в вершинах левого поддерева и больше значений в вершинах правого поддерева. Элементы возрастающей последовательностиnчисел можно расположить в узлах дерева поиска . Оно будет бинарным деревом и может быть выбраноc_nспособами.

Теорема 1. Числа Каталана равны .

Доказательство.Имеют место соотношения для чисел классов бинарных деревьев:

c_k = c₀c_k-1 + c₁c_k-2 + ∙ ∙ ∙ +c_k-1c₀ , для всехk>0.

Пусть C(x) = производящая функция последовательности чисел Каталана.

Получаем C(x) = xC²(x)+1, откуда.

4.6. Плоские графы Эйлерова характеристика. Двумерной клеткой мы будем называть часть поверхности, ограниченную некоторым криволинейным многоугольником.

Теорема 1. Пусть   граф, разбивающий замкнутую поверхность S на двумерные клетки. Пусть p  число вершин графа, q – число ребер, r – число клеток. Тогда число p – q + r не зависит от разбивающего графа и называется эйлеровой характеристикой поверхности.

Теорема 2. Пусть   связный граф, разбивающий сферу на двумерные клетки. Тогда p – q + r = 2.

Доказательство.С помощью индукции поq. Еслиq=0, тоp=1иr=1. Пусть теорема верна для графа сqребрами. Докажем ее дляq+1ребер. Рассмотрим два случая добавления ребра (рис. 4.8). В первом случае добавляется ребро, вершины не добавляются. Во втором добавляется ребро и вершина. Если обозначить новые числа вершин, ребер и граней черезp’,q’,r’, то в первом случае получим

p’–q’+r’=p – (q+1)+(r+1) = p–q+r =2,

во втором ─ p’–q’+r’ = (p+1) – (q+1)+r = p–q+r =2.

Рис. 4.8. К доказательству теоремы 2

Графы Куратовского. Далее мы рассмотрим следующие две задачи.

Первая задачапринадлежит Мебиусу. Речь идет о короле, завещавшем своим пяти сыновьям разделить между собой его владения так, чтобы каждая из частей имела общие границы с каждой из остальных частей.

Рассматривая граф, вершины которого соответствуют пяти частям, а ребра – общим границам, приходим к вопросу, является ли он плоским?

Вторая задача– задача о трех домах и трех колодцах. На поверхности сферы заданы 3 точки, называющиеся домами, и 3 точки, называющиеся колодцами. Нужно соединить не пересекающимися кривыми (играющими роль тропинок) каждый дом со всеми колодцами.

Докажем неразрешимость этих двух задач.

Лемма 1. Для связного плоского графа с p>3 вершинами и q ребрами справедливо неравенство q  3p-6. Если существует вложение в сферу, при котором каждая грань имеет не менее 4 ребер, то справедливо неравенство q  2p – 4.

Доказательство.Рассмотрим множество пар (ребро, грань), где ребро содержится в грани. Число таких пар равно2q , ибо каждое ребро принадлежит двум граням. С другой стороны, оно не меньше3r, ибо грань содержит не меньше трех ребер. Отсюда

2q ≥ 3r. Если грань содержит не меньше четырех ребер, то получаем2q ≥ 4r. Подставляя в эти неравенстваr = 2 – p +q, получим доказываемые неравенства.