ВУЗ:
Составители:
Рубрика:
-наоборот, то такие дуги называются не строго параллельными.
Определение.
Дуга e
1
смежна с дугой e
2
, если конечная вершина
e
1
совпадает с начальной вершиной e
2
.
Определение.
Число дуг, положительно инцидентных вершине
v, называется положительной степенью вершины v и обозначается
через
δ
+
(v), а отрицательно инцидентных вершине v называется
отрицательной степенью вершины v и обозначается через
δ
--
(v).
Учитывая, что каждая дуга положительно инцидентна одной
вершине и отрицательно инцидентна также одной вершине, полу-
чаем (в случае петли одной и той же)
() () ,
vV vV
vv
δδ
+−
∈∈
==
∑∑
E
где ⎢E ⎢ - число дуг графа.
Если
δ
(v)=
δ
+
(v)+
δ
−
(v) - степень вершины, то для орграфа
также справедлива
Теорема.
В орграфе число вершин нечетной степени четно.
Определение.
Вершина v называется изолированной, если
δ
(v)=0.
Определение. Орграф называется пустым, если все его верши-
ны являются изолированными.
Определение.
Рассмотрим граф G=<V,E>. Граф G
1
=<V
1
,E
1
>
называется подграфом G тогда и только тогда, когда
1.V
1
⊆
V, E
1
⊆
E.
2. Если дуга e
∈
E
1
положительно инцидентна вершине v
∈
V
1
и
отрицательно инцидентна вершине u
∈
V
1
, то и дуга e
∈
E также по-
ложительно инцидентна вершине v
∈
V и отрицательно инцидентна
вершине u
∈
V.
Ориентированные маршруты, пути, контуры
Определение. Ориентированным маршрутом (ормаршрутом)
длины n называется последовательность (не обязательно различ-
ная) дуг e
1
,…, e
n
таких, что для соответствующей последователь-
ности n+1 вершин v
0
,v
1
,…,v
n
выполняется условие
1
,,1,
iii
evvi
−
=< > = n
, т.е. вершины v
i-1
и v
i
являются соответст-
венно начальной и конечной вершинами дуги e
i
. Ормаршрут замк-
нут, если v
0
=v
n
(циклический ормаршрут).
Определение.
Ормаршрут, в котором нет повторяющихся дуг,
называется путем
и простым путем, если все его вершины различ-
31
Страницы
- « первая
- ‹ предыдущая
- …
- 29
- 30
- 31
- 32
- 33
- …
- следующая ›
- последняя »
