Эвристический алгоритм для поиска наибольшего независимого множества

Розроблено евристичний алгоритм для розв’язання задачі пошуку найбільшої незалежної множини вершин в неорієнтованому графі. Для цього використано підхід скінченних частково впорядкованих множин, зокрема техніка розбиття такої множини на мінімальне число ланцюгів. Побудовано спеціальний орграф, i на...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2012
Автор:	Плотников, А.Д.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Назва видання:	Кибернетика и системный анализ
Теми:	Кибернетика
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/84142
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Эвристический алгоритм для поиска наибольшего независимого множества / А.Д. Плотников // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 41-48. — Бібліогр.: 6 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-84142
record_format	dspace
spelling	irk-123456789-841422015-07-04T03:01:50Z Эвристический алгоритм для поиска наибольшего независимого множества Плотников, А.Д. Кибернетика Розроблено евристичний алгоритм для розв’язання задачі пошуку найбільшої незалежної множини вершин в неорієнтованому графі. Для цього використано підхід скінченних частково впорядкованих множин, зокрема техніка розбиття такої множини на мінімальне число ланцюгів. Побудовано спеціальний орграф, i на ocнові гіпотези про його властивості запропоновано розв’язувальний алгоритм. Наведено дані експериментів на відомих прикладах. A heuristic algorithm is developed for finding the maximum independent set of vertices in an undirected graph. To this end, the technique of finite partially ordered sets is used, in particular, the technique of partitioning such a set into the minimum number of chains. A special digraph is constructed and a solution algorithm is proposed on the basis of the hypothesis about its properties. Some experimental data are presented for well-known examples 2012 Article Эвристический алгоритм для поиска наибольшего независимого множества / А.Д. Плотников // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 41-48. — Бібліогр.: 6 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84142 519.14 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Кибернетика Кибернетика
spellingShingle	Кибернетика Кибернетика Плотников, А.Д. Эвристический алгоритм для поиска наибольшего независимого множества Кибернетика и системный анализ
description	Розроблено евристичний алгоритм для розв’язання задачі пошуку найбільшої незалежної множини вершин в неорієнтованому графі. Для цього використано підхід скінченних частково впорядкованих множин, зокрема техніка розбиття такої множини на мінімальне число ланцюгів. Побудовано спеціальний орграф, i на ocнові гіпотези про його властивості запропоновано розв’язувальний алгоритм. Наведено дані експериментів на відомих прикладах.
format	Article
author	Плотников, А.Д.
author_facet	Плотников, А.Д.
author_sort	Плотников, А.Д.
title	Эвристический алгоритм для поиска наибольшего независимого множества
title_short	Эвристический алгоритм для поиска наибольшего независимого множества
title_full	Эвристический алгоритм для поиска наибольшего независимого множества
title_fullStr	Эвристический алгоритм для поиска наибольшего независимого множества
title_full_unstemmed	Эвристический алгоритм для поиска наибольшего независимого множества
title_sort	эвристический алгоритм для поиска наибольшего независимого множества
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2012
topic_facet	Кибернетика
url	http://dspace.nbuv.gov.ua/handle/123456789/84142
citation_txt	Эвристический алгоритм для поиска наибольшего независимого множества / А.Д. Плотников // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 41-48. — Бібліогр.: 6 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT plotnikovad évrističeskijalgoritmdlâpoiskanaibolʹšegonezavisimogomnožestva
first_indexed	2025-07-06T11:05:47Z
last_indexed	2025-07-06T11:05:47Z
_version_	1836895382525706240
fulltext	ÓÄÊ 519.14 À.Ä. ÏËÎÒÍÈÊÎÂ ÝÂÐÈÑÒÈ×ÅÑÊÈÉ ÀËÃÎÐÈÒÌ ÄËß ÏÎÈÑÊÀ ÍÀÈÁÎËÜØÅÃÎ ÍÅÇÀÂÈÑÈÌÎÃÎ ÌÍÎÆÅÑÒÂÀ ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Ìíîæåñòâî âñåõ íåîðèåíòèðîâàííûõ n-âåðøèííûõ ãðàôîâ áåç ïåòåëü è êðàò- íûõ ðåáåð îáîçíà÷èì Ln . Ïóñòü èìååòñÿ ãðàô G V Ln� �( , )� , ãäå V — ìíî- æåñòâî ãðàôîâûõ âåðøèí, � — îòîáðàæåíèå V â V . Ëþáîé ïîäãðàô Q V1 1 1� ( , )� ãðàôà G íàçûâàåòñÿ êëèêîé, ïîðîæäåííîé V1, åñëè �1 1( ) \ { }v V v� äëÿ âñåõ v V� 1. Â ÷àñòíîì ñëó÷àå, êîãäà Card( )V1 1� , îäíîâåðøèííûé ïîäãðàô Q V1 1 1� ( , )� íàçûâàåòñÿ îäíîâåðøèííîé êëèêîé. Êëèêà Q1 íàçûâàåòñÿ ìàêñèìàëüíîé, åñëè ê íåé íåëüçÿ ïðèñîåäèíèòü íèêàêîé âåð- øèíû v V� òàê, ÷òîáû íîâîå ìíîæåñòâî âåðøèí òàêæå îáðàçîâûâàëî êëèêó ãðàôà G . Êëèêà �Q íàçûâàåòñÿ íàèáîëüøåé, åñëè ãðàô G íå èìååò êëèêè áîëüøåãî ðàçìåðà, ÷åì �Q . Ïóñòü òðåáóåòñÿ íàéòè íàèáîëüøóþ êëèêó ãðàôà G . Ñôîðìóëèðîâàíà èçâåñò- íàÿ çàäà÷à ïîèñêà íàèáîëüøåé êëèêè. Ìíîæåñòâî âåðøèí U V� ãðàôà G íàçûâàåòñÿ íåçàâèñèìûì, åñëè U U� � ��( ) . Íåçàâèñèìîå ìíîæåñòâî U ãðàôîâûõ âåðøèí íàçûâàåòñÿ ìàêñè- ìàëüíûì (ÌÍÌ), åñëè U U V� ��( ) , è ÌÍÌ U íàçûâàåòñÿ íàèáîëüøèì (ÍÁÍÌ), åñëè Card (U ) Card (U ) äëÿ ëþáîãî ÌÍÌ U ãðàôà G . Ïóñòü òðåáóåòñÿ íàéòè ÍÁÍÌ ãðàôà G. Ñíîâà ñôîðìóëèðîâàíà èçâåñòíàÿ çà- äà÷à ïîèñêà íàèáîëüøåãî íåçàâèñèìîãî ìíîæåñòâà âåðøèí ãðàôà G. Îáå ñôîð- ìóëèðîâàííûå âûøå çàäà÷è ÿâëÿþòñÿ NP-ïîëíûìè [1, 2]. Îíè òåñíî ñâÿçàíû: ðå- øåíèå îäíîé èç íèõ âëå÷åò ðåøåíèå äðóãîé. Ãðàô G íàçûâàþò äîïîëíèòåëüíûì ê ãðàôó G, åñëè îí èìååò òàêîå æå ìíî- æåñòâî âåðøèí, ÷òî è ãðàô G, à ðåáðà ñîåäèíÿþò äâå âåðøèíû ãðàôà G òîãäà è òîëüêî òîãäà, êîãäà ýòè âåðøèíû íåñìåæíûå â G. Íåòðóäíî âèäåòü, ÷òî âñÿêàÿ êëèêà ãðàôà G ñîîòâåòñòâóåò íåçàâèñèìîìó ìíîæåñòâó âåðøèí äîïîëíèòåëüíîãî ãðàôà G è íàîáîðîò. Ïîýòîìó íàõîæäåíèå ÍÁÍÌ âåðøèí â îäíîì ãðàôå ýêâèâàëåíòíî íàõîæäåíèþ íàèáîëüøåé êëèêè â åãî äîïîëíèòåëüíîì ãðàôå è íàîáîðîò. Â íàñòîÿùåé ñòàòüå íà îñíîâå ãèïîòåçû î ñâîéñòâàõ ñïåöèàëüíîãî îðãðàôà ðàçðàáîòàí ïîëèíîìèàëüíî-âðåìåííîé ðåøàþùèé àëãîðèòì äëÿ íàõîæäåíèÿ ÍÁÍÌ âåðøèí ãðàôà. ÎÑÍÎÂÍÛÅ ÎÏÐÅÄÅËÅÍÈß Ïóñòü èìååòñÿ ãðàô G V Ln� �( , )� . Ðàçîáüåì ìíîæåñòâî ãðàôîâûõ âåðøèí V íà ïîäìíîæåñòâà V V V m0 1, � (1) òàê, ÷òî ïîäìíîæåñòâî V k , k m� 0 1 2, , , ... , , åñòü ÌÍÌ ïîäãðàôà Gk � ( \ (V V 0 � � � � � � ��V V V Vk k k m k 1 1 � �), ) ( , )� � . ßñíî, ÷òî G V V Gm 0 0 0� � � �( , )� � . Ïî äàííîìó íåîðèåíòèðîâàííîìó ãðàôó G è ðàçáèåíèþ (1) ìîæíî ïîñòðîèòü àöèêëè÷åñêèé îðãðàô � � G V V( ) ( , )0 � � ñëåäóþùèì îáðàçîì. Åñëè ðåáðî èç G ñâÿçû- âàåò âåðøèíó v Vi k � 1 ñ âåðøèíîé v Vj k � 2 , òî îíî çàìåíÿåòñÿ äóãîé ( , )v vi j ïðè k k1 2� . Â ýòîì ñëó÷àå âåðøèíà vi íàçûâàåòñÿ íà÷àëîì äóãè ( , )v vi j , à âåðøèíà ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 41 © À.Ä. Ïëîòíèêîâ, 2012 v j — åå êîíöîì; ïîäìíîæåñòâî âåðøèí V k , k ò� 0 1 2, , , ..., , íàçûâàåòñÿ k-ì ñëîåì âåðøèí îðãðàôà, à ìíîæåñòâîV 0 — èíèöèèðóþùèì. Ïðèìåð ïîñòðîåíèÿ îðãðàôà ïî äàííî- ìó íåîðèåíòèðîâàííîìó ãðàôó ïðåäñòàâëåí íà ðèñ. 1. Ïîñëåäîâàòåëüíî â èñõîäíîì ãðà- ôå (ñì. ðèñ. 1, a) âûáðàíû ñëåäóþùèå ÌÍÌ: V v v v0 3 7� { 1, , } , V v v v1 2 5 8� { }, , è V v v2 4 6� { }, . Îáîçíà÷èì D G( ) ìíîæåñòâî ðàçëè÷íûõ àöèêëè÷åñêèõ îðãðàôîâ, ñîîòâåòñòâó- þùèõ ãðàôó G Ln� , êàæäûé èç êîòîðûõ ïîðîæäåí íåêîòîðîé îðèåíòàöèåé åãî ðå- áåð. Äàëåå áóäåì ðàññìàòðèâàòü òîëüêî îðãðàôû èç D G( ) . Ìàêñèìàëüíàÿ äëèíà �( )v îðèåíòèðîâàííîé öåïè, ñîåäèíÿþùåé âåðøèíó v V� è èíèöèèðóþùåå ìíîæåñòâî V 0 , íàçûâàåòñÿ ðàíãîì v. ßñíî, ÷òî åñëè v V� 0 , òî �( )v = 0. Ïî ïîñòðîåíèþ êàæäàÿ âåðøèíà k-ãî ñëîÿ V k îðãðàôà ñîäåð- æèò ãðàôîâûå âåðøèíû, èìåþùèå îäèí è òîò æå ðàíã �( )v = k. ×òîáû èñïîëüçîâàòü ïîäõîä, ðàçðàáîòàííûé äëÿ ÷àñòè÷íî óïîðÿäî÷åííûõ ìíîæåñòâ, êàæäîìó îðãðàôó � G V D G( ) ( )0 � ñòàâèòñÿ â ñîîòâåòñòâèå ãðàô òðàíçè- òèâíîãî çàìûêàíèÿ (ÃÒÇ) � � G V Vt t( ) ( , )0 � � [3, 4]. Òàê êàê îðãðàô � G V( )0 àöèêëè- ÷åñêèé è íå èìååò ïåòåëü, åãî òðàíçèòèâíîå çàìûêàíèå � G Vt ( )0 åñòü ãðàô ñòðîãî- ãî ÷àñòè÷íîãî ïîðÿäêà ( , )V . Äàëåå íå áóäåì ðàçëè÷àòü ãðàô òðàíçèòèâíîãî çà- ìûêàíèÿ � G Vt ( )0 è ÷àñòè÷íî óïîðÿäî÷åííîå ìíîæåñòâî ( , )V . Ïîýòîìó ðàññìîòðèì, íàïðèìåð, àíòèöåïè ãðàôà � G Vt ( )0 . Ñóùåñòâóåò ýôôåêòèâíûé àëãîðèòì äëÿ ïîñòðîåíèÿ ÃÒÇ. Âðåìÿ ðàáîòû òà- êîãî àëãîðèòìà ðàâíî O n( )3 [3, 5]. Äóãó ( , )v vi j ãðàôà � G Vt ( )0 áóäåì íàçûâàòü ñóùåñòâåííîé, åñëè ñóùåñòâóåò äóãà ( , )v vi j îðãðàôà � G V( )0 . Â ïðîòèâíîì ñëó÷àå äóãó ( , )v vi j áóäåì íàçûâàòü ôèêòèâíîé. Îáîçíà÷èì v vi j ñóùåñòâåííóþ äóãó, à v vi j ôèêòèâíóþ äóãó. Î÷åâèäíî, ÷òî âñÿêàÿ ôèêòèâíàÿ äóãà ãðàôà � G Vt ( )0 îïðåäåëÿåò äâå íåçàâèñèìûå âåðøèíû îðãðàôà � G V( )0 . Ïóñòü èìååòñÿ ÷àñòè÷íî óïîðÿäî÷åííîå ìíîæåñòâî ( , )À . Åñëè a b èëè b a , òî ýëåìåíòû à è b èç A íàçûâàþòñÿ ñðàâíèìûìè. Åñëè a b è b a íå âû- ïîëíÿþòñÿ, òî òàêàÿ ïàðà ýëåìåíòîâ íàçûâàåòñÿ íåñðàâíèìîé. Åñëè A A1 � è êàæäàÿ ïàðà ýëåìåíòîâ èç A1 ñðàâíèìà, òî ïðèíÿòî ñ÷èòàòü, ÷òî A1 îïðåäåëÿåò öåïü èç ( , )À . Åñëè A A1 � è êàæäàÿ ïàðà ýëåìåíòîâ èç A1 íåñðàâíèìà, òî ïîëà- ãàåì, ÷òî A1 åñòü àíòèöåïü èç ( , )À . Àíòèöåïü A1 íàçûâàåòñÿ íàèáîëüøåé â ( , )À , åñëè Card Card( ) ( )A A1 äëÿ ëþáîé àíòèöåïè A A � â ( , )À . ×àñòè÷íî óïîðÿäî÷åííîå ìíîæåñòâî ( , )À ðàçáèòî íà öåïè A Am1, ..., , åñëè êàæäîå Ai (Ai � � , i m�1 2, , ..., ) åñòü öåïü, A Ai i m � � 1 � , è A Ai j� � �, êîãäà i j� ( , { , ..., }i j m� 1 ). Ðàçáèåíèå ìíîæåñòâà ( , )À íà öåïè íàçûâàåòñÿ íàèìåíüøèì, åñëè îíî èìå- åò íàèìåíüøåå ÷èñëî ýëåìåíòîâ m ïî ñðàâíåíèþ ñ äðóãèìè ðàçáèåíèÿìè ( , )À íà öåïè. Òàêîå ðàçáèåíèå òàêæå íàçûâàåòñÿ ìèíèìàëüíûì öåïíûì ðàçáèåíèåì (ÌÖÐ) ìíîæåñòâà ( , )À . 42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 Ðèñ. 1. Ïîñòðîåíèå îðãðàôà Ïîñêîëüêó � G Vt ( )0 — ãðàô ñòðîãîãî ÷àñòè÷íîãî ïîðÿäêà, ìîæíî íàéòè ÌÖÐ P S S p� { , ..., }1 . Â îáùåì ñëó÷àå ýòî ðàçáèåíèå íåîäíîçíà÷íî. Íà ðèñ. 2 ïðåäñòàâëåí îðãðàô, â êîòîðîì ïîêàçàíû ðàçëè÷íûå ÌÖÐ ñîîòâåò- ñòâóþùåãî ÃÒÇ. Äóãè îðãðàôà, ïðèíàäëåæàùèå öåïÿì èç ÌÖÐ, âûäåëåíû æèðíû- ìè ëèíèÿìè. Çäåñü è äàëåå ïîëàãàåì, ÷òî äóãè îðãðàôà íàïðàâëåíû ñíèçó ââåðõ. Ïóñòü V S q( ) , q p� �1 2, , , , — ìíîæåñòâî âåð- øèí, ïðèíàäëåæàùèõ öåïè S q ÌÖÐ P. Åñëè âåðøè- íû v v V Si j q, ( )� êîíå÷íûå äëÿ ôèêòèâíîé äóãè v vi j , ïðèíàäëåæàò îäíîé è òîé æå öåïè S q , òî âåðøèíà v j íàçûâàåòñÿ îòìå÷åííîé. Ìíîæåñòâî âñåõ îòìå÷åííûõ âåðøèí èç � G Vt ( )0 îïðåäåëÿåòñÿ íàéäåííûì ÌÖÐ P (îáîçíà÷èì åãî B P( )) è áóäåò ðàçëè÷íûì äëÿ ðàçëè÷íûõ ÌÖÐ. Íàïðèìåð, äëÿ ÌÖÐ P1( ñì. ðèñ. 2, a) èìååì B P v v( ) { , }1 5 6� , à äëÿ ÌÖÐ P2 (ñì. ðèñ. 2, á) èìååì B P( )2 � � . Ëåììà 1. Ïóñòü � G V( )0 — îðãðàô è � G Vt ( )0 — åãî ãðàô òðàíçèòèâíîãî çàìû- êàíèÿ. Åñëè B P( ) � � , ãäå P åñòü ÌÖÐ ãðàôà � G Vt ( )0 , òî íàèáîëüøàÿ àíòèöåïü �U ÿâëÿåòñÿ ÍÁÍÌ ãðàôà G Ln� è ÌÖÐ îïðåäåëÿåò íàèìåíüøåå êëèêîâîå ðàçáèåíèå G. Åñëè óñëîâèÿ ëåììû 1 âûïîëíÿþòñÿ, òî êàæäàÿ öåïü S Pq � åñòü êëèêà îðãðàôà � G V( )0 . Ïîýòîìó ÌÖÐ P — íàèìåíüøåå êëèêîâîå ðàçáèåíèå. Ñ äðóãîé ñòîðîíû, âåðøèíû íàèáîëüøåé àíòèöåïè �U ãðàôà � G Vt ( )0 ïðèíàä- ëåæàò ðàçëè÷íûì êëèêàì, ò.å. ÷èñëî âåðøèí â ÍÁÍÌ ðàâíî ÷èñëó âåðøèí âî ìíîæåñòâå �U . � Çàìåòèì, ÷òî ëåììà 1 ìîæåò âûïîëíÿòüñÿ, åñëè îðãðàô � G V( )0 íå ÿâëÿåòñÿ òðàíçèòèâíî îðèåíòèðóåìûì. Î÷åâèäíî, ÷òî ëþáàÿ àíòèöåïüU V� ãðàôà òðàíçèòèâíîãî çàìûêàíèÿ � G Vt ( )0 îïðåäåëÿåò ìíîæåñòâî íåçàâèñèìûõ âåðøèí îðãðàôà � G V( )0 è ìíîæåñòâî íåçàâè- ñèìûõ âåðøèí U V� îðãðàôà � G V( )0 îïðåäåëÿåò àíòèöåïü ãðàôà � G Vt ( )0 , åñëè è òîëüêî åñëè íèêàêèå äâå âåðøèíû èç U íå ïðèíàäëåæàò îäíîé è òîé æå îðèåíòè- ðîâàííîé öåïè � G V( )0 . Ìíîæåñòâî íåçàâèñèìûõ âåðøèí U V� íàçûâàåòñÿ ðàñïîçíàâàåìûì îðãðà- ôîì � G V( )0 , åñëè îíî ñîîòâåòñòâóåò àíòèöåïè ãðàôà � G Vt ( )0 . ÍÀÑÛÙÅÍÍÛÉ ÎÐÃÐÀÔ Ïóñòü èìååòñÿ àöèêëè÷åñêèé îðãðàô � � G V V( ) ( , )0 � � , W V� — íåêîòîðîå íåçà- âèñèìîå ìíîæåñòâî âåðøèí. Äëÿ îðãðàôà � G V( )0 îïðåäåëèì óíàðíóþ îïåðà- öèþ ñå÷åíèÿ �W G V( ( )) � 0 , êîòîðàÿ ñîñòîèò â ïåðåîðèåíòàöèè âñåõ äóã èç � G V( )0 , âõîäÿùèõ â âåðøèíû ìíîæåñòâà W. Ðåçóëüòàòîì ýòîé îïåðàöèè ÿâëÿ- åòñÿ òàêæå îðãðàô � G Y( )0 , ãäå Y V W W0 0 1� ��( \ ( )) � � . Çäåñü � � �1 — îòîáðà- æåíèå, îáðàòíîå � � . Òåîðåìà 1. Ïóñòü èìååòñÿ îðãðàô � G V D G( ) ( )0 � è W V� — íåêîòîðîå åãî íåçàâèñèìîå ìíîæåñòâî âåðøèí. Òîãäà îðãðàô � G Y( )0 = �W G V( ( )) � 0 ÿâëÿåòñÿ òàê- æå àöèêëè÷åñêèì, ò.å. � G Y D G( ) ( )0 � . Â ñàìîì äåëå, òàê êàê îðãðàô � � G V V( ) ( , )0 � � àöèêëè÷åñêèé, ëþáàÿ åãî ÷àñòü — òàêæå àöèêëè÷åñêèé îðãðàô. Òàêèì îáðàçîì, îðèåíòèðîâàííûé ïîäãðàô� � G V W1 1� ( \ , )� àöèêëè÷åñêèé. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 43 Ðèñ. 2. Ðàçëè÷íûå ÌÖÐ ãðàôà òðàíçèòèâíîãî çàìûêàíèÿ Î÷åâèäíî, ÷òî � � G G Y1 0� ( ) . Ïðèñîåäèíèì íåçàâèñèìîå ìíîæåñòâî âåðøèí W ê ïîäãðàôó � G1. Ñîåäèíèì êàæäóþ âåðøèíó v W� ñ âåðøèíîé y èç � G1 äóãîé ( , )v y , åñëè è òîëüêî åñëè ñóùåñòâóåò äóãà ( , )y v îðãðàôà � G V( )0 . Î÷åâèäíî, ÷òî ïîëó÷åííûé â ðåçóëüòàòå îðãðàô � G Y( )0 áóäåò òàêæå àöèêëè÷åñêèì. Íàêîíåö, ïîëó÷èì � G Y D G( ) ( )0 � , òàê êàê ëþáàÿ ïåðåîðèåíòàöèÿ äóã îðãðà- ôà � G V( )0 íå èçìåíÿåò íåçàâèñèìîñòè åãî âåðøèí. � Ïóñòü èìååòñÿ îðãðàô � G V D G( ) ( )0 � è åãî ÃÒÇ � G Vt ( )0 . Íàéäåì ÌÖÐ P ýòîãî ãðàôà ñ îäíîâðåìåííûì íàõîæäåíèåì íàèáîëüøåé àíòèöåïè �U , êàê ýòî îïèñàíî â [6]. Â îáùåì ñëó÷àå ìîæåì íàéòè íåñêîëüêî ðàçëè÷íûõ íàèáîëüøèõ àíòèöåïåé. Ïðåäïîëîæèì, ÷òî àíòèöåïü �U 1 ïðåäøåñòâóåò àíòèöåïè �U 2 â ãðàôå � G Vt ( )0 è îáîçíà÷èì � �U U1 2� , åñëè äëÿ âñåõ âåðøèí v U U� � \ � 1 2 èìååòñÿ âåðøèíà y U U� � \ � 2 1 òàêàÿ, ÷òî v y� . Ïî ìåòîäîëîãèè Ôîðäà è Ôàëêåðñîíà, èçëîæåííîé â [6], â ÃÒÇ � G Vt ( )0 ìîæ- íî íàéòè íàèáîëüøóþ àíòèöåïü �U òàêóþ, äëÿ êîòîðîé ëþáàÿ äðóãàÿ íàèáîëüøàÿ àíòèöåïü �U 1 ÿâëÿåòñÿ ïðåäøåñòâóþùåé, ò.å. � �U U1 2� äëÿ ëþáîé àíòèöåïè �U 1 ãðàôà � G Vt ( )0 . Àíòèöåïü �U ãðàôà � G Vt ( )0 áóäåì íàçûâàòü ãåíåðàëüíîé. Â äîïîëíåíèå ê ãåíåðàëüíîé àíòèöåïè ìîæíî íàéòè äðóãèå íàèáîëüøèå àíòèöåïè ÃÒÇ � G Vt ( )0 , åñëè îíè ñóùåñòâóþò. Òàê, äëÿ âåðøèíû v V� ãðàôà � G Vt ( )0 ìîæíî íàéòè íàèáîëüøóþ àíòèöåïü � ( )U v òàêóþ, ÷òî v U v� � ( ) . ×òîáû íàéòè àíòèöåïü � ( )U v , äîñòàòî÷íî â ìàòðèöå ñìåæíîñòè ÃÒÇ � G Vt ( )0 , â êîòîðîé íàéäåíî íàèáîëüøåå ÷èñëî åäèíèö â äîïóñòèìûõ êëåòêàõ (è ðàññòàâëåíû ìåòêè ñîãëàñíî àëãîðèòìó Ôîðäà–Ôàëêåðñîíà), ê ñóùåñòâóþùèì ìåòêàì äîáàâèòü ìåòêó � äëÿ ñòðîêè, ñîîòâåòñòâóþùåé âåðøèíå v, è âûïîëíèòü öèêë ðàññòàíîâ- êè ìåòîê. Â ýòîì ñëó÷àå íà ïåðâîì øàãå ýòîãî öèêëà îòìå÷àþòñÿ âñå ñòîëáöû, êîòîðûå â ñòðîêå, ñîîòâåòñòâóþùåé âåðøèíå v, ñîäåðæàò åäèíèöû (â òîì ÷èñëå è âûáðàííóþ åäèíèöó). ßñíî, ÷òî àíòèöåïü � ( )U v áóäåò ãåíåðàëüíîé äëÿ âåðøè- íû v , ò.å. ëþáàÿ äðóãàÿ àíòèöåïü, ñîäåðæàùàÿ âåðøèíó v, áóäåò ïðåäøåñòâî- âàòü ýòîé àíòèöåïè. Çàìåòèì, ÷òî â îáùåì ñëó÷àå íå äëÿ âñÿêîé âåðøèíû v V� ãðàôà � G Vt ( )0 ñó- ùåñòâóåò íàèáîëüøàÿ àíòèöåïü � ( )U v . Íàïðèìåð, ïóñòü îðãðàô, ïðåäñòàâëåííûé íà ðèñ. 3, çàäàåò ÷àñòè÷íî óïîðÿäî÷åííîå ìíîæåñòâî (êàê óêàçàíî âûøå). Ëåãêî âèäåòü, ÷òî âåðøèíû a a a3 4 5, , îáðàçóþò íàèáîëüøóþ àíòèöåïü è â íåì íå ñó- ùåñòâóåò íàèáîëüøèõ àíòèöåïåé � ( )U a1 è � ( )U a2 . Îðãðàô � G V( )0 áóäåì íàçûâàòü íàñûùåííûì îòíîñèòåëüíî èíèöèèðóþùåãî ìíîæåñòâà V 0 , åñëè â åãî ãðàôå � G Vt ( )0 ëþáàÿ ñóùåñòâóþùàÿ íàèáîëüøàÿ àíòè- öåïü � ( )U v V� åñòü ÌÍÌ îðãðàôà � G V( )0 è óäîâëåòâîðÿåò ñîîòíîøåíèþ Card Card( � ( )) ( )U v V� 0 . Îðèåíòèðîâàííûé ïîäãðàô � G V k( ), k m� �0 1 1, , ..., , îðãðàôà � G V( )0 áóäåì íàçûâàòü íàñûùåííûì îòíîñèòåëüíî èíèöèèðóþùåãî ìíîæåñòâà V k , åñëè â ÃÒÇ � G Vt k( ) ëþáàÿ ñóùåñòâóþùàÿ íàèáîëüøàÿ àíòèöåïü � ( )U v V� åñòü ÌÍÌ ïîäãðà- ôà � G V k( ) è óäîâëåòâîðÿåò ñîîòíîøåíèþ Card Card( � ( )) ( )U v V k� . Î÷åâèäíî, ïîäãðàô � G V m( ) íå èìååò äóã è ïîýòîìó âñåãäà ÿâëÿåòñÿ íàñûùåííûì îòíîñè- òåëüíî èíèöèèðóþùåãî ìíîæåñòâà V m . 44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 Îðãðàô � G V( )0 íàçûâàåòñÿ âåðøèí- íî-íàñûùåííûì (ÂÍ-îðãðàôîì), åñëè ëþáîé îðèåíòèðîâàííûé ïîäãðàô � G V k( ) , k m� 0 1, , ..., , ïîðîæäåííûé ñëî- åì V k , ÿâëÿåòñÿ íàñûùåííûì îòíîñè- òåëüíî èíèöèèðóþùåãî ìíîæåñòâà V k . Çàìåòèì, ÷òî îðãðàô, ïðåäñòàâëåí- íûé íà ðèñ. 3, íå ÿâëÿåòñÿ âåðøèííî-íà- ñûùåííûì. Â òî æå âðåìÿ îðãðàô, ïðåä- ñòàâëåííûé íà ðèñ. 4, âåðøèííî-íàñû- ùåííûé è èìååò ÍÁÍÌ {v v v v1 2 7 8, , , }. Ïóñòü èìååòñÿ íåêîòîðûé îðãðàô � G V( )0 . ×òîáû ïîñòðîèòü ÂÍ-îðãðàô, èñïîëüçóåì ñëåäóþùèé àëãîðèòì. Âõîä àëãîðèòìà — íåêîòîðûé îðãðàô � G V( )0 , à âûõîä — îðãðàô � G Y( )0 , íàñûùåí- íûé îòíîñèòåëüíî êàæäîãî ñëîÿ Y k mk , , , ..., ,� 0 1 è ÃÒÇ � G Yt ( )0 . Àëãîðèòì ïîñòðîåíèÿ ÂÍ-îðãðàôà Øàã 1. Ïîëîæèòü k :=0 è �:=false. Øàã 2. Íàéòè ÃÒÇ � G Vt k( ) . Øàã 3. Ïîñòðîèòü ÌÖÐ ãðàôà � G Vt k( ). Øàã 4. Íàéòè ìàêñèìàëüíóþ àíòèöåïü ãðàôà � G Vt k( ) äëÿ êàæäîé âåðøèíû v V Vk m� � �� . Øàã 5. Ïðîâåðèòü, ÿâëÿåòñÿ ëè êàæäàÿ èç íàéäåííûõ íàèáîëüøèõ àíòèöå- ïåé � ( )U v ãðàôà � G Vt k( ) ÌÍÌ îðãðàôà � G V k( ) è Card Card( � ( )) ( )U v V k� . Åñëè ýòî òàê, çàêîí÷èòü ïîñòðîåíèå îðãðàôà � G V k( ) , íàñûùåííîãî îòíîñèòåëüíî èíèöèè- ðóþùåãî ìíîæåñòâà V k . Ïåðåéòè ê øàãó 6. Â ïðîòèâíîì ñëó÷àå, åñëè íåîáõîäè- ìî, äîïîëíèòü íàéäåííóþ àíòèöåïü � ( )U v äî ÌÍÌ W è ïîñòðîèòü íîâûé àöèêëè- ÷åñêèé îðãðàô � G V k( ) îïåðàöèåé ñå÷åíèÿ �W G V( ( )) � 0 , ïîëîæèòü �: = true è ïî- ñòðîèòü íîâûé îðãðàô � G V( )0 . Âåðíóòüñÿ ê øàãó 2. Øàã 6. Âû÷èñëèòü k k:� �1 . Åñëè k m� , òî âûäåëèòü ÃÒÇ � G Vt k( ) èç � G Vt k( )�1 , ñîõðàíÿÿ âñå öåïè ÌÖÐ ãðàôà � G Vt k( )�1 , êîòîðûå èíöèäåíòíû âåðøè- íàì íîâîãî ãðàôà. Ïåðåéòè ê øàãó 4. Åñëè k m� è � = true, òî ïåðåéòè ê øàãó 1. Åñëè k m� è � = false, òî ïåðåéòè ê øàãó 7. Øàã 7. Çàêîí÷èòü âû÷èñëåíèÿ. ÂÍ-îðãðàô ïîñòðîåí. Ïîêàæåì, ÷òî äàííûé àëãîðèòì äåéñòâèòåëüíî ñòðîèò ÂÍ-îðãðàô. Òåîðåìà 2. Ïóñòü � G V( )0 — îðãðàô, ïîñòðîåííûé àëãîðèòìîì ÂÍ-îðãðàôà, � � G V Yk k( ) ( , )� � , k m� 0 1, , ..., , — îðèåíòèðîâàííûé ïîäãðàô, ïîðîæäåííûé ñëîåì V k îðãðàôà � G V( )0 . Òîãäà äëÿ ëþáîé àíòèöåïèU Y Vk k� \ ãðàôà � � G V Yt k k t( ) ( , )� � âûïîëíÿåòñÿ ñëåäóþùåå ñîîòíîøåíèå: Card Card( ) ( ).V U Uk t� � � � 1 Ïðåäïîëîæèì, ÷òî â îðèåíòèðîâàííîì ïîäãðàôå � G V k( ) áóäåò íàéäåíà àíòè- öåïüU Y Vk k� \ ãðàôà � � G V Yt k k t( ) ( , )� � òàêàÿ, ÷òî Card Card( ) ( )V U Uk t� �� 1 . Ïîñòðîèì ìíîæåñòâî U V U Uk t * ( \ ( ))� �� 1 . ßñíî, ÷òî ýòî ìíîæåñòâî íåçàâè- ñèìîå â îðèåíòèðîâàííîì ïîäãðàôå � G V k( ) è Card Card( ) ( )U V k . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 45 Ðèñ. 4. Ïðèìåð ïîñòðîåíèÿ âåð- øèííî-íàñûùåííîãî îðãðàôà Ðèñ. 3. Óïîðÿäî÷åííîå ìíîæåñòâî: îðôãðàô (à); ìàòðèöû ñìåæíîñòè (á, â) Ïîñêîëüêó ìíîæåñòâî V k åñòü àíòèöåïü ÃÒÇ � � G V Yt k k t( ) ( , )� � , ìíîæåñòâî V U Vk t\ ( ) � � � �1 ÿâëÿåòñÿ àíòèöåïüþ ýòîãî ãðàôà. Ìíîæåñòâî U Y Vk k� \ åñòü àíòèöåïü ÃÒÇ � G Vt k( ) ïî óñëîâèÿì òåîðåìû 2. Î÷åâèäíî, ÷òî U V Ut k t� � �� ( \ ( ))1 , ïîýòîìó ìíîæåñòâî U — àíòè- öåïü ÃÒÇ � G Vt k( ) . Òàêèì îáðàçîì, ïîëó÷åíî ïðîòèâîðå÷èå, ïîñêîëüêó îðèåíòèðîâàííûé ïîä- ãðàô � G V k( ) ïîñòðîåí àëãîðèòìîì ÂÍ-îðãðàôà è íà øàãå 5 àíòèöåïü U * áûëà áû îáíàðóæåíà. Ýòî äîêàçûâàåò ñïðàâåäëèâîñòü òåîðåìû 2. Ñëåäñòâèå 1. Îðãðàô � G V( )0 , ïîñòðîåííûé àëãîðèòìîì ÂÍ-îðãðàôà, ÿâëÿåò- ñÿ âåðøèííî-íàñûùåííûì. Òåîðåìà 3. ÂÍ-îðãðàô ìîæíî ïîñòðîèòü çà âðåìÿ O n( )5 . Äëÿ îäíîêðàòíîãî âûïîëíåíèÿ øàãîâ 1–6 íåîáõîäèìî âðåìÿ, ðàâíîå O n k ( )3 , ãäå nk — ðàçìåð èíèöèèðóþùåãî ìíîæåñòâà â � G V k( ) . Ïîëàãàÿ, ÷òî íà êàæäîé èòåðàöèè óêàçàííîãî âûøå àëãîðèòìà íàèáîëüøàÿ àíòèöåïü óâåëè÷èâàåòñÿ íà îäíó âåðøèíó, ïîëó÷àåì âðåìÿ ïîñòðîåíèÿ îðãðàôà � G V k( ) âåðøèííî-íàñûùåí- íîãî îòíîñèòåëüíî ñâîåãî èíèöèèðóþùåãî ìíîæåñòâà, ðàâíîå O n k ( )4 . Ñëåäîâàòåëüíî, âðåìÿ ïîñòðîåíèÿ ïðàâèëüíî ïîñòðîåííîãî âåðøèííî-íàñû- ùåííîãî îðãðàôà � G V( )0 ðàâíî O n O n k nk ( ) ( )4 5� � � . � Òåîðåìà 4. Ïóñòü îðãðàô � G V( )0 åñòü âåðøèííî-íàñûùåííûé. Òîãäà ñóùåñ- òâóåò ÌÖÐ P ãðàôà � G Vt ( )0 òàêîå, ÷òî åãî öåïè ñîäåðæàò òîëüêî ñóùåñòâåííûå âåðøèíû. Ïóñòü � G V( )0 — îðãðàô, ïîñòðîåííûé àëãîðèòìîì ÂÍ-îðãðàôà. Ñîãëàñíî òå- îðåìå 3 êàæäûé äâóäîëüíûé îðãðàô G V Vk k( , )�1 , k m� �0 1 1, , ..., , ýòîãî îðãðàôà óäîâëåòâîðÿåò òåîðåìå Õîëëà è, ñëåäîâàòåëüíî, èìååò ïàðîñî÷åòàíèå, êîòîðîå íàñûùàåò êàæäóþ âåðøèíó ìíîæåñòâà V k�1. � Ñëåäñòâèå 2. Ïóñòü � G V( )0 åñòü ÂÍ-îðãðàô. Òîãäà êàæäàÿ öåïü ÌÖÐ P ãðàôà � G Vt ( )0 íà÷èíàåòñÿ â íåêîòîðîé âåðøèíå v ìíîæåñòâà V 0. Ïîëó÷åííûé ðåçóëüòàò ïîçâîëÿåò â äàëüíåéøåì äëÿ íàõîæäåíèÿ ÌÖÐ ãðàôà � G Vt ( )0 èñïîëüçîâàòü ìàòðèöó ñìåæíîñòè ÂÍ-îðãðàôà � G V( )0 êàê ðàáî÷óþ òàáëèöó. Òàêèì îáðàçîì, äàëåå ïîëàãàåì, ÷òî öåïè ÌÖÐ ãðàôà òðàíçèòèâíîãî çàìûêàíèÿ ÂÍ-îðãðàôà íàõîäÿòñÿ ñ èñïîëüçîâàíèåì ìàòðèöû ñìåæíîñòè îðãðàôà, ò.å. ïðè ïî- ñòðîåíèè êàæäîãî íîâîãî ÌÖÐ âûáèðàåì äëÿ åãî öåïåé òîëüêî ñóùåñòâåííûå äóãè. Ðàçóìååòñÿ, ÷òî ïðè îòûñêàíèè íàèáîëüøèõ àíòèöåïåé � ( )U v òàêîãî ÃÒÇ íóæíî èñïîëüçîâàòü ìàòðèöó åãî ñìåæíîñòè. ÀËÃÎÐÈÒÌ ÍÀÕÎÆÄÅÍÈß ÍÁÍÌ ÃÐÀÔÀ Ïóñòü ïîñòðîåí ÂÍ-îðãðàô � G V( )0 , â êîòîðîì èìååòñÿ ÍÁÍÌ �U òàêîå, ÷òî Card Card( � ) ( )U V 0 . ßñíî, ÷òî òîãäà õîòÿ áû îäíà èç öåïåé ãðàôà òðàíçèòèâ- íîãî çàìûêàíèÿ ÂÍ-îðãðàôà � G V( )0 ñîäåðæèò ôèêòèâíóþ äóãó, êîíöåâûå âåð- øèíû êîòîðîé ïðèíàäëåæàò ÍÁÍÌ. 46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 Ïóñòü äàëåå â ÃÒÇ � G Vt ( )0 íàéäåíà íåêîòîðàÿ ôèêòèâíàÿ äóãà v vi j .Óäàëèì èç îðãðàôà � G V( )0 âåðøèíû v vi j, , à òàêæå âñå ñìåæíûå ñ íèìè âåðøèíû. Â ðåçóëü- òàòå ïîëó÷èì îðãðàô � � G V V1 1 0 1 1( ) ( , )� � , ãäå V V v v v vi j i j1 � � �\ ({ , } ( ) ( ))� � , V V v vi j1 0 0 1 1� �� \ ( ( ) ( )) � � � � , � � � �1 1� �V . Çäåñü � � �( ) ( ) ( )v v v� � � � � 1 . Ê îðãðàôó � G V1 1 0( ) ïðèìåíèì àëãîðèòì ïîñòðîåíèÿ ÂÍ-îðãðàôà, â ðåçóëüòàòå ïîëó÷èì îðãðàô � G Z( )0 , êîòîðûé íàçîâåì ÂÍ-îðãðàôîì, ïîðîæäåííûì óäàëåíè- åì ôèêòèâíîé äóãè v vi j . Àëãîðèòì ïîèñêà ÍÁÍÌ îðãðàôà � G V( )0 ïîñòðîåí íà ïðåäïîëîæåíèè, ÷òî ñïðàâåäëèâà ñëåäóþùàÿ ãèïîòåçà. Ãèïîòåçà 1. Ïóñòü ÂÍ-îðãðàô � G V( )0 èìååò íåçàâèñèìîå ìíîæåñòâîU òàêîå, ÷òî Card Card( ) ( )U V 0 . Òîãäà íàéäåòñÿ ôèêòèâíàÿ äóãà v vi j òàêàÿ, ÷òî â ÂÍ-îðãðàôå � G Z( )0 , ïîðîæäåííîì óäàëåíèåì ýòîé äóãè, âûïîëíÿåòñÿ ñîîòíî- øåíèå Card Card( ) ( )Z V0 0 1 � . Ñôîðìóëèðîâàííàÿ ãèïîòåçà ïîçâîëÿåò ïðåäëîæèòü ðàçðåøàþùèé àëãîðèòì äëÿ íàõîæäåíèÿ ÍÁÍÌ ãðàôà G Ln� . Âõîäîì àëãîðèòìà ÿâëÿåòñÿ íåîðèåíòèðî- âàííûé ãðàô G Ln� . Àëãîðèòì íàõîæäåíèÿ ÍÁÍÌ Øàã 1. Âûïîëíèòü ïåðâîíà÷àëüíóþ îðèåíòàöèþ ðåáåð ãðàôà G Ln� òàê, ÷òîáû ïîëó÷èòü àöèêëè÷åñêèé îðãðàô � G V( )0 . Øàã 2. Äëÿ îðãðàôà � G V( )0 âûïîëíèòü àëãîðèòì ïîñòðîåíèÿ ÂÍ-îðãðàôà. Øàã 3. Â ãðàôå òðàíçèòèâíîãî çàìûêàíèÿ ÂÍ-îðãðàôà íàéòè íåîòìå÷åííóþ ôèêòèâíóþ äóãó v vi j è îòìåòèòü åå êàê ðàññìîòðåííóþ. Åñëè âñå ôèêòèâíûå äóãè îòìå÷åíû, òî ïåðåéòè ê øàãó 7. Øàã 4. Èç ÂÍ-îðãðàôà � G V( )0 óäàëèòü âåðøèíû v vi j, , à òàêæå âñå ñìåæíûå ñ íèìè âåðøèíû. Â ðåçóëüòàòå áóäåò ïîëó÷åí îðãðàô � G V1 1 0( ) . Øàã 5. Äëÿ îðãðàôà � G V1 1 0( ) âûïîëíèòü àëãîðèòì ïðîñòîåíèÿ ÂÍ-îðãðàôà. Â ðåçóëüòàòå áóäåò ïîëó÷åí îðãðàô � G Z( )0 . Øàã 6. Åñëè Card Card( ) ( )Z V0 0 1 � , òî ïîñòðîèòü ìíîæåñòâî W Z v vi j� �0 { , } è â íàñûùåííîì îðãðàôå � G V( )0 âûïîëíèòü îïåðàöèþ ñå÷åíèÿ �W G V( ( )) � 0 . Ïåðåéòè ê øàãó 2. Â ïðîòèâíîì ñëó÷àå âåðíóòüñÿ ê øàãó 3. Øàã 7. Ïîëîæèòü ÍÁÍÌ �U V� 0 . Òåîðåìà 5. Åñëè ãèïîòåçà 1 âåðíà, òî ñôîðìóëèðîâàííûé àëãîðèòì íàõîäèò ÍÁÍÌ ãðàôà G Ln� . Äîêàçàòåëüñòâî î÷åâèäíî. Òåîðåìà 6. Âðåìÿ ðàáîòû àëãîðèòìà íàõîæäåíèÿ ÍÁÍÌ ðàâíî O n( )8 . Äåéñòâèòåëüíî, äëÿ îäíîêðàòíîãî âûïîëíåíèÿ øàãîâ 3–6 àëãîðèòìà íàõîæ- äåíèÿ ÍÁÍÌ íåîáõîäèìî âðåìÿ, ðàâíîå O n( ) 1 5 , ãäå n1 — ÷èñëî âåðøèí â îðãðàôå � G Z( )0 , ïîðîæäåííîì óäàëåíèåì ôèêòèâíîé äóãè. Òàê êàê îáùåå ÷èñëî ôèêòèâ- íûõ äóã ðàâíî O n( )2 , â õóäøåì ñëó÷àå äëÿ âûïîëíåíèÿ øàãîâ 3–6 íåîáõîäèìî âðåìÿ, ðàâíîå O n( )7 . Åñëè ïðåäïîëîæèòü, ÷òî ïîñëå âûïîëíåíèÿ ýòèõ øàãîâ íàé- äåííîå íåçàâèñèìîå ìíîæåñòâî V 0 óâåëè÷èòñÿ íà åäèíèöó, òî îáùåå âðåìÿ âû- ïîëíåíèÿ øàãîâ 2–6 áóäåò ðàâíî O n( )8 . � ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 47 ÝÊÑÏÅÐÈÌÅÍÒÀËÜÍÛÅ ÐÅÇÓËÜÒÀÒÛ Äëÿ ïðåäëàãàåìîãî àëãîðèòìà àâòîðîì áûëà íàïèñàíà ïðîãðàììà íà Ïàñêàëå, à Òîìàñîì Êàðáå (Thomas Karbe) èç Áåðëèíñêîãî òåõíè÷åñêîãî óíèâåðñèòåòà — íà ÿçûêå Java (http://www.is.svitonline.com/plot/solver.html èëè http://www.vinnica.ua/ ~aplot/solver.html). Äëèòåëüíîå òåñòèðîâàíèå ïðîãðàìì íà ñëó÷àéíûõ ãðàôàõ ïîêàçàëî, ÷òî àë- ãîðèòì ðàáîòàåò ñòàáèëüíî è êîððåêòíî. Êðîìå òîãî, îñóùåñòâëÿëàñü îòëàäêà ïðîãðàììû íà ÿçûêå Java â ðàáîòå ñ èçâåñòíûìè ïðèìåðàìè. Â òàáë. 1 ïðèâåäåíû íåêîòîðûå ðåçóëüòàòû âû÷èñëèòåëüíîãî ýêñïåðèìåíòà, êîòîðûé áûë âûïîëíåí íà íîóòáóêå (Toshiba Personal Computer, Intel Celeron M processor, 1.60 GHz, 736 ÎÇÓ, ÎÑ Microsoft Windows XP Home Edition SP3). Òàêèì îáðàçîì, ïðåäëîæåííûé àëãîðèòì ïðàêòè÷åñêè íåêîíêóðåíòåí ââèäó âûñî- êîé ñòåïåíè ïîëèíîìèàëüíîé îöåíêè âðåìåíè âûïîëíåíèÿ. Îäíàêî òåîðåòè÷åñêè îí âà- æåí, òàê êàê ñóùåñòâóåò íåêîòîðàÿ âåðîÿòíîñòü äîêàçàòåëüñòâà, ÷òî äëÿ NP-ïîëíûõ çà- äà÷ ìîæíî ïîñòðîèòü ïîëèíîìèàëüíî-âðåìåííîé ðåøàþùèé àëãîðèòì. Ïîëó÷åííûå ýêñïåðèìåíòàëüíûå ðåçóëüòàòû ïîäòâåðæäàþò ïðàâèëüíîñòü âûáðàííîé ìåòîäîëîãèè ðåøåíèÿ îäíîé èç íàèáîëåå òðóäíûõ çàäà÷ êëàññà NÐ. Îíè òàêæå ÿâëÿþòñÿ ñòèìóëîì äëÿ áîëåå ïîëíîãî èññëåäîâàíèÿ ñâîéñòâ ÂÍ-îðãðàôîâ äëÿ äîêàçàòåëüñòâà âûäâèíóòîé ãèïîòåçû. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ã ý ð è Ì . , Ä æ î í ñ î í Ä . Âû÷èñëèòåëüíûå ìàøèíû è òðóäíîðåøàåìûå çàäà÷è: Ïåð. ñ àíãë. — Ì.: Ìèð, 1982. — 416 ñ. 2. A c o mp e n d i u m of NP optimization problems. — Stocholm: Royal Inst. of Technology, 1998. — 61 p. 3. Ñ â à ì è Ì . , Ò õ ó ë à ñ è ð à ì à í Ê . Ãðàôû, ñåòè è àëãîðèòìû: Ïåð. ñ àíãë. — Ì.: Ìèð, 1984. — 454 ñ. 4. W e s t D . Â . Introduction to graph theory. — Englewood Cliffs (NJ): Prentice Hall, 1996. — 512 p. 5. Ð å é í ã î ë ü ä Ý . , Ä å î Í . Êîìáèíàòîðíûå àëãîðèòìû: Ïåð. ñ àíãë. — Ì.: Ìèð, 1980. — 476 ñ. 6. Ô î ð ä Ë . Ð . , Ô à ë ê å ð ñ î í Ä . Ð . Ïîòîêè â ñåòÿõ: Ïåð. ñ àíãë. — Ì.: Ìèð, 1966. — 276 ñ. Ïîñòóïèëà 10.11.2010 Ïîñëå äîðàáîòêè 16.04.2012 48 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 5 Íàçâàíèå ôàéëà Êîëè÷åñòâî Âðåìÿ ðåøåíèÿ, ñâåðøèí ðåáåð brock200_1.clq 200 14834 172971.438 brock200_2.clq 200 9876 7513.078 brock200_3.clq 200 12048 29699.031 c-fat200-1.clq 200 1534 23.312 c-fat200-2.clq 200 3235 17.422 c-fat200-5.clq 200 8473 29.609 c-fat500-1.clq 500 4459 29.609 c-fat500-2.clq 500 9139 711.125 c-fat500-5.clq 500 23191 793.656 Íàçâàíèå ôàéëà Êîëè÷åñòâî Âðåìÿ ðåøåíèÿ, ñâåðøèí ðåáåð c-fat500-10.clq 500 46627 2182.938 hamming6-2.clq 64 1824 0.141 hamming6-4.clq 64 704 2.375 hamming8-2.clq 256 31616 9.266 johnson8-2-4.clq 28 210 0.203 johnson8-4-4.clq 70 1855 76.421 johnson16-2-4.clq 120 5460 4731.469 keller4.clq 171 9435 17816.656 p_hat500-1.clq 500 31569 81801.313 Ò à á ë è ö à 1

Эвристический алгоритм для поиска наибольшего независимого множества

Репозитарії

Схожі ресурси