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

UptoLike

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

Рубрика:

÷èõ âåðøèí. Ýòîò ïðîöåññ ïîèñêà ïðåäïî÷òèòåëüíûõ îáúåêòîâ ïðî-

èëëþñòðèðîâàí íà ðèñ. 4.11.

4.7.7. Âûäåëåíèå ïðåäïî÷òèòåëüíûõ îáúåêòîâ â ÿäðàõ ãðàôà

Ðàññìîòðèì ñïîñîá, êîòîðûé ââîäèò â ïðîöåññ ïîèñêà ÿäåð ãðàôà

îòíîøåíèå ïðåâîñõîäñòâà, ÷òî ïîçâîëÿåò îáúåäèíèòü â îäèí àëãîðèòì

ýòàïû âûäåëåíèÿ êîíòóðîâ â ãðàôå è ïîèñêà ïðåäïî÷òèòåëüíûõ îáúåê-

òîâ â ÿäðàõ ãðàôà ïóòåì ñòÿãèâàíèÿ êîíòóðîâ.

Ïóñòü P

îòíîøåíèå ïðåâîñõîäñòâà : (v,v')∈P

→ (v,v')∈U â ãðàôå

G=(V,U). Â äóãå (v,v') âåðøèíó-êîíåö äóãè (v') áóäåì íàçûâàòü îñòàâëÿ-

åìîé (ïðåâîñõîäÿùåé, ïðåäïî÷òèòåëüíîé), à âåðøèíó-íà÷àëî äóãè  èñ-

êëþ÷àåìîé.

Ïóñòü Ð  ìíîæåñòâî îñòàâëÿåìûõ âåðøèí v', à VP  ìíîæåñòâî

èñêëþ÷àåìûõ âåðøèí v. Ìíîæåñòâî Ð äîëæíî óäîâëåòâîðÿòü ñëåäóþ-

ùèì äâóì ñâîéñòâàì:

1) âíóòðåííåé óñòîé÷èâîñòè:

∀ v∈P è ∀ v'∈P → (v, v')∉U, ò. å. íèêàêîé îáúåêò èç ìíîæåñòâà Ð íå

ïðåâîñõîäèòñÿ äðóãèì îáúåêòîì èç Ð;

2) âíåøíåé óñòîé÷èâîñòè :

∀ v∈VP ∃ v'∈P → (v,v')∈U, ò. å. äëÿ ëþáîé èç èñêëþ÷àåìûõ âåðøèí

v ñóùåñòâóåò ñðåäè îñòàâëÿåìûõ ïî êðàéíåé ìåðå îäíà âåðøèíà v', êî-

òîðàÿ ïðåâîñõîäèò v.

Ðèñ. 4.11. Ïîèñê ïðåäïî÷òèòåëüíûõ îáúåêòîâ:

à  âûäåëåíèå êëàññîâ ýêâèâàëåíòíîñòåé âåðøèí;

á  âûäåëåíèå ÿäåð ãðàôà



à á

