Составители:
Рубрика:
8 9
Замечание 1.3. Множество дуг в графе будем обозначать Р. Зада-
ние множества дуг в графе
FX ,Г
определяет отображение F и на-
оборот, поэтому граф Г можно также записывать в виде
РX ,Г
.
Определение 1.10. Ребром графа
РX ,Г
называется множествоо
из двух элементов
X
yx ,
, для которых или
Pyx ,
, или
Pxy ,
.
Замечание 1.4. В отличие от дуги для ребра ориентация роли
не играет. Множество ребер будем обозначать Р.
Определение 1.11. Путем в графе
FX ,Г
называется последо-
вательность дуг, или ребер
...,...,,,
21 k
pppp
, или вершин
1
,,...,,
21
i
xik
Fxxxx
такая, что конец каждой предыдущей дуги совпа-
дает с началом следующей.
Определение 1.12. Длина пути
k
pppp ...,,,
21
есть число
kpl
дуг последовательности; в случае бесконечного пути р полага-
ем
f pl
.
Определение 1.13. Под цепью будем понимать последовательность
ребер
...,...,,,
21 k
ppp
, в которой у каждого ребра
k
p
одна из граничных
вершин является также граничной для
1k
p
, а другая – граничной для
1k
p
.
Определение 1.14. Цикл – это конечная цепь, начинающаяся в не-
которой вершине и оканчивающаяся в той же вершине (см. рис. 1.1), т. е.
для последовательности
k
xxx ...,,,
21
выполняются условия
1
i
xi
Fxi
и
1
xF
k
x
.
Определение 1.15. Граф называется связным, если любые две его
вершины можно соединить цепью, т. е. это граф, множество узлов Х ко-
торого нельзя разбить на два множества
ZY
:
YFYy
y
,
ZFZz
z
.
Определение 1.16. Дерево, или древовидный граф – это конечный
связный граф без циклов, имеющий не менее двух вершин, т. е. для лю-
бого пути
k
xxx ...,,,
1
в графе выполняется
1
i
xi
Fx
для всех х
ki ,2
и
k
x
F
.
При построении многошаговой игры будем использовать в каче-
стве модели древовидные графы, поэтому приведем здесь некоторые из
их свойств.
Утверждение 1.3. Во всяком древовидном графе существует един-
ственная вершина
0
x
:
XF
x
0
ˆ
.
Определение 1.17. Вершина
Xx
0
называется корнем дереваа или
начальной вершиной графа Г, если она: 1) не имеет прообраза; 2)
X
x
:
k
k
x
Fx
1
0
, т. е.
0
x
принадлежит прообразу у k-й степени точки x.
Определение 1.18. Длина дерева – это длина наибольшего пути в
древовидном графе.
Определение 1.19. Прообраз
1
x
F
вершины
X
x
– это множе-е-
ство таких вершин y, что
x
принадлежит образу этих вершин, т. е.
^`
yx
FxyF
:
1
.
Пример 1.2. Так, из рис. 1.3 следует, что
^`
74
1
,
6
xxF
x
.
Утверждение 1.4. Для любой вершины x древовидного графа Г
существует
0
1
: xFxn
xn
, где
0
x
не зависит от т x, т. е. для любого x
существует обратное отображение, которое за n раз приведет в
0
x
.
Замечание 1.5. Для любого
X
x
прообраз
1
x
F
либо содержит
единственный элемент, либо является
. Это условие исключает нали-
чие циклов.
Замечание 1.6. В древовидном графе каждая вершина имеет един-
ственный прообраз, кроме
0
x
, которая не имеет прообраза.
Замечание 1.7. В случае, если граф является конечным, обязатель-
но существует вершина x:
x
F
(см. рис. 1.1).
На рис. 1.2 изображен древовидный граф с началом
0
x
. Точками
X
x
отмечены вершины графа. Дуги графа изображены отрезками со
стрелкой, определяющей начало и конец дуги.
Пример 1.3. С помощью древовидного графа можно изобразить
игру в шашки или шахматы, если под вершиной графа понимать распо-
ложение фигур на доске в данный момент, указание хода и все последо-
вательные расположения фигур на предыдущих ходах. Тогда
существует
единственная цепь, ведущая из начальной вершины в любую заданную,
поэтому соответствующий граф игры не содержит циклов и является
деревом.
Пусть
X
z
.
Определение 1.20. Подграфом
z
Г
древовидного графа
FX ,Г
называется граф вида
z
z
FX ,
, где
z
z
FX
ˆ
,a
zxz
XFxF
.
На рис. 1.2 линией обведен подграф, берущий начало из вершины z.
В древовидном графе для всех
z
Xx
множество
x
F
и множество о
xF
z
совпадают, т. е. отображение
z
F
является сужением отображения F
на множество
z
X
, поэтому для подграфов древовидного графа будем ис-
пользовать обозначение
FX
z
z
,Г
.
Страницы
- « первая
- ‹ предыдущая
- …
- 3
- 4
- 5
- 6
- 7
- …
- следующая ›
- последняя »
