Орграф называется ориентированным деревом (ордеревом), если
1. существует единственный узел, полустепень захода которого равна 0 (корень),
2. полустепень захода остальных узлов равна 1,
3. все узлы достижимы из корня.
Пример.
• • • •
• • • • • • •
• • •
•
•
Рис. 37. Ордеревья с 4 узлами.
Остальные ордеревья с 4 узлами изоморфны гоафам на рис. 37.
Теорема. Свойства оррдеревьев.
1.Если q – число дуг, а p – число узлов оррдерева, то q = p -1.
2. Если в оррдереве отменить ориентацию ребер, то получится свободное дерево.
3. Для каждого узла существует единственный путь из корня.
4. В оррдереве нет контуров.
5. Если в свободном дереве любую вершину назначить корнем, то получится оррдерево.
Доказательство.
1. т.к. в каждый узел, кроме вершины, заходит единственная дуга (п. 1,2 определения), то q = p -1
2. Отмена ориентации в оррдереве приведет к созданию связного дерева (иначе нарушается п.3 определения). Из доказанного свойства 1 следует, что этот граф древовиден. Граф связен и древовиден, значит, он – дерево.
3. Если допустить в ордереве наличие контуров, то при отмене ориентации получится граф с циклами, т.е. не дерево, что противоречит свойству 2.
4. Если предположить наличие двух путей для некоторого узла, то при отмене ориентации получится граф с циклами, т.е. не дерево, что противоречит свойству 2.
5. Пусть вершина u назначена корнем. Инцидентные с ней ребра ориентируем в глубину. Т.к. для любой вершины v существует единственная цепь, соединяющая u и v, то полустепень захода d+(v) =1 
v, и каждый узел достижим из корня.
Упорядоченные деревья.
Если в качестве корня в ордереве выбрать какой-нибудь узел v, то множество узлов, достижимых из v образует орграф с корнем v (поддерево).
|
|
Если относительный порядок поддеревьев установлен, то ордерево называется упорядоченным.
Ордеревья и упорядоченные деревья часто используются в программировании. Например, для представления выражений, вложенных блоков, для представления иерархической структуры операторов, структуры вложенности каталогов и файлов, скобочные структуры и т.д.
Существует договоренность об изображении корня вверху дерева, направление дуг сверху вниз, что позволяет не рисовать стрелок, если это не приводит к путанице.
Если рассматривать деревья рис. 38 как упорядоченные деревья, то они все различные. Если рассматривать их как ордеревья, то 1 = П, но П ≠ Ш. Если рассматривать их как свободные деревья, то они все изоморфны. 
Бинарные деревья.
В информатике широко используются подмножества множества деревьев, в которых каждый узел является либо листом, либо образует два поддерева – левое и правое. Такой вид деревьев называется бинарным деревом. Бинарное дерево не является упорядоченным ордеревом.
Например, деревья а и b различны.
Рис. 38 Пример бинарного дерева.
Бинарное дерево называется полным уровня п, если каждый узел уровня п является листом, а каждый узел меньшего уровня имеет непустые левое и правое поддеревья.
Примером полного графа может служить таблица розыгрыша кубка по какому-нибудь виду спорта по олимпийской системе (плей офф).
Эйлеровы циклы.
Задача о Кёнигсбергских мостах.
По Кёнигсбергу протекает река Прегель, образующая два острова, связанных между собой и с берегами семью мостами. Надо разработать такой замкнутый маршрут, в котором каждый из мостов проходится один раз. Эта задача была решена Эйлером в 1736 г.
|
|
 |
Рис. 39. Задача о Кёнигсбергских мостах.
Задача сводится к построению циклического графа с 4 вершинами и 7 ребрами так, чтобы каждое ребро входило в него по одному разу.
Аналогична задача о рисовании конвертов, не отрывая карандаша и не рисуя дважды одну линию.
Рис.40. Закрытый и открытый конверты
Если граф имеет цепь (цикл), соединяющую две вершины и содержащую все ребра графа по одному разу, то цепь (цикл) называется эйлеровой, а сам граф называется эйлеровым.
Теорема. Для того чтобы граф быт эйлеровым, необходимо и достаточно, чтобы число вершин, степень которых нечетна, равнялось 0 или 2.
Доказательство:
Необходимость:
Пусть граф эйлеров, то есть существует или эйлерова цепь, или эйлеров цикл. И пусть имеется одна вершина с нечетной степенью, не являющаяся ни начальной, ни конечной, степень которой равна 2 п +1. Тогда 2 п +1 – е ребро приведет нас в эту вершину п +1-й раз, и покинуть её мы не сможем. Следовательно, такими вершинами могут быть только начальная и конечная. Их две в случае наличия цепи и 0 в случае цикла.
Достаточность:
 | |||
 | |||
А В
Рис. 41 Начальная и конечная точка цепи
Пусть имеется две вершины с нечетной степенью. Выйдя из вершины А, мы попадем в вершины, из которых всегда можно выйти. Таким образом, все ребра, инцидентные вершинам с четной степенью, будут пройдены, и мы придем к вершине В. Мы можем выйти, затем войти, но опять выйти уже не сможем. Таким образом, между А и В существует эйлерова цепь.
|
|
Докажем существование эйлерова цикла для вершины А:
Пусть эйлеров цикл существует для некоторых q 
ребер. Докажем, что он существует для q>q . Так как для любого q <q существует эйлеров цикл, а каждая вершина имеет четную степень, то существует вершина, принадлежащая обоим циклам (уже пройденному и еще нет, ребра которого не входят в 1 – ый цикл). Объединяя эти циклы, получим эйлеров цикл.
Рис. 42 Образование эййлеровоого цикла.
Таким образом, из теоремы Эйлера следует, что задача о Кёнигсбергских мостах и о рисовании закрытого конверта решений не имеют, т.к. вершин нечетной степени больше двух. Задача об открытом конверте решение имеет. Построение его следует начинать из вершины нечетной степени.
Гамильтоновы графы.
В средине 19 века ирландский математик Уильям Гамильтон опубликовал задачу о «кругосветном путешествии». Требуется обойти все вершины графа (столицы государств) по одному разу и вернуться в исходную вершину.
●
●
● ●
● ● ● ● ● ●
● ● ●
● ● ●
● ●
Рис. 43 Задача о «кругосветном путешествии».
Если граф имеет простой цикл, содержащий все вершины графа, то этот цикл называется гамильтоновым циклом, а сам граф называется гамильтоновым графом.
Гамильтонов цикл не обязательно содержит все ребра графа. Совершенно очевидно, что гамильтоновы графы являются связными.
Решение задачи о «кругосветном путешествии».
Находясь в любой вершине, мы можем повернуть вправо (П) или влево (Л). Условимся вместо ПП писать П 2 и т.д. Тогда решение может быть задано формулой
(Л3 П3 (ЛП)2)2 = ЛЛЛ ППП ЛП ЛП ЛЛЛ ППП ЛП ЛП.
Решение не единственно. Можно начинать в обратном порядке. Можно провести круговую перестановку.