Файл: Вершинами графа, элементы множества e называются ребрами графа а пара (V, e ), т е. множество вершин и ребер графа называется графом. Если две вершины графа соединены ребром, то такие вершины называются смежными.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.11.2023
Просмотров: 83
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
, Порожденное данным корневым деревом T, тогда вершина uназывается родителем вершины v , а v называется сыном вершины u , если существует ориентированное ребро
из u в v. Если u – родитель v и
, тогда v и называются братьями . Если существует ориентированный путь из вершины u в вершину v , тогда u называется предкомвершины v , а v называется потомком вершины u .
Если наибольшая из степеней выхода для вершины дерева равна m, то дерево называется
m- арным деревом . При m=2 – бинарное дерево . Определяется левый и правый сын в каждом бинарном дереве .
Определение. Пусть G=G (V , E ) – ориентированный граф . Ориентированным циклом
называется ориентированный путь ненулевой длины из вершины в ту же вершину без повторения ребер .
Определение. Пусть G=G (V , E ) – ориентированный граф. Ориентированный цикл , который включает все ребра и вершины графа G , называется эйлеровым циклом .
В этом случае говорят , что ориентированный граф G имеет эйлеров цикл .
Теорема . Ориентированный граф имеет эйлеров цикл тогда и только тогда , когда он связный и степень входа каждой вершины равна ее степени выхода .
.bGимеет эйлеров цикл . 
не имеет эйлерова цикла .a
. . c
. . 
. d . 
-
Среди приведенных ниже графов найдите те ,которые имеют эйлеров цикл .
-
. b 2) c
a
. . c . d . e b df
g h a f eI
j g jI
3
)a 4) a
F b d e
e j g b cI h
d
c5
) b 6) a
a c b c d e
d f f g
e h i j ku
7
) b c 8) ba
d e a cf
gdef
2.Среди приведенных ниже графов найдите те , которые имеют собственный эйлеров цикл .
1
) •с 2) •c
а• •в •d •fa• •b •d •e•e•f
-
•
k 4) •a
g• •h •I •j b• •d •e
•f •d •c
•b•a •c
5
) •g 6) •c
d• •e •j a• •b •da• •b •c e• •f
3.Какие из следующих ориентированных графов имеют эйлеровы циклы
1
