Дискретная математика: Основы теории графов и алгоритмизация задач. Прокушев Л.А. - 22 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

22
2
1
(, ) ( ) .
n
ii
i
dxy x y
=
=−
∑
Ïðîñòîé íåçàìêíóòîé êðèâîé â ïðîñòðàíñòâå ε
n
íàçûâàåòñÿ íåïðåðûâ-
íàÿ, ñàìîíåïåðåñåêàþùàÿñÿ êðèâàÿ, ñîåäèíÿþùàÿ äâå ðàçëè÷íûå òî÷êè â
ε
n
(ò. å. êðèâàÿ, ïîëó÷åííàÿ íåïðåðûâíîé äåôîðìàöèåé ïðÿìîëèíåéíîãî
îòðåçêà). Àíàëîãè÷íî ïðîñòîé çàìêíóòîé êðèâîé íàçûâàåòñÿ íåïðåðûâíàÿ
ñàìîíåïåðåñåêàþùàÿñÿ êðèâàÿ, êîíå÷íûå òî÷êè êîòîðîé ñîâïàäàþò.
Ãåîìåòðè÷åñêèé ãðàô â ïðîñòðàíñòâå ε
n
åñòü ìíîæåñòâî V={v
i
} òî÷åê
ïðîñòðàíñòâà ε
n
è ìíîæåñòâî U={u
i
} ïðîñòûõ êðèâûõ, óäîâëåòâîðÿþùèõ
ñëåäóþùèì óñëîâèÿì:
1. Êàæäàÿ çàìêíóòàÿ êðèâàÿ â U ñîäåðæèò òîëüêî îäíó òî÷êó v∈V.
2. Êàæäàÿ íåçàìêíóòàÿ êðèâàÿ â U ñîäåðæèò ðîâíî äâå òî÷êè ìíîæåñòâà
V, êîòîðûå ÿâëÿþòñÿ åå ãðàíè÷íûìè òî÷êàìè.
3. Êðèâûå â U íå èìåþò îáùèõ òî÷åê, çà èñêëþ÷åíèåì òî÷åê èç ìíîæå-
ñòâà V.
Ðàíåå áûëî îòìå÷åíî, ÷òî ëþáîé ãðàô â àáñòðàêòíîì ñìûñëå èäåíòè-
÷åí, èëè, èñïîëüçóÿ áîëåå ïðèíÿòûé òåðìèí, èçîìîðôåí íåêîòîðîìó ãåî-
ìåòðè÷åñêîìó ãðàôó.
Ãîâîðÿò, ÷òî ãðàôû G=(V,
U
) è G'=(V',
U
') èçîìîðôíû äðóã äðóãó, åñëè
ñóùåñòâóåò âçàèìíî îäíîçíà÷íîå ñîîòíîøåíèå ìåæäó V è V' è ìåæäó
U
è
U
', ñîõðàíÿþùåå îòíîøåíèå èíöèäåíòíîñòè. Èíà÷å ãîâîðÿ, ðåáðî
u
èí-
öèäåíòíî âåðøèíå v ãðàôà G òîãäà è òîëüêî òîãäà, êîãäà èíöèäåíòíû ñîîò-
âåòñòâóþùèå ýëåìåíòû
u
' è v' â ãðàôå G'. Åñëè ãðàô G èçîìîðôåí ãåî-
ìåòðè÷åñêîìó ãðàôó G', òî G' íàçûâàåòñÿ ãåîìåòðè÷åñêîé ðåàëèçàöèåé ãðàôà G.
Ãðàô íàçûâàåòñÿ ïëîñêèì òîãäà è òîëüêî òîãäà, êîãäà îí èìååò ãåîìåòðè-
÷åñêóþ ðåàëèçàöèþ â ïðîñòðàíñòâå ε
2
, ò. å. íà ïëîñêîñòè. Íàïðèìåð, ãðàô
G íà ðèñ. 1.12,à ïëîñêèé, òàê êàê îí èçîìîðôåí ãðàôó G', èçîáðàæåí-
íîìó ðÿäîì.
Ðèñ. 1.12. Ïëîñêèé ãðàô
v
v
v
"
v
!
à
G:
á
)
G:
v
v
v
!
v
"

Страницы