Дискретная математика: Основы теории графов и алгоритмизация задач. Прокушев Л.А. - 26 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

26
(êîíåö äóãè v
j
íàõîäèòñÿ â V
1
). Åñëè æå v
i
∈V
1
, à v
j
∉V
1
, òî ãîâîðÿò, ÷òî
äóãà u èñõîäèò èç V
1
(íà÷àëî äóãè v
i
íàõîäèòñÿ â V
1
).  îáîèõ ñëó÷àÿõ
äóãó u íàçûâàþò èíöèäåíòíîé ïîäìíîæåñòâó V
1
. Îáîçíà÷èì ÷åðåç
1
V
U
+
è
1
V
U
−
ìíîæåñòâà äóã, çàõîäÿùèõ â V
1
è èñõîäÿùèõ èç íåãî. Íàïðèìåð,
äëÿ ãðàôà íà ðèñ.1.15
1
V
U
+
= {u
1
=(v
1
, v
2
)},
1
V
U
−
= {u
2
=(v
2
, v
1
), u
6
(v
3
, v
4
)}.
Åñëè ïîäìíîæåñòâî ñâîäèòñÿ ê îäíîé âåðøèíå, òî äóãó íàçûâàþò
èíöèäåíòíîé ýòîé âåðøèíå (çàõîäÿùåé â íåå èëè èñõîäÿùåé èç íåå).
Îáîçíà÷èì ÷åðåç Ãv ïîäìíîæåñòâî âåðøèí V, ñìåæíûõ ñ v, â êîòî-
ðûå ìîæíî ïðèéòè ïî èíöèäåíòíûì äóãàì (ñòðåëêè èñõîäÿò èç v) èëè
èíà÷å ïîäìíîæåñòâî êîíöîâ äóã, èìåþùèõ íà÷àëîì âåðøèíó v. Íàïðè-
ìåð, äëÿ ãðàôà íà ðèñ. 1.15
Ãv
1
= {v
2
}, Ãv
2
= {v
1
, v
3
}, Ãv
3
= {v
3
, v
4
}, Ãv
4
= {v
1
}, Ãv
5
= {v
4
, v
5
}.
Ïî ìàòðèöå ñìåæíîñòè 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,
íàïðèìåð äëÿ ãðàôà íà ðèñ. 1.15
Ã{v
1
, v
2
} = Ãv
1
∪ Ãv
2
= {v
2
}∪{v
1
, v
3
} = {v
1
, v
2
, v
3
}.
Îïðåäåëèì ãðàô G
1
ñ ïîìîùüþ îáðàòíîãî îòîáðàæåíèÿ Ã
1
:
G
1
= (V, Ã
1
).
Ñîîòâåòñòâóþùèå ïðåäñòàâëåíèÿ ãðàôà G
1
ïîëó÷àþòñÿ, åñëè Ã
1
v
ðàññìàòðèâàòü êàê ïîäìíîæåñòâà âåðøèí, ñìåæíûõ ñ v, èç êîòîðûõ ìîæíî
çàéòè â âåðøèíó v ïî èíöèäåíòíûì äóãàì, ïðè ýòîì ìàòðèöà ñìåæíîñ-
òè ãðàôà G
1
îáðàçóåòñÿ òðàíñïîíèðîâàíèåì (ïåðåñòàíîâêîé ñòðîê è
ñòîëáöîâ) ìàòðèöû ñìåæíîñòè ãðàôà G. Íàïðèìåð, äëÿ ãðàôà íà ðèñ.1.15
Ã
1
v
1
={v
2
, v
4
}, Ã
1
v
2
={v
1
}, Ã
1
v
3
={v
2
, v
3
}, Ã
1
v
4
={v
3
, v
5
}, Ã
1
v
5
={v
5
}.

Страницы