ВУЗ:
Составители:
59
K
i
x
∩
K
j
x
≠∅
.
Например, K
1
x
∩
K
2
x
={3,4} и K
1
x
∩
K
4
x
=
∅
.
Касание контуров
r есть бинарное отношение на множестве
контуров
K графа, оно может быть задано неориентированным гра-
фом
R
k
=
<
K,r
>
, который
называют графом касания.
Обозначим множество
контуров графа на рис.
2.22 в виде К={1,2,3,4},
тогда граф касания для
этого множества может
быть иллюстрирован рис.
2.23, a. Аналогично вводятся понятия не-
касания и графа некасания контуров⎯
R
k
=
<
K,
⎯
r
>
(см. рис. 2.23, б).
Очевидно, граф некасания контуров⎯
R
k
является дополнением графа
R
k
до полного графа (полный граф определен в следующем подраз-
деле).
Путь
k
jr
P и контур K
i
считаются касающимися, если имеют хотя
бы одну общую вершину. В примере путь
1
78
x
P и контур К
1
касаются,
т.к.
1
78
x
P
∩
K
1
x
=
{4}.
Если в графе выделить некоторый путь
k
jr
P , то можно говорить
о подмножестве контуров, касающихся этого пути
k
jr
P
rK и не касаю-
щихся пути
k
jr
P ⎯rK . Например, подмножество
1
78
x
P
rK=K, т.е. путь
1
78
x
P
касается всех контуров, а подмножество
P
12,8
rK={4}. Соответствен-
но можно написать
∅
=KrP
78
и
KrP
8,12
={1,2,3}. Можно исследовать
алгебраические свойства отношения касания и отношения некасания
контуров на графах. Например, очевидно, что данные отношения
симметричны.
Рис. 2.23
а
2
1 3
4
2
1 3
4
б
Страницы
- « первая
- ‹ предыдущая
- …
- 61
- 62
- 63
- 64
- 65
- …
- следующая ›
- последняя »
