ВУЗ:
Составители:
Рубрика:
ны.
Определение.
Замкнутый путь называется контуром. Замкну-
тый простой путь называется простым контуром.
Сильная связность
Определение. Орграф называется сильно связным, если для ка-
ждой пары различных вершин u и v существует путь из u в v и из v
в u.
Определение.
Орграф называется сильно k - связным, если для
каждой пары различных вершин u и v существует по крайней мере
k путей из u в v, и из v в u, которые не имеют общих вершин (а
следовательно и дуг) за исключением конечно u и v.
Деревья
Определение. Орграф является ориентированным деревом, рас-
тущим из корня v
0
, если
1) он образует дерево в неориентированном смысле;
2) единственная цепь между v
0
и любой другой вершиной v яв-
ляется путем из v
0
в v.
Метрические характеристики графа
Пусть G=(V,E) – связный граф, а u и v – две его несовпадаю-
щие вершины. Обозначим через d(u,v) длину кратчайшей простой
цепи между u и v, и положим d(u,u)=0. Введенное таким образом
расстояние удовлетворяет аксиомам метрики:
1) d(u,v)
≥
0,
2) d(u,v)=0 тогда и только тогда, когда u=v,
3) d(u,v)=d(v,u),
4) d(u,v)+d(v,w)
≥
d(u,w).
Определение. Эксцентриситетом фиксированной вершины и
называется величина
),(max)( vudul
Vv∈
=
.
Определение.
Диаметром графа G=(V,E) называется величина
.
)(max)( ulGd
Vu∈
=
Определение
. Вершина v называется периферийной, если
l(v)=d(G).
Определение
. Радиусом графа G=(V,E) называется величина
.
)(min)( ulGr
Vu∈
=
Определение.
Вершина v называется центральной, если
32
Страницы
- « первая
- ‹ предыдущая
- …
- 30
- 31
- 32
- 33
- 34
- …
- следующая ›
- последняя »
