ВУЗ:
Составители:
Рубрика:
30
ребро.
Доказательство.
Удаление одного произвольного ребра разби-
вает дерево на два компонента, т.е. превращает его в лес из двух
деревьев. Удаление второго ребра превращает дерево в лес из 3-х
деревьев, и т.д. Удаление n-1 ребра превращает дерево в лес из n
деревьев, каждое из которых является изолированной вершиной.
Лекция 8. Ориентированные графы: основные понятия;
ориентированные маршруты, пути, контуры;
сильная связность; деревья. Метрические харак-
теристики графа.
Основные понятия
Во многих случаях ребрам графа необходимо задать ориента-
цию или направление. Из этого следует единственное структурное
различие между неориентированными и ориентированными гра-
фами, заключающиеся в том, что в первом случае граничные точки
ребра образуют неупорядоченную, а во втором - упорядоченную
пару вершин.
Определение
. Ориентированным графом (или орграфом) назы-
вается пара G=<V,E>, где V - непустое множество, а E
⊆
V
2
=V
×
V.
Элементы множества V называются вершинами графа, а эле-
менты множества E - дугами.
Определение.
Если дуга e=<u,v>
∈
E, то говорят, что вершина u
смежна с v, а дуга e отрицательно инцидентна вершине v и поло-
жительно инцидентна вершине u.
Определение изоморфизма ориентированных графов идентично
определению изоморфизма неориентированных графов.
Определение.
Если дуга e=<u,v> отрицательно инцидентна
вершине v и положительно инцидентна вершине u, то u и v назы-
ваются начальной и конечной вершинами дуги e соответственно.
Определение.
Если u и v начальная и конечная вершины дуги
e=<u,v> и u=v, то e называется петлей (в этом случае u смежна
сама с собой).
Определение.
Если e
1
= <u,v> и e
2
=<u,v>, т.е. u и v являются
начальной и конечной вершинами дуг e
1
и e
2
, то e
1
и e
2
называются
строго параллельными.
Определение.
Если e
1
= <u,v>, а e
2
=<v,u>, т.е. вершина u явля-
ется начальной вершиной дуги e
1
и конечной вершиной дуги e
2
, а v
Страницы
- « первая
- ‹ предыдущая
- …
- 28
- 29
- 30
- 31
- 32
- …
- следующая ›
- последняя »
