Элементы теории графов. Домнин Л.Н. - 21 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

B
i
B
j
v
i
v
j
BB
T
A=BB
T
−D D= diag(deg v
1
, deg v
2
, . . . , deg v
n
)
e
1
e
2
e
3
e
4
e
5
e
6
e
7
v
1
v
1
v
1
v
2
v
2
v
3
v
4
v
2
v
3
v
4
v
3
v
4
v
4
v
5
v
1
v
2
, v
3
, v
4
v
2
v
1
, v
3
, v
4
v
3
v
1
, v
2
, v
4
v
4
v
1
, v
2
, v
3
, v
5
v
5
v
2
   Ïîñêîëüêó â ãðàôå îòñóòñòâóþò ïàðàëëåëüíûå ðåáðà, òî
ñêàëÿðíîå ïðîèçâåäåíèå ëþáîé ïàðû âåêòîðîâ èíöèäåíòíîñòè
Bi Bj ðàâíî åäèíèöå, åñëè âåðøèíû vi è vj ñìåæíû, è íó-
ëþ, åñëè ýòè âåðøèíû íåñìåæíû. Ñëåäîâàòåëüíî, ïðîèçâåäå-
íèå BBT äîëæíî ñîâïàäàòü ñ ìàòðèöåé ñìåæíîñòè ãðàôà çà
èñêëþ÷åíèåì äèàãîíàëüíûõ ýëåìåíòîâ, êîòîðûå ðàâíû ñòå-
ïåíÿì ñîîòâåòñòâóþùèõ âåðøèí. Ýòî îçíà÷àåò, ÷òî ìàòðèöà
ñìåæíîñòè è ìàòðèöà èíöèäåíòíîñòè ãðàôà ñâÿçàíû ñîîòíî-
øåíèåì A=BBT −D , ãäå D= diag(deg v1 , deg v2 , . . . , deg vn ) .
   Ïðèìåíèòåëüíî ê ìàòðèöàì èíöèäåíòíîñòè èçîìîðôíûõ
ãðàôîâ òàêæå ñïðàâåäëèâî óòâåðæäåíèå î òîì, ÷òî îíè ìîãóò
áûòü ïîëó÷åíû îäíà èç äðóãîé ïóòåì íåêîòîðîé ïåðåñòàíîâêè
ñòðîê è ñòîëáöîâ.
   Êðîìå ðàññìîòðåííûõ äëÿ ïðåäñòàâëåíèÿ ãðàôîâ èñïîëü-
çóþò è äðóãèå ìàòðèöû. Íåêîòîðûå èç íèõ îïèñàíû â ñëåäó-
þùèõ ðàçäåëàõ.
   Ñïèñêè. Ïðè ðåøåíèè ìíîãèõ çàäà÷ íàðÿäó ñ ìàòðèöàìè
äëÿ ïðåäñòàâëåíèÿ ãðàôîâ èñïîëüçóþò ñïèñîê ðåáåð (ñïèñîê
èíöèäåíòíîñòè) è ñïèñîê âåðøèí (ñïèñîê ñìåæíîñòè). Òàê,
äëÿ ãðàôà íà ðèñ. 1.14 ýòè ñïèñêè èìåþò âèä:
                                              Ñïèñîê âåðøèí
              Ñïèñîê ðåáåð                    v1 v2 , v3 , v4
       e1   e2 e3 e4 e5 e6 e7                 v2 v1 , v3 , v4
                                              v3 v1 , v2 , v4        .
       v1   v1 v1 v2 v2 v3 v4
       v2   v3 v4 v3 v4 v4 v5                 v4 v1 , v2 , v3 , v5
                                              v5 v2

   Â ñïèñêå ðåáåð êàæäîå ðåáðî ïðåäñòàâëåíî ïàðîé êîíöå-
âûõ âåðøèí, à â ñïèñêå ñìåæíîñòè äëÿ êàæäîé âåðøèíû óêà-
çàíû âñå ñìåæíûå ñ íåé. Ìîæíî ñ÷èòàòü, ÷òî ñïèñîê ðåáåð
ÿâëÿåòñÿ êîìïàêòíîé çàïèñüþ ìàòðèöû èíöèäåíòíîñòè, åñëè
â êàæäîì ñòîëáöå çàìåíèòü îáå åäèíèöû îáîçíà÷åíèåì ñîîò-
âåòñòâóþùèõ âåðøèí (ñòðîê), à íóëè îòáðîñèòü. Àíàëîãè÷íî
èç ìàòðèöû ñìåæíîñòè ìîæíî ïîëó÷èòü ñïèñîê âåðøèí, åñëè
åäèíèöû â êàæäîé ñòðîêå çàìåíèòü îáîçíà÷åíèåì ñîîòâåòñòâó-
þùåé âåðøèíû (ñòîëáöà) è îòáðîñèòü íóëè.



                               21

Страницы