Составители:
Рубрика:
8
âèäåòü, ÷òî îïðåäåëåíî îòîáðàæåíèå f
1
: Y→X. Èìåííî, f
1
(y)=a òîãäà
è òîëüêî òîãäà, êîãäà f
1
({y})={a}.
1.2. Îñíîâíûå ïîíÿòèÿ äëÿ ãðàôîâ
1.2.1. Ãåîìåòðè÷åñêîå ïðåäñòàâëåíèå ãðàôîâ
Ïðåæäå ÷åì îïðåäåëèòü ïîíÿòèå ãðàôà â íàèáîëåå îáùåé ôîðìå, ïî-
ëåçíî ðàññìîòðåòü ãåîìåòðè÷åñêóþ ôîðìó ãðàôîâ. Ýòî ïîçâîëèò ñ ñà-
ìîãî íà÷àëà ïîëó÷èòü óäîáíîå, íàãëÿäíîå ïðåäñòàâëåíèå ðàçëè÷íûõ ïî-
íÿòèé è ñòðóêòóð, êîòîðûå áóäóò ðàññìàòðèâàòüñÿ â äàëüíåéøåì. Ëþ-
áîé ãðàô â àáñòðàêòíîì ñìûñëå ýêâèâàëåíòåí (ïî îòíîøåíèþ ê ñâîé-
ñòâàì, èçó÷àåìûì â òåîðèè ãðàôîâ) íåêîòîðîìó ãåîìåòðè÷åñêîìó ãðà-
ôó. Ïðè íåêîòîðîé èäåàëèçàöèè ìíîãèå èçâåñòíûå ñòðóêòóðû ìîæíî
ðàññìàòðèâàòü êàê ãåîìåòðè÷åñêèå ãðàôû è èçó÷àòü ñ ïîìîùüþ ìåòî-
äîâ òåîðèè ãðàôîâ. Íàïðèìåð, â âèäå ãðàôà ìîæíî ïðåäñòàâèòü ñèñòå-
ìó èëè ñåòü óëèö â ãîðîäå, åñëè ïðåíåáðå÷ü øèðèíîé ïîñëåäíèõ, à ïåðå-
ñå÷åíèÿ ñ÷èòàòü òî÷êàìè.
Ãåîìåòðè÷åñêèé ãðàô åñòü ãåîìåòðè÷åñêàÿ êîíôèãóðàöèÿ èëè ñòðóê-
òóðà â ïðîñòðàíñòâå, ñîñòîÿùàÿ èç ìíîæåñòâà òî÷åê, âçàèìîñâÿçàííûõ
ìíîæåñòâîì íåïðåðûâíûõ, ñàìîíåïåðåñåêàþùèõñÿ êðèâûõ.
Íà ðèñ. 1.1 ïîêàçàíî îáû÷íîå ïðåäñòàâëåíèå ãåîìåòðè÷åñêîãî ãðàôà,
ñ ïîìîùüþ êîòîðîãî ìîæíî ïðîèëëþñòðèðîâàòü íåêîòîðûå òåðìèíû
òåîðèè ãðàôîâ.
Ñ ïîçèöèè òåîðèè ãðàôîâ ýëåìåíòû v íàçûâàþòñÿ âåðøèíàìè ãðàôà,
à ñîåäèíÿþùèå èõ íåîðèåíòèðîâàííûå ëèíèè (u) ðåáðàìè èëè äóãàìè,
åñëè ëèíèè ñíàáæåíû ñòðåëêàìè, è òîãäà ðàçëè÷àþò íåîðèåíòèðîâàí-
íûé ãðàô (ðèñ.1.1,à) èëè îðèåíòèðîâàííûé ãðàô (ñîêðàùåííî îðãðàô)
(ðèñ.1.1,á). Åñëè ìíîæåñòâî âåðøèí (V) è ðåáåð (äóã) (U) êîíå÷íî, òî ãðàô
íàçûâàåòñÿ êîíå÷íûì. Ìû áóäåì ðàññìàòðèâàòü òîëüêî êîíå÷íûå ãðàôû.
v
!
v
v
v
$
v
#
v
v
v
!
v
!
u
!
u
u
"
u
v
"
u
#
u
$
u
u
$
u
u
!
u
"
u
#
u
%
á
Ðèñ. 1.1. Ãåîìåòðè÷åñêîå ïðåäñòàâëåíèå ãðàôîâ:
à íåîðèåíòèðîâàííûé ãðàô; á îðèåíòèðîâàííûé ãðàô
a)
Страницы
- « первая
- ‹ предыдущая
- …
- 6
- 7
- 8
- 9
- 10
- …
- следующая ›
- последняя »
