Составители:
Рубрика:
19
øèí, èñêëþ÷àÿ, êîíå÷íî, v è w. Íàïðèìåð, ëþáîé ïðîñòîé öèêë (èñêëþ-
÷àÿ ïåòëè) îáðàçóþò 2-ñâÿçíûé ãðàô. Íà ðèñ.1.9 èçîáðàæåí 4-ñâÿçíûé
ãðàô. Ïðè k=1 ýòî ïîíÿòèå ñîâïàäàåò ñ ïîíÿòèåì îáû÷íîé ñâÿçíîñòè.
Íàïðèìåð, äåðåâî ýòî îäíîñâÿçíûé ãðàô.
Äâóäîëüíûì íàçûâàåòñÿ ãðàô, â êîòîðîì âåðøèíû ìîãóò áûòü ðàçáè-
òû íà äâà íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâà V
1
è V
2
òàê, ÷òî êàæäîå
ðåáðî èìååò îäíó ãðàíè÷íóþ òî÷êó â V
1
, à äðóãóþ â V
2
. Â îáùåì ñëó-
÷àå ãðàô íàçûâàåòñÿ k-äîëüíûì, åñëè ìíîæåñòâî åãî âåðøèí ìîæíî
ðàçáèòü íà k íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâ {V
1
, V
2
, , V
k
} òàê, ÷òî
íå ñóùåñòâóåò ðåáåð, ñîåäèíÿþùèõ âåðøèíû îäíîãî è òîãî æå ïîäìíî-
æåñòâà. Äâóäîëüíûé ãðàô èçîáðàæàþò, ðàçìåùàÿ ìíîæåñòâà âåðøèí
V
1
è V
2
â ðàçíûõ ñòîëáöàõ (èëè ñòðîêàõ), êàê ïîêàçàíî íà ðèñ. 1.10.
1.3.9. Ìàòðè÷íîå ïðåäñòàâëåíèå ãðàôîâ
Ìàòðèöà èíöèäåíöèé
Äëÿ óäîáñòâà îáðàáîòêè ãðàôîâ ñ èñïîëüçîâàíèåì ÝÂÌ ëó÷øå âñå-
ãî ïîäõîäèò ìàòðè÷íàÿ ôîðìà ïðåäñòàâëåíèÿ ãðàôà. Ïóñòü G ãðàô,
èìåþùèé n âåðøèí è m ðåáåð. Ãðàô G ìîæíî îïèñàòü ìàòðèöåé èí-
öèäåíöèé A ðàçìåðîì n×m, ñòðîêè è ñòîëáöû êîòîðîé ñîîòâåòñòâóþò
âåðøèíàì è ðåáðàì ãðàôà. Ýëåìåíò ìàòðèöû a
ij
ïðèíèìàåò çíà÷åíèå
1 èëè 0 â çàâèñèìîñòè îò òîãî, èíöèäåíòíî j-å ðåáðî i-é âåðøèíå
èëè íåò. Äëÿ ïåòëè âñå ýëåìåíòû ñòîëáöà ñ÷èòàþòñÿ ðàâíûìè 0. Ìàò-
ðèöû, ñîäåðæàùèå òîëüêî ýëåìåíòû 1 èëè 0, íàçûâàþòñÿ áóëåâûìè
ìàòðèöàìè. Íà ðèñ. 1.11 ïðåäñòàâëåí äâóõêîìïîíåíòíûé ãðàô è åãî
ìàòðèöà èíöèäåíöèé.
Íåêîòîðûå ñâîéñòâà ãðàôà ïðîÿâëÿþòñÿ â åãî ìàòðèöå èíöèäåíöèé. Íà-
ïðèìåð, òàê êàê ðåáðî ãðàôà èíöèäåíòíî òî÷íî äâóì âåðøèíàì, òî êàæäûé
Ðèñ. 1.10. Äâóäîëüíûé ãðàô
v
v
v
"
v
!
Ðèñ. 1.9. Ïðèìåð
îáûêíîâåííîãî ïîëíîãî ãðàôà
V
V
Страницы
- « первая
- ‹ предыдущая
- …
- 17
- 18
- 19
- 20
- 21
- …
- следующая ›
- последняя »
