Составители:
Рубрика:
21
òåëüíîé íóìåðàöèåé ðåáåð è âåðøèí âíóòðè êàæäîé êîìïîíåíòû è ìåæäó
êîìïîíåíòàìè, êàê ïîêàçàíî â ïðèìåðå, èëè íåïîñðåäñòâåííî ñ ïîìî-
ùüþ ïîäñòàíîâêè ñòðîê è ñòîëáöîâ ìàòðèöû èíöèäåíöèé.
Ìîæíî óòâåðæäàòü, ÷òî äâà ãðàôà èçîìîðôíû, åñëè îíè èìåþò îäíè
è òå æå ìàòðèöû èíöèäåíöèé ñ òî÷íîñòüþ äî ïåðåñòàíîâîê ñòðîê è ñòîë-
áöîâ. Òàêèì îáðàçîì, ìàòðèöà èíöèäåíöèé îáåñïå÷èâàåò ïîëíîå îïèñà-
íèå ãðàôà (åñëè ïåòëè èñêëþ÷åíû).
Ìàòðèöà ñìåæíîñòè âåðøèí
Äëÿ íåîðèåíòèðîâàííûõ ãðàôîâ ìîæíî îïðåäåëèòü ìàòðèöó ñìåæ-
íîñòè âåðøèí (èëè ïðîñòî ìàòðèöó ñìåæíîñòè). Ýòî êâàäðàòíàÿ ìàòðè-
öà S-ðàçìåðà n×n, ãäå ñòðîêè è ñòîëáöû ñîîòâåòñòâóþò âåðøèíàì ãðàôà,
à ýëåìåíò s
i j
ðàâåí ÷èñëó ðåáåð, èíöèäåíòíûõ îäíîâðåìåííî i-é è j-é
âåðøèíàì. Òàêèì îáðàçîì, äëÿ ãðàôà íà ðèñ. 1.11 èìååì ìàòðèöó ñìåæ-
íîñòè
S
7×7
=
L
1
L
2
L
3
L
4
L
5
L
6
L
7
L
1
1100000
L
2
1011000
L
3
0101000
L
4
0110000
L
5
0000021
L
6
0000201
L
7
0000110
.
Ìàòðèöà ñìåæíîñòè íåîðèåíòèðîâàííîãî ãðàôà (áåç ïåòåëü) ñèììåò-
ðè÷íà îòíîñèòåëüíî ãëàâíîé äèàãîíàëè, ïîñêîëüêó ïàðå âåðøèí (v
i
, v
j
)
èíöèäåíòíû îäèíàêîâûå ðåáðà [v
i
, v
j
]=[v
j
, v
i
], ò. å. äîñòàòî÷íî ðàññìàò-
ðèâàòü òîëüêî ïîëîâèíó ìàòðèöû âûøå ãëàâíîé äèàãîíàëè. Î÷åâèäíî,
÷òî ìàòðèöà ñìåæíîñòè îáûêíîâåííîãî ãðàôà (áåç ïåòåëü è êðàòíûõ
ðåáåð) ÿâëÿåòñÿ áóëåâîé ìàòðèöåé.
1.3.10. Èçîìîðôèçì ãðàôîâ. Ïëîñêèé ãðàô
Âåðíåìñÿ ê ïîíÿòèþ ãåîìåòðè÷åñêîãî ãðàôà, ðàñøèðèâ åãî. Îáîçíà-
÷èì n-ìåðíîå åâêëèäîâî ïðîñòðàíñòâî ε
n
. Åâêëèäîâî n-ìåðíîå ïðî-
ñòðàíñòâî åñòü ìíîæåñòâî ïîñëåäîâàòåëüíîñòåé èç n äåéñòâèòåëü-
íûõ ÷èñåë x = (x
1
, , x
n
), â êîòîðîì ðàññòîÿíèå ìåæäó ëþáûìè äâóìÿ
òî÷êàìè x = (x
1
, ,x
n
) è y = (y
1
, , y
n
) îïðåäåëåíî ñëåäóþùèì îáðàçîì:
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »
