Дискретная математика

152 ветви. Уровень вершины ордерева - это расстояние от корня до выбранной вершины (если считаем, что все дуги имеют единичную. длину). Корень имеет уровень 0. Вершины одного уровня о^'разуют ярус дерева. Для деревьев применяется ещё и «генеалогическая» терминология. Вершина v, достижимая из вершины и, называется потомком вершины и\ вершина и называется предком для v. Если м и v - смежные вершины, то и называют отцом (родителем) для v, а v - сыном {дитём) для и. Ясно, что лист не имеет потомков. Как правило, при изображении дерева и ордерева корень располагают наверху и его ветви идут вниз, что естественно при использовании генеалогической интерпретации. Поэтому иногда при изображении ордерева не указывается ориентация ребер, ибо она всегда направлена от корня. Ориентированное дерево называют бинарным, если полустепень исхода любой его вершины не больше двух. Бинарное ориентированное дерево называют полным, если из любой его вершины, не являющейся листом, исходят ровно две дуги, а ярусы (уровни) всех листьев совпадают. Можно доказать, что в полном ориентированном дереве высоты h имеется ровно 2'' листьев. Всякое (свободное) дерево молено ориентировать, назначив одну из вершин (любую вершину) корнем. Где начало того конца, которым оканчивается начало? К. Прутков § 14. Эйлеровы графы Рассмотрим упоминавшуюся в начале этой главы задачу о кенигсбергских мостах. В Кёнигсберге (ныне Калининград) было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом, как показано на рис. 5.1. Каждый мост имел свои названия; Лавочный, Зелёный, Пороховой, Кузнечный, Деревянный, Высокий и Медовый. Нужно выяснить, существует В ли маршрут прогулки, проходящий через каждый Рис 5 25 ^ только один раз, и такой, что позволял бы, выйдя из произвольной точки города, вновь вернуться в эту же точку, Части города, лежащие на северной и южной сторонах реки, обозначим соответственно через А и В. Западный остров обозначим через С, а восточный - через D. Так как нас интересуют только переходы по мостам, можно считать А, В, С и D вершинами некоторого графа, ребра которого отвечают соответствующим мостам. Б результате получим граф, диаграмма