Элементы теории графов. Домнин Л.Н. - 120 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

a v
P
|P |=n a∈Γ(v)
|P |=n a/∈Γ(v)
|P |<n Γ(v)⊆P |P |−1
u=P red(v),
v u
P.
u
Γ(u),
P, u.
Γ(u)−P − u
w=P red(u),
u P
Γ(u)−P.
a.
Γ(a).
G
íî, ÷òî ýòîò ïðîöåññ êîíå÷åí â ñèëó óêàçàííîãî îãðàíè÷åíèÿ
è êîíå÷íîãî ÷èñëà âåðøèí ãðàôà è çàâåðøàåòñÿ, êîãäà òàêîå
íàðàùèâàíèå ñòàíîâèòñÿ íåâîçìîæíûì. Åñëè ê ìîìåíòó îñòà-
íîâà öåïü ñîäåðæèò âñå âåðøèíû ãðàôà, ò. å. ÿâëÿåòñÿ ãàìèëü-
òîíîâîé, îñòàåòñÿ âûÿñíèòü, åñòü ëè äóãà, ñîåäèíÿþùàÿ êîíåö
öåïè ñ åå íà÷àëîì.  ïðîòèâíîì ñëó÷àå èìååì ïðîñòóþ öåïü,
êîòîðàÿ íå ìîæåò áûòü äàæå ÷àñòüþ ãàìèëüòîíîâà öèêëà.
   Ïóñòü a  íà÷àëüíàÿ, v  êîíå÷íàÿ âåðøèíû ñôîðìèðî-
âàííîé öåïè, à P  ìíîæåñòâî âåðøèí, âîøåäøèõ â öåïü. Òî-
ãäà âàðèàíòû çàâåðøåíèÿ îïèñàííîãî ïðîöåññà âûãëÿäÿò òàê:
   à) |P |=n è a∈Γ(v)  íàéäåí ãàìèëüòîíîâ öèêë;
   á) |P |=n è a∈Γ(v)
                 /      íàéäåíà ãàìèëüòîíîâà öåïü;
   â) |P |

Страницы