ВУЗ:
Составители:
58
1
78
w
P ={8,6,5,10,13,12},
2
78
w
P ={8,11,14,13,12};
множеств дуг, обозначаемых парами вершин
1
78
P ={(7,6),(6,5),(5,4),(4,10),(10,9),(9,8)},
2
78
P ={(7,6),(6,11),(11,10),(10,9),(9,8)}.
Множество всех путей между заданными вершинами r и j дан-
ного графа будем обозначать
P
jr
={
k
jr
P }.
Контур представляет собой замкнутый путь, т.е. путь у которо-
го совпадают начальная и конечная вершины. Следовательно, контур
может быть задан, так же как и путь. На рис.
2.22 граф имеет четыре
контура. Зададим, например, контур
K
2
рассмотренными выше спо-
собами
K
2
x
={3,4,5,6,3};
K
2
w
={3,5,6,17};
K
2
={(4,3),(5,4),(6,5),(3,6)}.
Множество всех контуров графа будем обозначать
К={К
1,
К
2,
К
3,
К
4
}.
Подграф
G
0
, содержащий вершины всех контуров, называют
контурной частью графа. Среди дуг связного графа (понятия под-
графа и связного графа приведены в следующем подразделе), не
принадлежащих ни одному контуру, можно выделить дуги трех ти-
пов: ни одна из вершин дуги не принадлежит
G
0
, например дуга
(2,1); одна вершина дуги принадлежит G
0
, например дуги (3,2), (7,6),
и (9,8); обе вершины принадлежат G
0
, например дуги (4,10) и (6,11).
Два контура K
i
и К
j
считаются касающимися, если имеют хотя
бы одну общую вершину, т.е.
Страницы
- « первая
- ‹ предыдущая
- …
- 60
- 61
- 62
- 63
- 64
- …
- следующая ›
- последняя »
