Составители:
Рубрика:
9
Âåðøèíû, ñâÿçàííûå ðåáðîì èëè äóãîé, íàçûâàþòñÿ ñìåæíûìè. Åñëè
ñìåæíûå âåðøèíû ñâÿçàíû áîëåå ÷åì îäíèì ðåáðîì èëè äóãîé, òî òà-
êèå ðåáðà (äóãè) íàçûâàþòñÿ êðàòíûìè, èëè ïàðàëëåëüíûìè (u
3
, u
4
íà
ðèñ. 1.1,à; u
2
, u
3
íà ðèñ. 1.1,á), à ñàì ãðàô íàçûâàåòñÿ ìóëüòèãðàôîì, ò.
å. ãðàôû íà ðèñ. 1.1 ÿâëÿþòñÿ ìóëüòèãðàôàìè. Âåðøèíû, íåñâÿçàííûå ñ
äðóãèìè, íàçûâàþòñÿ èçîëèðîâàííûìè, íàïðèìåð, v
4
íà ðèñ. 1.1,à. Ðåá-
ðî (äóãà), íà÷èíàþùååñÿ è çàêàí÷èâàþùååñÿ â îäíîé òî÷êå, íàçûâàåòñÿ
ïåòëåé (ïåòëè u
6
íà ðèñ. 1.1,à è u
7
íà ðèñ. 1.1,á). Ãîâîðÿò, ÷òî ðåáðî
(äóãà) è åãî ãðàíè÷íûå òî÷êè èíöèäåíòíû äðóã äðóãó, èíà÷å ãîâîðÿ,
âåðøèíû, èíöèäåíòíûå ðåáðó (äóãå), ÿâëÿþòñÿ åãî êîíöåâûìè òî÷êà-
ìè, íàïðèìåð, íà ðèñ. 1.1,à ðåáðó u
1
èíöèäåíòíû âåðøèíû v
1
è v
3
, à
âåðøèíå v
3
èíöèäåíòíû ðåáðà u
1
, u
3
, u
4
.
Âîîáùå ãîâîðÿ, ìíîæåñòâî äóã U (íî íå âåðøèí V) ìîæåò áûòü ïóñ-
òûì, òîãäà ãîâîðÿò, ÷òî ãðàô âûðîæäåííûé.
1.2.2. Àáñòðàêòíûå ãðàôû
Ãåîìåòðè÷åñêîå ïðåäñòàâëåíèå ãðàôîâ, ÿâëÿÿñü íàãëÿäíûì, òðóäíî
ïîääàåòñÿ ìàòåìàòè÷åñêîé îáðàáîòêå, ïîýòîìó íåîáõîäèìî åãî ôîðìà-
ëèçîâàòü è ïðåäñòàâèòü îïðåäåëåíèå ãðàôà â áîëåå îáùåì àáñòðàêòíîì
âèäå. Õîòÿ ìíîãèå ãðàôû, ïðåäñòàâëÿþùèå ðåàëüíûå îáúåêòû (ïîñëå èõ
èäåàëèçàöèè), ÿâëÿþòñÿ ãåîìåòðè÷åñêèìè ãðàôàìè, ñ òî÷êè çðåíèÿ òåî-
ðèè ãðàôîâ, èõ åäèíñòâåííàÿ ñòðóêòóðíàÿ îñîáåííîñòü ñîñòîèò â òîì,
÷òî ñ êàæäûì ðåáðîì ñâÿçàíû äâå (âîçìîæíî ñîâïàäàþùèå) âåðøèíû.
Òàêèå ðåáðà (äóãè) è âåðøèíû áûëè îïðåäåëåíû âûøå êàê âçàèìíî
èíöèäåíòíûå. Ïîíÿòèå èíöèäåíòíîñòè ðåáåð (äóã) è èõ êîíöåâûõ âåð-
øèí ÿâëÿåòñÿ ôóíäàìåíòàëüíûì â òåîðèè ãðàôîâ, êîòîðàÿ ïîñòðîåíà ñ
ó÷åòîì èìåííî ýòîé îñîáåííîñòè è íå ó÷èòûâàåò ðåàëüíîé ïðèðîäû
âåðøèí è ðåáåð (äóã).
Ââåäåíèå ïîíÿòèÿ àáñòðàêòíîãî ãðàôà ïîçâîëÿåò, âî-ïåðâûõ, èçáà-
âèòüñÿ îò ñëó÷àéíûõ ãåîìåòðè÷åñêèõ õàðàêòåðèñòèê, ñîõðàíèâ íàèáî-
ëåå ñóùåñòâåííûå êîìáèíàòîðíûå ñâîéñòâà ãðàôà, âî-âòîðûõ, ðàñøè-
ðèòü âîçìîæíîñòè ïðèëîæåíèÿ òåîðèè, òàê êàê ìíîãèå ðåàëüíûå ñòðóê-
òóðû èìåþò êîìáèíàòîðíûå ñâîéñòâà, êîòîðûå ïîëåçíî èññëåäîâàòü ñ
ïîìîùüþ ìàòåìàòè÷åñêîãî àïïàðàòà òåîðèè ãðàôîâ. Íàïðèìåð, ïðè ïðî-
åêòèðîâàíèè ñëîæíîãî èçäåëèÿ (òåõíè÷åñêîãî èëè ïðîãðàììíîãî) â âèäå
ãðàôà ìîæíî çàäàòü ñîîòíîøåíèå ìåæäó îòäåëüíûìè ðàáîòàìè, êîòî-
ðûå ñîñòàâëÿþò ñëîæíûå ïðîåêòû.  ýòîì ñëó÷àå âåðøèíû ïðåäñòàâëÿ-
Страницы
- « первая
- ‹ предыдущая
- …
- 7
- 8
- 9
- 10
- 11
- …
- следующая ›
- последняя »
