Дуги, инцидентные подмножеству вершин

Пусть задан граф G=(V,U) и непустое подмножество V₁  V. Говорят, что дуга u=(v_i , v_j ) заходит в V₁ , если v_i  V₁ , а v_j  V₁. Если же v_i  V₁ , а v_j  V₁ ,

- 7 -

то говорят, что дуга исходит из V₁. В обоих случаях дугу называют инцидентной подмножеству V₁.

Обозначим через и множества дуг, заходящих в V₁ и исходящих из него. Если подмножество V₁ сводится к одной вершине, то дугу называют инцидентной этой вершине по общему определению. Например, для графа на рис. 3.1 выделим подмножество V₁={v₂ , v­₃}, тогда ={u₁=(v_1,v₂)}, = {u₂=(v₂,v₁), u₆=(v₃,v₄)}.

|| S || :

	v1	v2	v3	v4	v5
v­1	0	1	0	0	0
v2	1	0	2	0	0
v3	0	0	1	1	0
v4	1	0	0	0	0
v5	0	0	0	1	1

u₁

v₁ v₂ V₁ u₂

u₇ u₄ u₃

v₅ v₃

u ₉ u₈ v₄ u₆ u₅

Рис. 3.1. Орграф и его матрица смежности

Кратными называются дуги, граничные точки которых совпадают. При этом, если, например, как на рис. 3.1 u₃=(v₂, v₃) и u₄=(v₂,v₃), то дуги u₃ и u₄ называются параллельными, а если u₁=(v₁, v₂), но u₂=(v₂, v₁), то дуги u₁ и u₂ будем называть встречными. Орграф без параллельных дуг описывается булевой матрицей смежности.

Обозначим через Гv подмножество вершин, смежных с вершиной v, в которые можно придти по инцидентным дугам (стрелки исходят из v), или иначе это подмножество вершин-концов дуг, имеющих началом вершину v. Например, для орграфа на рис. 3.1

Гv₁={v₂}, Гv₂={v₁,v₃}, Гv₃={v₃,v₄}, Гv₄={v₁}, Гv₅={v₄,v₅}.

По матрице смежности ||S|| можно выделить подмножество Гv_i по строке i, где ненулевые элементы s_ij указывают на вершины v_j  Гv_i . Отображение инцидентности и смежности Г позволяет определить граф как пару

G=(V,Г), образованную множеством вершин V и многозначным отображением Г множества V в себя. Элемент v_iV является вершиной, а пара (v_i,v_j), где v_jГv_i, дугой. Граф G имеет порядок n, если число вершин |V|=n.

Отображение Г можно определить для любого подмножества из V. Например, для орграфа на рис.3.1 Г{v₁, v₂}= Гv₁  Гv₂ = {v₂}  {v₁,v₃}= {v₁, v₂, v₃}.

Определим орграф G^-1 c помощью обратного отображения Г^-1:

G^-1 = (V, Г^-1).

- 8 -

Соответствующее представление графа G^-1 получается, если Г^-1v рассматривать как подмножество вершин, смежных с v , из которых можно зайти в вершину v по инцидентным дугам. При этом матрица смежности графа G^-1 образуется транспонированием (перестановкой строк и столбцов) матрицы смежности орграфа G. Например, для графа на рис. 3.1 имеем:

Г^-1v₁={v₂,v₄}, Г^-1v₂={v₁}, Г^-1v­₃={v₂,v₃}, Г^-1v₄={v₃,v₅}, Г^-1v₅={v₅}.

Обозначим через Гⁿv подмножества тех вершин (концы дуг), в которые можно придти из вершины v не более чем через n смежных дуг, а через Г^-nv подмножества тех вершин (начала дуг), из которых можно попасть в вершину v не более чем через n смежных дуг. Например, на рис. 3.1 имеем:

Г²v₁ = Г{Гv₁} = Г{v₂} = {v₁,v₃};

Г^-2v₁ = Г^-1{Г^-1v₁} = Г^-1{v₂,v₄} = Г^-1v₂  Г^-1v₄ = {v₁,v₃,v₅}.

Транзитивным замыканием v_i называется многозначное отображение, определяемое формулой

v_i = {v_i}  Гv_i  Г²v_i  ... , т.е. это множество вершин (концы дуг), в которые можно придти из v_i по стрелкам, а также вершина v_i.

Аналогично, обратное транзитивное замыкание

^-v_i = {v_i}  Г^-1v_i  Г^-2v_i  ... есть множество вершин (начала дуг), из которых можно попасть в v_i по стрелкам, а также вершина v_i .

Например, на рис. 3.1

v₁ = { v₁, v₂, v₃, v₄ } , ^-v₁ = { v₁, v₂, v₃, v₄, v₅ } = V , т.е. из вершины v₁ нельзя придти в вершину v₅, а в вершину v₁ можно придти из любых других вершин орграфа.