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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

v w G
v w
d(v, w).
v
e(v)= max
w∈V
d(v, w),
G
2
e(v
1
)=e(v
2
)=e(v
3
)=e(v
5
)=2, e(v
4
)=1.
[n/2].
d(G)= max
v∈V
e(v)
r(G)= min
v∈V
e(v)
G
G
2
d(K
n
)=r(K
n
)=1,
d(C
n
)=r(C
n
)=[n/2].
r(G)≤d(G).
v e(v)=r(G).
v
4
.
   1.5. Äèàìåòð, ðàäèóñ è öåíòð ãðàôà
   Ïóñòü v è w ëþáûå äâå âåðøèíû ñâÿçíîãî ãðàôà G . Íà-
çîâåì ðàññòîÿíèåì ìåæäó v è w äëèíó ñàìîé êîðîòêîé öå-
ïè, ñîåäèíÿþùåé ýòè âåðøèíû, è îáîçíà÷èì êàê d(v, w). Òî-
ãäà êàæäàÿ âåðøèíà ãðàôà v ìîæåò áûòü îõàðàêòåðèçîâàíà
âåëè÷èíîé e(v)= max d(v, w), êîòîðàÿ íàçûâàåòñÿ ýêñöåíòðè-
                  w∈V
ñèòåòîì. Íåòðóäíî óáåäèòüñÿ, ÷òî â ãðàôå G2 íà ðèñ. 1.9
ýêñöåíòðèñèòåò âñåõ âåðøèí ðàâåí òðåì, òîãäà êàê â ãðàôå
íà ðèñ. 1.14 èìååì: e(v1 )=e(v2 )=e(v3 )=e(v5 )=2, e(v4 )=1. Î÷å-
âèäíî, ÷òî â ïîëíîì ãðàôå âñå âåðøèíû èìåþò ýêñöåíòðèñèòåò
ðàâíûé 1, à â ïðîñòîì öèêëå  [n/2].
   Ìàêñèìàëüíûé ýêñöåíòðèñèòåò d(G)= max e(v) íîñèò íà-
                                             v∈V
çâàíèå äèàìåòðà ãðàôà, à ìèíèìàëüíûé r(G)= min e(v)  ðà-
                                                   v∈V
äèóñà ãðàôà G . Äèàìåòð ãðàôà íà ðèñ. 1.14 ðàâåí äâóì, ðà-
äèóñ  åäèíèöå, à â ãðàôå G2 íà ðèñ. 1.9 è äèàìåòð è ðàäèóñ
ðàâíû òðåì. Â ïîëíîì ãðàôå èìååì d(Kn )=r(Kn )=1, à â ïðî-
ñòîì öèêëå  d(Cn )=r(Cn )=[n/2].
   Äëÿ ëþáîãî ãðàôà ñïðàâåäëèâî ñîîòíîøåíèå r(G)≤d(G).
   Âåðøèíà v íàçûâàåòñÿ öåíòðàëüíîé, åñëè e(v)=r(G). Â
ãðàôå íà ðèñ. 1.14 öåíòðàëüíîé ÿâëÿåòñÿ v4 . Ãðàô ìîæåò
èìåòü íåñêîëüêî òàêèõ âåðøèí, à â íåêîòîðûõ ãðàôàõ âñå âåð-
øèíû îêàçûâàþòñÿ öåíòðàëüíûìè, íàïðèìåð êàê â ãðàôàõ íà
ðèñ. 1.9.  ïðîñòîé öåïè ïðè íå÷åòíîì ÷èñëå âåðøèí òîëü-
êî îäíà ÿâëÿåòñÿ öåíòðàëüíîé, à ïðè ÷åòíîì èõ ÷èñëå òàêèõ
âåðøèí äâå. Â ïîëíîì ãðàôå öåíòðàëüíûìè ÿâëÿþòñÿ âñå âåð-
øèíû. Òî æå ñàìîå ñïðàâåäëèâî è äëÿ ïðîñòîãî öèêëà. Ìíî-
æåñòâî âñåõ öåíòðàëüíûõ âåðøèí íàçûâàåòñÿ öåíòðîì ãðàôà.
   Ïîíÿòèÿ öåíòðàëüíîé âåðøèíû è öåíòðà ãðàôà ïîÿâèëèñü
â ñâÿçè ñ çàäà÷àìè îïòèìàëüíîãî ðàçìåùåíèÿ ïóíêòîâ ìàñ-
ñîâîãî îáñëóæèâàíèÿ, òàêèõ êàê áîëüíèöû, ïîæàðíûå ÷àñòè,
ïóíêòû îõðàíû îáùåñòâåííîãî ïîðÿäêà è ò. ï., êîãäà âàæíî
ìèíèìèçèðîâàòü íàèáîëüøåå ðàññòîÿíèå îò ëþáîé òî÷êè íåêî-
òîðîé ñåòè äî áëèæàéøåãî ïóíêòà îáñëóæèâàíèÿ.




                               22

Страницы