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

UptoLike

ВУЗ: 

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

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

Рубрика: 

18
îí íå ñîäåðæèò ïîäãðàôà, êîòîðûé ñîñòîèò èç âñåõ åãî âåðøèí è ÿâëÿåòñÿ
ñâÿçíûì.
Åñëè äåðåâî D ÿâëÿåòñÿ ïîäãðàôîì ãðàôà G, òî ðåáðà G, êîòîðûå ïðè-
íàäëåæàò äåðåâó D, íàçûâàþòñÿ âåòâÿìè äåðåâà D, à ðåáðà, íå ïðèíàäëåæà-
ùèå äåðåâó D, õîðäàìè îòíîñèòåëüíî äåðåâà D. Åñëè âñå âåðøèíû G
ïðèíàäëåæàò äåðåâó D, òî ãîâîðÿò, ÷òî äåðåâî ïîêðûâàåò ãðàô G. Ïðè ýòîì
òîëüêî ñâÿçíûå ãðàôû èìåþò ïîêðûâàþùèå äåðåâüÿ è òîëüêî äåðåâüÿ èìå-
þò åäèíñòâåííûå ïîêðûâàþùèå äåðåâüÿ.
Ðèñ. 1.8 èëëþñòðèðóåò îáùåå ñâîéñòâî äåðåâüåâ: êàæäîå äåðåâî ñ n âåð-
øèíàìè èìååò â òî÷íîñòè n  1 ðåáðî. Ïðèìåíèâ ýòîò ðåçóëüòàò ê êàæäîìó
äåðåâó ëåñà, ìîæíî ñêàçàòü: ëåñ èç K äåðåâüåâ, ñîäåðæàùèé n âåðøèí, èìå-
åò â òî÷íîñòè n k ðåáåð.
1.3.8. Ñïåöèàëüíûå êëàññû íåîðèåíòèðîâàííûõ ãðàôîâ
Êëàññèôèêàöèÿ ãðàôîâ çàâèñèò îò ñòðóêòóðíûõ ïðèçíàêîâ, êîòîðûå èñ-
ïîëüçóþòñÿ â êà÷åñòâå îñíîâû äëÿ êëàññèôèêàöèè, íàïðèìåð, ãðàôû ìîæ-
íî ðàçáèòü íà ñâÿçíûå è íåñâÿçíûå. Âîçìîæíû è äðóãèå ðàçíîâèäíîñòè
ãðàôîâ.
Îáûêíîâåííûì íàçûâàåòñÿ ãðàô, êîòîðûé íå ñîäåðæèò ïåòåëü è ïàðàë-
ëåëüíûõ ðåáåð. Âî ìíîãèõ ñëó÷àÿõ äîñòàòî÷íî ðàññìàòðèâàòü òîëüêî îáûê-
íîâåííûå ãðàôû. Íàïðèìåð, ñâÿçíîñòü ãðàôà (èëè îòñóòñòâèå åå) íå ìåíÿ-
åòñÿ, åñëè óäàëèòü âñå ïåòëè è ïàðàëëåëüíûå ðåáðà. Îáûêíîâåííûé ãðàô
ìîæíî òàêæå îïðåäåëèòü êàê ãðàô, íå èìåþùèé öèêëîâ, êîòîðûå ñîäåðæàò
ìåíåå òðåõ ðåáåð, òàê êàê öèêë èç äâóõ ðåáåð îáðàçóåòñÿ ïàðàëëåëüíûìè
ðåáðàìè.
Ïîëíûì íàçûâàåòñÿ ãðàô, â êîòîðîì ëþáûå äâå ðàçëè÷íûå âåðøèíû
ÿâëÿþòñÿ ñìåæíûìè, ò. å. ñîåäèíÿþòñÿ ðåáðîì. Îáû÷íî ýòîò òåðìèí ïðè-
ìåíÿåòñÿ ê îáûêíîâåííûì ãðàôàì, äëÿ êîòîðûõ ñóùåñòâóåò òîëüêî îäèí
ïîëíûé ãðàô ñ ôèêñèðîâàííûì ÷èñëîì âåðøèí. Ñëåäîâàòåëüíî, âûðàæå-
íèå ïîëíûé ãðàô ñ k âåðøèíàìè îäíîçíà÷íî îïðåäåëÿåò ãðàô. Íà ðèñ.
1.9 èçîáðàæåí ïîëíûé ãðàô ñ ÷åòûðüìÿ âåðøèíàìè.
Åñëè ñòåïåíü âåðøèíû δ(v)=k (÷èñëî ðåáåð, èíöèäåíòíûõ âåðøèíå,
âêëþ÷àÿ ïàðàëëåëüíûå ðåáðà è ïåòëè) äëÿ âñåõ âåðøèí ãðàôà, òî ãðàô íà-
çûâàåòñÿ îäíîðîäíûì ãðàôîì ñòåïåíè k èëè ïðîñòî k-îäíîðîäíûì. Çàìå-
òèì, ÷òî îáûêíîâåííûé ïîëíûé ãðàô, èìåþùèé k âåðøèí, ÿâëÿåòñÿ (k1)-
îäíîðîäíûì. Íàïðèìåð, ãðàô íà ðèñ. 1.9 ÿâëÿåòñÿ 3-îäíîðîäíûì.
Ãðàô íàçûâàåòñÿ k-ñâÿçíûì, åñëè ëþáàÿ ïàðà ðàçëè÷íûõ âåðøèí v è
w ñîåäèíåíà, ïî êðàéíåé ìåðå, k öåïÿìè, êîòîðûå íå èìåþò îáùèõ âåð-

Страницы