Составители:
Рубрика:
12
1.3.2. Ëîêàëüíûå ñâîéñòâà íåîðèåíòèðîâàííûõ ãðàôîâ
Äëÿ îïèñàíèÿ ðàçëè÷íûõ ñòðóêòóðíûõ ñâîéñòâ ãðàôîâ ïîëåçíî ââåñ-
òè ðÿä äîïîëíèòåëüíûõ ïîíÿòèé, êîòîðûå îñîáåííî íàãëÿäíî èëëþñò-
ðèðóþòñÿ íà ïðèìåðå ãåîìåòðè÷åñêèõ ãðàôîâ, ïîêàçàííûõ âûøå, à òàê-
æå íà ðèñ. 1.4.
Åñëè
u
=[v, w], òî v è w íàçûâàþòñÿ ãðàíè÷íûìè òî÷êàìè
u
íåçàâè-
ñèìî îò òîãî, ÿâëÿåòñÿ ãðàô ãåîìåòðè÷åñêèì èëè íåò.
Ïåòëåé
u
=[v, v] íàçûâàåòñÿ ðåáðî
u
c åäèíñòâåííîé ãðàíè÷íîé òî÷-
êîé, ò. å. ïåòëÿ èíöèäåíòíà îäíîé âåðøèíå, íàïðèìåð ïåòëè
u
4
è
u
5
íà
ðèñ. 1. 4.
Ïàðàëëåëüíûìè (êðàòíûìè) íàçûâà-
þòñÿ ðåáðà, åñëè îíè ñîåäèíÿþò îäíè
è òå æå âåðøèíû, íàïðèìåð
u
1
~[v
1
, v
2
]
è
u
2
~[v
1
, v
2
].  ÷àñòíîñòè, äâå ïåòëè,
èíöèäåíòíûå îäíîé è òîé æå âåðøèíå,
ÿâëÿþòñÿ ïàðàëëåëüíûìè, íàïðèìåð
u
4
è
u
5
.
Ãðàô G, èìåþùèé ïàðàëëåëüíûå
ðåáðà, íàçûâàåòñÿ ìóëüòèãðàôîì, íà-
ïðèìåð ìóëüòèãðàôû íà ðèñ. 1.1 è 1.4.
Ñìåæíûìè âåðøèíàìè íàçûâàþòñÿ
âåðøèíû v è w, îáðàçóþùèå ãðàíè÷íûå òî÷êè ðåáðà
u
~[v, w]. Îäíà
âåðøèíà ìîæåò èìåòü íåñêîëüêî ñìåæíûõ âåðøèí, åñëè â íåé ñõîäÿòñÿ
íåñêîëüêî ðåáåð, íàïðèìåð äëÿ âåðøèíû v
2
ñìåæíûìè ÿâëÿþòñÿ âåðøè-
íû v
1
è v
3
(ðèñ. 1.4).  ÷àñòíîñòè, âåðøèíà v ñìåæíà ñàìà ñ ñîáîé, åñëè
ñóùåñòâóåò ïåòëÿ, èíöèäåíòíàÿ v, íàïðèìåð âåðøèíà v
3
ñìåæíà ñàìà ñ
ñîáîé (ðèñ. 1. 4), â ïðîòèâíîì ñëó÷àå v íå ìîæåò áûòü ñìåæíîé ñàìà ñ
ñîáîé.
Ñìåæíûìè ðåáðàìè íàçûâàþòñÿ òàêèå, êîòîðûå èìåþò, ïî êðàéíåé
ìåðå, îäíó îáùóþ ãðàíè÷íóþ òî÷êó. Íàïðèìåð, íà ðèñ. 1.4 ñìåæíûìè
ÿâëÿþòñÿ ðåáðà
u
1
,
u
2
,
u
3
ñ îáùåé âåðøèíîé v
2
. Ñìåæíûìè ìîæíî
ñ÷èòàòü òàêæå ïàðàëëåëüíûå ðåáðà (
u
1
è
u
2
) è ïåòëè (
u
4
è
u
5
).
Çàìåòèì, ÷òî ñìåæíîñòü ÿâëÿåòñÿ îòíîøåíèåì ìåæäó äâóìÿ ïîäîá-
íûìè ýëåìåíòàìè (ìåæäó âåðøèíàìè èëè ðåáðàìè), òîãäà êàê èíöèäåí-
òíîñòü åñòü îòíîøåíèå ìåæäó ðàçíîðîäíûìè ýëåìåíòàìè (âåðøèíàìè è
ðåáðàìè).
L
L
L
"
L
!
1
u
2
u
3
u
4
u
5
u
Ðèñ. 1.4. Ïðèìåð
íåîðèåíòèðîâàííîãî ãðàôà
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
