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

UptoLike

ВУЗ: 

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

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

Рубрика: 

20
ñòîëáåö ìàòðèöû èíöèäåíöèé ñîäåðæèò ðîâíî äâå 1, ïðè÷åì äëÿ êðàòíûõ
ðåáåð â îäèíàêîâûõ ñòðîêàõ. Èñêëþ÷åíèå ñîñòàâëÿåò ïåòëÿ, òàê êàê îíà
äâàæäû èíöèäåíòíà îäíîé è òîé æå âåðøèíå. Ñòîëáåö, ñîîòâåòñòâóþùèé
ïåòëå, ñîñòîèò èç íóëåé. Òàêèì îáðàçîì, ìàòðèöà èíöèäåíöèé íå óêàçûâà-
åò íà ñóùåñòâîâàíèå ïåòåëü äëÿ êîíêðåòíîé âåðøèíû, ïîýòîìó ïðè èçó÷å-
íèè ãðàôîâ ñ ïîìîùüþ òàêèõ ìàòðèö æåëàòåëüíî èñêëþ÷àòü ïåòëè.
Ïðè ñîîòâåòñòâóþùåé íóìåðàöèè ðåáåð è âåðøèí ãðàôà êàæäàÿ åãî
êîìïîíåíòà ñîîòâåòñòâóåò ïîäìàòðèöå ìàòðèöû èíöèäåíöèé, êîòîðàÿ â ýòîì
ñëó÷àå èìååò áëî÷íóþ ñòðóêòóðó ñëåäóþùåãî âèäà:
1
2
A0...0
0 A ... 0
A
... ... ... ...
0 0 ... A
n



=




,
ãäå À
i
ìàòðèöà èíöèäåíöèé, ñîîòâåòñòâóþùàÿ i-é êîìïîíåíòå ãðàôà.
Áëî÷íî-äèàãîíàëüíîå ïðåäñòàâëåíèå ãðàôà ìîæíî ïîëó÷èòü ïîñëåäîâà-
Ðèñ.1.11. Ìàòðè÷íîå ïðåäñòàâëåíèå ãðàôà
à ãðàô; á ìàòðèöà èíöèäåíöèé
v
v
v
"
v
!
1
u
2
u
3
u
4
u
5
u
à
v
#
v
%
v
$
9
u
8
u
7
u
6
u
á)
u
1
u
2
u
3
u
4
u
5
u
6
7
u
8
u
9
A
7×9
=
L
1
010000000
L
2
011100000
L
3
001010000
L
4
000110000
L
5
000001110
L
6
000001101
L
7
000000011

Страницы