ВУЗ:
Составители:
61
Рис. 5.7. Граф и его части:
а – граф; б – часть графа; в – подграф; г - суграф
Исходный граф по отношению к его подграфу называют надграфом, а
по отношению к суграфу – сверхграфом. Совокупность всех ребер графа, не
принадлежащих его подграфу (вместе с инцидентными вершинами) образует
дополнение подграфа. Говорят, что
подграфы G′ = (V′, E′) и G′′ = (V′′, E′′) разде-
лены ребрами, если они не имеют общих ребер (Е′ E′′ = ) и разделены вер-
шинами, если у них нет общих вершин (V′ V′′ = ).
Две вершины графа называют связанными, если существует маршрут,
соединяющий эти
вершины. Граф, любая пара вершин которого связана, назы-
вают связным графом. Связность ориентированных графов определяется так же,
как и для неориентированных (без учета направления дуг). Специфичным для
орграфа (или смешанного графа) является понятие сильной связности. Орграф
называют сильно связным, если для любой пары вершин v
i
и v
j
существует путь
из v
i
в v
j
и из v
j
в v
i
. Например, граф, показанный на рис. 5.2, а, – сильно связ-
ный.
Связный граф может быть разделен на несвязные подграфы удалением
из него из него некоторых вершин и ребер (при удалении вершин исключаются
и все инцидентные им ребра, а при удалении ребер вершины сохраняются). Ес-
ли существует такая вершина, удаление которой превращает связный
граф (или
компоненту несвязного графа) в несвязный, то она называется точкой сочлене-
ния (рис. 5.8, а). Ребро с такими же свойствами называется мостом (рис. 5.8, б).
При наличии моста в графе имеется, по крайней мере, две точки сочленения.
Граф называется неразделимым, если он связный и не имеет точек со-
членения (например, граф на
рис. 5.7, а неразделим). Граф, имеющий хотя бы
одну точку сочленения, является разделимым и называется сепарабельным. Он
разбивается на блоки, каждый из которых представляет собой максимальный
неразделимый подграф (на рис. 5.8, в показаны блоки В
1
, В
2
, В
3
графа на рис.
5.8, б).
V
1
V
4
V
1
V
3
V
4
V
1
V
4
V
4
V
3
V
2
V
2
V
2
V
2
V
1
а б в г
Страницы
- « первая
- ‹ предыдущая
- …
- 59
- 60
- 61
- 62
- 63
- …
- следующая ›
- последняя »
