Совершенные паросочетания и расширенный полиматроид
Зазначено, що у відомих алгоритмах розв'язування задачі про призначення в явному вигляді чи опосередковано використовуються відомі класичні умови існування перфектного паросполучення в дводольному графі. Показано, що кожному дводольному графу можна співставити деякий вектор і розширений полімат...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2008 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/72218 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Совершенные паросочетания и расширенный полиматроид / Ф.А. Шарифов // Кибернетика и системный анализ. — 2008. — № 3. — С. 173-179. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859636559378120704 |
|---|---|
| author | Шарифов, Ф.А. |
| author_facet | Шарифов, Ф.А. |
| citation_txt | Совершенные паросочетания и расширенный полиматроид / Ф.А. Шарифов // Кибернетика и системный анализ. — 2008. — № 3. — С. 173-179. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Зазначено, що у відомих алгоритмах розв'язування задачі про призначення в явному вигляді чи опосередковано використовуються відомі класичні умови існування перфектного паросполучення в дводольному графі. Показано, що кожному дводольному графу можна співставити деякий вектор і розширений поліматроїд таким чином, що даний вектор є базою цього розширеного поліматроїда тоді та тільки тоді, коли даний граф містить перфектие паросполучення.
|
| first_indexed | 2025-12-07T13:16:13Z |
| format | Article |
| fulltext |
ÓÄÊ 519.8
Ô.À. ØÀÐÈÔÎÂ
ÑÎÂÅÐØÅÍÍÛÅ ÏÀÐÎÑÎ×ÅÒÀÍÈß
È ÐÀÑØÈÐÅÍÍÛÉ ÏÎËÈÌÀÒÐÎÈÄ1
Êëþ÷åâûå ñëîâà: ñîâåðøåííîå ïàðîñî÷åòàíèå, äâóäîëüíûé ãðàô, ðàñøèðåí-
íûé ïîëèìàòðîèä.
ÂÂÅÄÅÍÈÅ
Ïîäìíîæåñòâî ìíîæåñòâà ðåáåð ãðàôà íàçûâàåòñÿ ïàðîñî÷åòàíèåì, åñëè â ýòîì
ïîäìíîæåñòâå ïðîèçâîëüíàÿ ïàðà ðåáåð íå èìååò îáùèõ âåðøèí. Ïàðîñî÷åòàíèå
ñ ìàêñèìàëüíûì ÷èñëîì ðåáåð íàçûâàåòñÿ íàèáîëüøèì. Ñ÷èòàþò, ÷òî ïàðîñî÷å-
òàíèå ïîêðûâàåò äàííóþ âåðøèíó, åñëè ýòà âåðøèíà èíöèäåíòíà íåêîòîðîìó åãî
ðåáðó. Åñëè ïàðîñî÷åòàíèå ïîêðûâàåò âñå âåðøèíû ãðàôà, òî îíî íàçûâàåòñÿ ñî-
âåðøåííûì ïàðîñî÷åòàíèåì. Çàäà÷à íàõîæäåíèÿ ñîâåðøåííîãî è ìàêñèìàëüíîãî
ïàðîñî÷åòàíèÿ ÷àñòî âîçíèêàåò ïðè îïðåäåëåíèè âåðõíåé îöåíêè äëÿ îïòèìàëüíî-
ãî çíà÷åíèÿ çàäà÷è ñèíòåçà ñåòè ïðè óñëîâèè, ÷òî ïîñëå óäàëåíèÿ ïðîèçâîëüíîãî
ðåáðà èç ñåòè â ïîëó÷åííîì ïîäãðàôå äîëæåí ñóùåñòâîâàòü õîòÿ áû îäèí ïóòü,
ñîåäèíÿþùèé ïðîèçâîëüíóþ ïàðó òåðìèíàëüíûõ óçëîâ. Ïðåäëîæåí ðÿä ýôôåê-
òèâíûõ àëãîðèòìîâ äëÿ íàõîæäåíèÿ ìàêñèìàëüíîãî ïàðîñî÷åòàíèÿ â äâóäîëüíîì
ãðàôå G U V E� ( , , ). Íàèëó÷øèì ïî âðåìåííîé ñëîæíîñòè ÿâëÿåòñÿ àëãîðèòì ñ
òðóäîåìêîñòüþ O n m n( / ).1 5 log â [1, 2], ãäå | |E = m è | | | |U V n� � .
 ðàáîòå [3] ïðåäëîæåí ìåòîä ñèãíàòóðû (the signature method) äëÿ ðåøåíèÿ
çàäà÷è íàçíà÷åíèÿ. Ñ åãî ïîìîùüþ íàõîäèòñÿ ðåøåíèå äâîéñòâåííîé çàäà÷è ê
çàäà÷å íàçíà÷åíèÿ. Ïðè ýòîì, åñëè ìíîæåñòâî ðåáåð, îòíîñèòåëüíî êîòîðûõ âû-
ïîëíÿþòñÿ óñëîâèÿ äîïîëíÿþùåé íåæåñòêîñòè, îáðàçóþò îñòîâíîå äåðåâî T ïî-
ëíîãî äâóäîëüíîãî ãðàôà, à ñòåïåíè âåðøèí ýòîãî äåðåâà — ïðîèçâîëüíûé âåê-
òîð (ñ n êîìïîíåíòàìè) âèäà (2,2,...,1,2,...,2), òî äàííûé ìåòîä çàâåðøàåò ðàáîòó è
òàêèì îáðàçîì íàõîäÿòñÿ ðåøåíèÿ äâîéñòâåííîé è ïðÿìîé çàäà÷è.  ðàáîòå [3]
ïîäîáíûå âåêòîðû íàçâàíû ñèãíàòóðîé äåðåâà T . Ïîêàçàíî, ÷òî ëþáîå îñòîâíîå
äåðåâî ñ òàêîé ñèãíàòóðîé ñîäåðæèò ñîâåðøåííîå ïàðîñî÷åòàíèå. Îáû÷íî â ïðî-
öåññå ðåøåíèÿ çàäà÷è íàçíà÷åíèÿ ìíîæåñòâî ðåáåð, îòíîñèòåëüíî êîòîðûõ âû-
ïîëíÿþòñÿ óñëîâèÿ äîïîëíÿþùåé íåæåñòêîñòè, îáðàçóþò íåêîòîðûé îñòîâíûé
ïîäãðàô G ïîëíîãî äâóäîëüíîãî ãðàôà, è ÷àñòî ëèáî ýòîò ïîäãðàô íå ñîäåðæèò
äåðåâà T ñ óêàçàííîé ñèãíàòóðîé, ëèáî îí ÿâëÿåòñÿ îñòîâíûì äåðåâîì ïîëíîãî
äâóäîëüíîãî ãðàôà. Íåñìîòðÿ íà òî ÷òî ñèãíàòóðà äåðåâà (âåêòîð ñ
êîìïîíåíòàìè—ñòåïåíÿìè âåðøèí) îòëè÷àåòñÿ îò âåêòîðà (2,2,...,1,2,...,2), îíî
ñîäåðæèò ñîâåðøåííîå ïàðîñî÷åòàíèå, ò.å. äîïóñòèìîå ðåøåíèå çàäà÷è
íàçíà÷åíèÿ.
Ïóñòü G — íåêîòîðûé ãðàô, dui
, dvi
— ñòåïåíè âåðøèí ui , vi â G è
b du ui i
� �1, b dv vi i
� �1 äëÿ âñåõ u Ui � , v Vi � . Ïîêàæåì, ÷òî ãðàô G ñîäåðæèò
ñîâåðøåííîå ïàðîñî÷åòàíèå òîãäà è òîëüêî òîãäà, êîãäà âåêòîð
� � � �( , , , , , )b b b bu u v vn n1 1
� � ÿâëÿåòñÿ áàçîé ðàñøèðåííîãî ïîëèìàòðîèäà
(îïðåäåëåíèå ñì. íèæå). Èñõîäÿ èç ýòîãî � íàçûâàåòñÿ ñèãíàòóðîé ãðàôà G. Â [4]
ïðåäëîæåí àëãîðèòì òðóäîåìêîñòüþ O mn( ) äëÿ ðåøåíèÿ çàäà÷è íàõîæäåíèÿ ìè-
íèìàëüíîãî ðàçðåçà â ñåòè, ê êîòîðîé ñâîäèòñÿ çàäà÷à ïðèíàäëåæíîñòè çàäàííîãî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 173
1Ðàáîòà âûïîëíåíà ïðè ÷àñòè÷íîé ôèíàíñîâîé ïîääåðæêå INTAS, ãðàíò 06–1000017–8909.
© Ô.À. Øàðèôîâ, 2008
âåêòîðà ê ðàñøèðåííîìó ïîëèìàòðîèäó. Ó÷èòûâàÿ, ÷òî G — äâóäîëüíûé ãðàô,
ïîêàæåì, ÷òî çàäà÷à ïðèíàäëåæíîñòè ñèãíàòóðû � ê ðàñøèðåííîìó
ïîëèìàòðîèäó ýêâèâàëåíòíà ñïåöèàëüíîé òðàíñïîðòíîé çàäà÷å íà ãðàôå G.
ÎÁÎÇÍÀ×ÅÍÈß È ÒÅÐÌÈÍÎËÎÃÈß
Äëÿ óäîáñòâà ìíîæåñòâî âåðøèí çàäàííîãî äâóäîëüíîãî ãðàôà G U V E� ( , , ) îá-
îçíà÷èì êàê UV , ò.å. UV = U V� . Äëÿ S UV� îáîçíà÷èì �( )S è �( )S ìíîæåñ-
òâà, êîòîðûå ñîäåðæàò ðåáðà ñ äâóìÿ êîíå÷íûìè âåðøèíàìè â S è îäíîé êî-
íå÷íîé âåðøèíîé â S ñîîòâåòñòâåííî. Ìíîæåñòâî ðåáåð �( )S íàçûâàåòñÿ ðàç-
ðåçîì â ãðàôå G äëÿ � � S UV . Èç îïðåäåëåíèÿ ìíîæåñòâ �( )S è �( )S
ñëåäóåò, ÷òî � �( ) ( )S S� — ìíîæåñòâî ðåáåð õîòÿ áû ñ îäíîé êîíå÷íîé âåð-
øèíîé â S . Äëÿ S � � ïðåäïîëàãàåì, ÷òî �( )S � � è �( )S � �.
Áóäåì ãîâîðèòü, ÷òî ïîäãðàô F îïðåäåëÿåòñÿ ìíîæåñòâîì âåðøèí S , åñëè S
— ìíîæåñòâî âåðøèí ïîäãðàôà F è âñå ðåáðà ñ êîíå÷íûìè âåðøèíàìè èç S ÿâ-
ëÿþòñÿ åãî ðåáðàìè. Ïîäãðàô F ñ ìíîæåñòâîì ðåáåð �( )w (�( ){ }w ) íàçûâàåòñÿ
çâåçäîé. Ïîëîæèì � � �( ) ( ) ( )S S S� � è îïðåäåëèì ôóíêöèè f S S( ) | ( )|� � è
f S S* ( ) | ( )|� � äëÿ âñåõ S UV� .
Ôóíêöèÿ �, îïðåäåëåííàÿ íà ïîäìíîæåñòâàõ ìíîæåñòâà UV , íàçûâàåòñÿ ñó-
ïåðìîäóëÿðíîé (ñóáìîäóëÿðíîé), åñëè äëÿ âñåõ A B UV, � âûïîëíÿþòñÿ
íåðàâåíñòâà
� � � �( ) ( ) ( ) ( ) ( ).A B A B A B
� � �
Ôóíêöèÿ � — ìîíîòîííàÿ, åñëè � �( ) ( )A B� äëÿ A B UV� � . Ñòåïåíè âåð-
øèí w UV� îáîçíà÷èì dw. Äëÿ êîíå÷íîãî ìíîæåñòâà T è âåêòîðà y ( y R T
� ), êîì-
ïîíåíòû êîòîðîãî èíäåêñèðîâàíû ýëåìåíòàìè T , âìåñòî � �( , )y v Sv áóäåì ïè-
ñàòü y S( ), ãäå S T� . Ñëåäóþùèå óòâåðæäåíèÿ ëåãêî äîêàçûâàþòñÿ:
1) ôóíêöèÿ f S( ) ñóïåðìîäóëÿðíàÿ;
2) ôóíêöèè f S* ( ) è f S f S* ( ) ( )� ñóáìîäóëÿðíûå;
3) f S f S S* ( ) ( ) | ( )|� � � ;
4) f S f S* ( ) ( )� � 0 äëÿ âñåõ S UV� ;
5) f S f S f S f S* *( ) ( ) ( ) ( )� � � äëÿ âñåõ S UV� è S UV S� \ ;
6) f UV f UV f f* *( ) ( ) ( ) ( ) ;� � � � � � 0
7) f S* ( ) è f S( ) — ìîíîòîííûå ôóíêöèè;
8) f S f S* ( ) ( )� — íåìîíîòîííàÿ ôóíêöèÿ;
9) f S f S d S* ( ) ( ) ( )
� äëÿ âñåõ S UV� .
Áóäåì ïðåäïîëàãàòü, ÷òî ïåðâûå n êîìïîíåíò êàæäîãî âåêòîðà y R UV
� èí-
äåêñèðîâàíû ýëåìåíòàìè ìíîæåñòâà U , à îñòàëüíûå n êîìïîíåíò — ýëåìåíòàìè
ìíîæåñòâà V . Ìíîãîãðàííèê
P x R x S S S UVUV( ) ; ( ) ( ), ,� �� � � �{ }
îïðåäåëåííûé ìîíîòîííîé è íåîòðèöàòåëüíîé ñóáìîäóëÿðíîé ôóíêöèåé �, íà-
çûâàåòñÿ ïîëèìàòðîèäîì. Åñëè � — íåîòðèöàòåëüíàÿ ñóáìîäóëÿðíàÿ ôóíêöèÿ,
ìíîãîãðàííèê P ( )� íàçûâàåòñÿ ðàñøèðåííûì ïîëèìàòðîèäîì [5]. Ïîýòîìó
P f f( )*
� ÿâëÿåòñÿ ðàñøèðåííûì ïîëèìàòðîèäîì.
Íå íàðóøàÿ îáùíîñòè, ìîæíî ïðåäïîëîæèòü, ÷òî | | | |U V� äëÿ ïðîèçâîëüíî-
ãî äâóäîëüíîãî ãðàôà G U V E� ( , , ). Äåéñòâèòåëüíî, äîïóñòèì, ÷òî | | | |U V0 � äëÿ
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
ãðàôà G U V E0 0 0� ( , , ).  ýòîì ñëó÷àå, äîáàâèâ | | | |V U� 0 íîâûõ âåðøèí è ðåáðà,
ñîåäèíÿþùèå êàæäóþ íîâóþ âåðøèíó ñ êàæäîé âåðøèíîé èç V , ïîëó÷èì äâó-
äîëüíûé ãðàô G U V E� ( , , ) ñ | | | |U V� è U U0 . Äîïóñòèì, ÷òî M — ìàêñèìàëü-
íîå ïàðîñî÷åòàíèå â G è M 0 — ÷àñòè÷íîå ïàðîñî÷åòàíèå ïàðîñî÷åòàíèÿ M òà-
êîå, ÷òî M 0 ñîäåðæèò òîëüêî ðåáðà, ïîêðûâàþùèå íîâûå âåðøèíû.
Óòâåðæäåíèå 1. Åñëè M — ìàêñèìàëüíîå ïàðîñî÷åòàíèå â ãðàôå G, òî ïàðî-
ñî÷åòàíèå M M\ 0 — ìàêñèìàëüíîå ïàðîñî÷åòàíèå â G0 .
Äîêàçàòåëüñòâî. Åñëè M — ñîâåðøåííîå ïàðîñî÷åòàíèå â G, òî äîêàçàò-
åëüñòâî óòâåðæäåíèÿ òðèâèàëüíî. Ïóñòü W0 — ìàêñèìàëüíîå ïàðîñî÷åòàíèå â G0
è äîïóñòèì, ÷òî | | | \ |W M M0 0� . Â ãðàôå G âûäåëèì ðåáðà, ñîîòâåòñòâóþùèå ðåá-
ðàì W0 . Òàê êàê êàæäàÿ íîâàÿ âåðøèíà ñîåäèíåíà ñ êàæäîé âåðøèíîé v V� , ê ïàðîñî-
÷åòàíèþ W0 ìîæíî äîáàâèòü ðåáðà òàêèå, ÷òî îíè îáðàçóþò ïàðîñî÷åòàíèå Wn , êîòî-
ðîå ïîêðûâàåò âñå íîâûå âåðøèíû. ßñíî, ÷òî Wn è W0 íå èìåþò îáùèõ âåðøèí. Ïîý-
òîìó W W Wn � �0 — ìàêñèìàëüíîå ïàðîñî÷åòàíèå â G. Òîãäà èç | | | \ |W M M0 0�
ñëåäóåò, ÷òî | | | |W M� . Ýòî ïðîòèâîðå÷èò òîìó, ÷òî M — ìàêñèìàëüíîå
ïàðîñî÷åòàíèå â G.
ÏÀÐÎÑÎ×ÅÒÀÍÈÅ È ÐÀÑØÈÐÅÍÍÛÉ ÏÎËÈÌÀÒÐÎÈÄ
Ïîêàæåì, ÷òî â äâóäîëüíîì ãðàôå G ñóùåñòâóåò ñîâåðøåííîå ïàðîñî÷åòàíèå
òîãäà è òîëüêî òîãäà, êîãäà âåêòîð � ÿâëÿåòñÿ áàçîé ðàñøèðåííîãî ïîëèìàòðî-
èäà P f f( )*
� . Íàïîìíèì, ÷òî âåêòîð x R UV
� ÿâëÿåòñÿ áàçîé P f f( )*
� , åñëè
x UV f UV f UV( ) ( ) ( )*
� � � 0 è x S f S f S( ) ( ) ( )*
� � äëÿ âñåõ S UV� . Áàçà
P f f( )*
� îïðåäåëÿåòñÿ ñ ïîìîùüþ ãðèäè-àëãîðèòìà ñëåäóþùèì îáðàçîì [5].
Ïóñòü UV w w n0 1 2� { }, ,� — íåêîòîðîå ëèíåéíîå óïîðÿäî÷åíèå âåðøèí èç
UV ; L0 � �; L w wi i� { }1, ,� äëÿ âñåõ i n�1 2, ,� .
Äëÿ âñåõ i n�1 2, ,� ïîëîæèì
x f L f L f L f L
w i i i i
i
0 1 1� � �
� �
* *( ) ( ) ( ) ( ). (1)
 [5] äîêàçûâàåòñÿ, ÷òî âåêòîð x 0 ÿâëÿåòñÿ áàçîé ðàñøèðåííîãî ïîëèìàòðî-
èäà P f f( )*
� . Èç îïðåäåëåíèÿ áàçû x 0 ÿñíî, ÷òî ðàçëè÷íûì ëèíåéíûì óïîðÿ-
äî÷åíèÿì âåðøèí èç UV ñîîòâåòñòâóþò ðàçëè÷íûå áàçû P f f( )*
� , èíûìè ñëî-
âàìè, âåêòîðû, ñîîòâåòñòâóþùèå ðàçëè÷íûì ëèíåéíûì óïîðÿäî÷åíèÿì âåðøèí,
ÿâëÿþòñÿ êðàéíèìè òî÷êàìè ìíîãîãðàííèêà P f f( )*
� . Âåêòîð x 0 íàçîâåì áàçîé
P f f( )*
� îòíîñèòåëüíî ëèíåéíîãî óïîðÿäî÷åíèÿ UV0 .
 äàëüíåéøåì áóäåì ïðåäïîëàãàòü, ÷òî G — ñâÿçíûé ãðàô. Ýòî ïðåäïîëîæå-
íèå åñòåñòâåííî, òàê êàê â ïðîòèâíîì ñëó÷àå ìîæåì ðàññìîòðåòü êàæäóþ êîìïî-
íåíòó ñâÿçíîñòè ãðàôà G êàê îòäåëüíûé ãðàô.
Ïóñòü UV u u v vn n1 1 1� { }, , , , ,� � — ëèíåéíîå óïîðÿäî÷åíèå âåðøèí ãðàôà
G òàêîå, ÷òî u Ui � è v Vi � äëÿ âñåõ i n�1, ,� . Ïî ôîðìóëå (1) âåêòîð
x d d d dd
u u v vn n
� � �( , , , , , )
1 1
� � ÿâëÿåòñÿ áàçîé ðàñøèðåííîãî ïîëèìàòðîèäà
P f f( )*
� îòíîñèòåëüíî ëèíåéíîãî óïîðÿäî÷åíèÿ UV1. Ó÷èòûâàÿ ñèììåòðè÷-
íîñòü äâóäîëüíîãî ãðàôà, ïîëó÷àåì, ÷òî âåêòîð � x d òàêæå ÿâëÿåòñÿ áàçîé
P f f( )*
� îòíîñèòåëüíî ëèíåéíîãî óïîðÿäî÷åíèÿ {v vn1, , ,� u un1, ,� }.
Äëÿ êàæäîãî A U� ìíîæåñòâî âåðøèí èç v V� , ñìåæíûõ ñ âåðøèíàìè A,
îáîçíà÷èì N A . Ïî òåîðåìå Êåíèãà–Õîëëà, êîòîðàÿ ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì
òåîðåìû Òàòòà î ñîâåðøåííûõ ïàðîñî÷åòàíèÿõ [5], â ãðàôå G ñóùåñòâóåò ñîâåð-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 175
øåííîå ïàðîñî÷åòàíèå òîãäà è òîëüêî òîãäà, êîãäà | | | |A N A� äëÿ âñåõ A U� . Òàê
êàê G — ñâÿçíûé äâóäîëüíûé ãðàô, èìååì dw � 1 äëÿ âñåõ w UV� . Ïîýòîìó
b dw w� �1 — öåëîå ÷èñëî äëÿ âñåõ w UV� . Ïóñòü âåêòîð b b bu un
� ( , , ,
1
�
b bv vn1
, , )� . Òîãäà ñèãíàòóðà ãðàôà G — âåêòîð � � � �( , , , , , )b b b bu u v vn n1 1
� � ,
ãäå u Ui � è v Vi � äëÿ âñåõ i n�1, ,� .
Òåîðåìà 1.  ãðàôå G ñóùåñòâóåò ñîâåðøåííîå ïàðîñî÷åòàíèå òîãäà è òîëü-
êî òîãäà, êîãäà ñèãíàòóðà � ãðàôà G ÿâëÿåòñÿ áàçîé ðàñøèðåííîãî ïîëèìàòðîèäà
P f f( )*
� .
Äîêàçàòåëüñòâî. Ïîñêîëüêó ïî îïðåäåëåíèþ ñèãíàòóðû è óòâåðæäåíèþ 6
�( ) ( ) ( )*UV f UV f UV� � �0 , äëÿ äîêàçàòåëüñòâà òåîðåìû äîñòàòî÷íî ïîêàçàòü,
÷òî åñëè â ãðàôå G ñóùåñòâóåò ñîâåðøåííîå ïàðîñî÷åòàíèå, òî � � �P f f( )* , è
íàîáîðîò. Ñíà÷àëà ïîêàæåì, ÷òî åñëè � � �P f f( )* , òî â ãðàôå G ñóùåñòâóåò
ñîâåðøåííîå ïàðîñî÷åòàíèå.
Äëÿ ïðîèçâîëüíîãî A U� èç îïðåäåëåíèÿ ñèãíàòóðû � ñëåäóåò
| | | | ( ) ( ) ( ( ) ( )) ( ) ( ) (N A d N d A b N b A d N d A A NA A A A A� � � � � � � � �� ),
à òàêæå ïî îïðåäåëåíèþ ôóíêöèé f * è f èìååì
d N d A f A N f A NA A A( ) ( ) ( ) ( ).*
� � � � �
Ïîýòîìó
| | | | ( ) ( ) ( ( ) ( ))N A d N d A b N b AA A A� � � � � �
� � � � � �f A N f A N A NA A A
* ( ) ( ) ( ).�
Ïîñêîëüêó � � �P f f( )* , òî f A N f A N A NA A A
* ( ) ( ) ( )� � � � � �� 0. Äðó-
ãèìè ñëîâàìè, | | | |N AA � äëÿ ïðîèçâîëüíîãî A U� . Ïîýòîìó â ãðàôå G ñóùåñ-
òâóåò ñîâåðøåííîå ïàðîñî÷åòàíèå.
Äîêàæåì îáðàòíîå óòâåðæäåíèå òåîðåìû: åñëè â ãðàôå G ñóùåñòâóåò ñîâåð-
øåííîå ïàðîñî÷åòàíèå, òî � � �P f f( )* . Ïóñòü M — ñîâåðøåííîå ïàðîñî÷åòà-
íèå â ãðàôå G. Ðàññìîòðèì äâóäîëüíûé ãðàô G U V E M1 � ( , , \ ), ò.å. ãðàô G1 ïî-
ëó÷àåòñÿ ïîñëå óäàëåíèÿ ðåáåð ñîâåðøåííîãî ïàðîñî÷åòàíèÿ M èç ãðàôà G.
Îïðåäåëèì ñóáìîäóëÿðíóþ è ñóïåðìîäóëÿðíóþ ôóíêöèè f A1
* ( ) è f A1 ( ) îòíîñè-
òåëüíî ãðàôà G1 àíàëîãè÷íî îïðåäåëåíèþ ôóíêöèé f A* ( ) è f A( ) äëÿ G. ßñíî,
÷òî f A f A f A f A1 1
* *( ) ( ) ( ) ( )� � � äëÿ ïðîèçâîëüíîãî A UV� è, êðîìå òîãî,
ñòåïåíè âåðøèí w ðàâíû bw â ãðàôå G1. Ñëåäîâàòåëüíî, âåêòîð
( , , , , , )� �b b b bu u v vn n1 1
� � ÿâëÿåòñÿ áàçîé ðàñøèðåííîãî ïîëèìàòðîèäà
P f f( )*
1 1� îòíîñèòåëüíî ëèíåéíîãî óïîðÿäî÷åíèÿ {v vn1, , ,� u un1, ,� }. Òàêèì
îáðàçîì, �( ) ( ) ( ) ( ) ( )* *A f A f A f A f A� � � �1 1 äëÿ ïðîèçâîëüíîãî A UV� , ÷òî
çàâåðøàåò äîêàçàòåëüñòâî òåîðåìû.
Èç òåîðåìû ïîëó÷àåì ñëåäóþùèé ðåçóëüòàò.
Ñëåäñòâèå 1. Åñëè � ÿâëÿåòñÿ áàçîé ðàñøèðåííîãî ïîëèìàòðîèäà
P f f( )*
� , òî âåêòîð � � òàêæå áàçà P f f( )*
� .
Ñîãëàñíî òåîðåìå 1 çàäà÷à ïðèíàäëåæíîñòè âåêòîðà � ðàñøèðåííîìó ïîëè-
ìàòðîèäó P f f( )*
� ñâîäèòñÿ ê ñëåäóþùåé çàäà÷å:
min{ }f A f A A A UV* ( ) ( ) ( ), .� � ��
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
 ðàáîòå [4] ïîêàçàíî, ÷òî ïîñëåäíàÿ çàäà÷à ýêâèâàëåíòíà íàõîæäåíèþ ìè-
íèìàëüíîãî ðàçðåçà ãðàôà G è äëÿ åå ðåøåíèÿ ïðåäëîæåí àëãîðèòì òðóäîåìêîñ-
òüþ O mn( ). Â ýòîì àëãîðèòìå òàêæå èñïîëüçóþòñÿ áàçû ðàñøèðåííîãî
ïîëèìàòðîèäà P f f( )*
� .
Äëÿ ïðîèçâîëüíîãî A UV� ïî óòâåðæäåíèþ 9 èìååì
f A f A A f A d A A* *( ) ( ) ( ) ( ) [ ( ) ( )].� � � �
� �2
Ïî óòâåðæäåíèþ 7) f A* ( ) — ïîëèìàòðîèäíàÿ ôóíêöèÿ è dv v
�� 0 äëÿ âñåõ
v UV� . Òîãäà èìååì [5]
min{ }2 f A d A A A UV* ( ) [ ( ) ( )],�
� ��
� � � � �
max{ }z UV z A f A A UV z d( ); ( ) ( ), , .*2 0 �
Ïóòåì çàìåíû ïåðåìåííûõ y z d� � â ïðàâîé ñòîðîíå ýòîãî íåðàâåíñòâà,
à òàêæå ñ ó÷åòîì f A d A f A* ( ) ( ) ( )� � ïîëó÷àåì
min{ }f A f A A A UV* ( ) ( ) ( ),� � � ��
� � � � � �max ( ); ( ), .*{ }y UV y P f f d y � (2)
 ôîðìóëå (2) îãðàíè÷åíèÿ � � �d y bu u u ìîæíî çàìåíèòü íà 0 � �y bu u äëÿ
âñåõ u U� , â ñìûñëå, ÷òî ïîñëå òàêîé çàìåíû îïòèìàëüíîå ðåøåíèå çàäà÷è íå
èçìåíèòñÿ. Ïåðåìåííûå yu ïðåäñòàâèìû â âèäå
y z u Uu
u v u
uv� �
�
�
( , ) ( )
,
�
äëÿ âñåõ
y z v Vv
u v v
uv� � �
�
�
( , ) ( )
,
�
äëÿ âñåõ
ãäå ïåðåìåííûå zuv äîëæíû óäîâëåòâîðÿòü îãðàíè÷åíèÿì 0 1� �zuv . Òîãäà
îãðàíè÷åíèÿ
0 � � � � � � � �y b u U d y b v Vu u v v v, , , ,
ïðåîáðàçóþòñÿ ê ñëåäóþùåìó âèäó:
z u b u U z v b v Vu v( ( )) , , ( ( )) , .� �� � � �
Ñîãëàñíî ñëåäñòâèþ 1 è ñ ó÷åòîì ñèììåòðè÷íîñòè äâóäîëüíîãî ãðàôà G, çàäà-
÷à (2) ìîæåò áûòü çàïèñàíà îòíîñèòåëüíî âåêòîðà � �. Òîãäà ïîëó÷èì ïîäî-
áíóþ (2) çàäà÷ó ñ îãðàíè÷åíèÿìè � � � �d y bu u u è 0 � �y bv v . Àíàëîãè÷íî
óêàçàííîìó âûøå ñïîñîáó îãðàíè÷åíèÿ ïîëó÷åííîé çàäà÷è ìîãóò ïðåîáðàçî-
âûâàòüñÿ ê ñëåäóþùåìó âèäó:
z u b u U z v b v Vu v( ( )) , , ( ( )) , .� �� � � �
Ïîëó÷åííûå ñèñòåìû íåðàâåíñòâ äëÿ âåêòîðà ïåðåìåííûõ z ýêâèâàëåíòíû
îãðàíè÷åíèÿì òðàíñïîðòíîãî òèïà:
z w b w UVw( ( )) ,� � � , (3)
0 1� � �z e Ee , . (4)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 177
Ïîêàæåì, ÷òî åñëè ïåðåìåííûå z z i U j Vij� � �{ }; , óäîâëåòâîðÿþò îãðàíè÷å-
íèÿì (3), (4), òî âåêòîðû � è � � ÿâëÿþòñÿ áàçàìè ðàñøèðåííîãî ïîëèìàòðîè-
äà P f f( )*
� .
Òàê êàê b U b V( ) ( )� , ñóùåñòâîâàíèå äîïóñòèìîãî ðåøåíèÿ ñèñòåì (3), (4)
ñâÿçàíî òîëüêî ñî ñòðóêòóðîé äâóäîëüíîãî ãðàôà G. Ïðè ýòîì ÿñíî, ÷òî åñëè
bw � 0 äëÿ íåêîòîðîãî w UV� , òî ze � 0, ãäå { }e w� �( ).
Òåîðåìà 2. Âåêòîð � ( � � ) ÿâëÿåòñÿ áàçîé ðàñøèðåííîãî ïîëèìàòðîèäà
P f f( )*
� òîãäà è òîëüêî òîãäà, êîãäà îãðàíè÷åíèÿ (3), (4) èìåþò ðåøåíèå íà
ãðàôå G.
Äîêàçàòåëüñòâî. Äîïóñòèì, ÷òî îãðàíè÷åíèÿ (3), (4) èìåþò ðåøåíèå íà ãðà-
ôå G. Ïîñêîëüêó bw — öåëîå ÷èñëî äëÿ âñåõ w UV� , èç òåîðèè ëèíåéíîãî ïðî-
ãðàììèðîâàíèÿ ñëåäóåò, ÷òî îãðàíè÷åíèÿ (3), (4) èìåþò öåëî÷èñëåííîå (0 èëè 1)
áàçèñíîå ðåøåíèå z z e Ee� �{ }; . Ðàññìîòðèì ïîäãðàô ñ ìíîæåñòâîì ðåáåð
E e e E ze1 1� � �{ }; , . Òàê êàê b dw w� �1, ñòåïåíè ïðîèçâîëüíûõ âåðøèí w UV�
ïîëó÷åííîãî ïîäãðàôà ðàâíû åäèíèöå. Ñëåäîâàòåëüíî, îí ÿâëÿåòñÿ ñîâåðøåííûì
ïàðîñî÷åòàíèåì è ïî òåîðåìå 1 � � �P f f( )* .
Îáðàòíî, ïóñòü � � �P f f( )* . Òîãäà ñîãëàñíî òåîðåìå 1 â ãðàôå G ñóùåñ-
òâóåò ñîâåðøåííîå ïàðîñî÷åòàíèå M òàêîå, ÷òî ïîñëå óäàëåíèÿ ðåáåð ýòîãî ïà-
ðîñî÷åòàíèÿ èç ãðàôà G â ïîëó÷åííîì ïîäãðàôå ñòåïåíè âñåõ âåðøèí w UV� ðàâ-
íû bw. Ýòî îçíà÷àåò, ÷òî åñëè ïîëîæèòü ze �1 äëÿ âñåõ ðåáåð e E M� \ è ze � 0
äëÿ âñåõ e M� , òî âåêòîð z z e Ee� �{ }; óäîâëåòâîðÿåò îãðàíè÷åíèÿì (3), (4).
Ïî òåîðåìå 2 çàäà÷à ïðèíàäëåæíîñòè âåêòîðà � ê P f f( )*
� ñâîäèòñÿ ê íà-
õîæäåíèþ äîïóñòèìîãî ðåøåíèÿ îãðàíè÷åíèé (3), (4) íà ãðàôå G è ÿâëÿåòñÿ ÷àñ-
òíûì ñëó÷àåì ñëåäóþùåé çàäà÷è íà ãðàôå G:
max
e E
ez
�
� , (5)
z w b w UVw( ( )) ,� � � , (6)
0 1� � �z e Ee , . (7)
Îòìåòèì, ÷òî èç òåîðèè ëèíåéíîãî ïðîãðàììèðîâàíèÿ ÿñíî, ÷òî åñëè ñóùåñ-
òâóåò õîòÿ áû îäíî äîïóñòèìîå ðåøåíèå çàäà÷è (5)–(7), òî îíà èìååò è áàçèñíîå
äîïóñòèìîå ðåøåíèå, ò.å. ze � �0 1. Ïîýòîìó â îãðàíè÷åíèÿõ çàäà÷è óñëîâèå
ze � �0 1 çàìåíåíî óñëîâèÿìè 0 1� �ze äëÿ e E� .
Ëåììà 1. Ïóñòü z z e Ee� �{ }; — îïòèìàëüíîå ðåøåíèå çàäà÷è (5)–(7) è G
— ïîäãðàô, ïîëó÷åííûé óäàëåíèåì èç ãðàôà G âñåõ ðåáåð e, äëÿ êîòîðûõ ze �1.
Òîãäà ïîäãðàô G ñîäåðæèò ïàðîñî÷åòàíèå è ïîäãðàôû òèïà çâåçäû.
Äîêàçàòåëüñòâî. Òàê êàê z — îïòèìàëüíîå ðåøåíèå çàäà÷è (5)–(7), â G íå
ñóùåñòâóåò ðåáðà ( , )u v òàêîãî, ÷òî z u bu( ( ))� � , z v bv( ( ))� � , è zuv � 0. Òîãäà åñëè
z u bu( ( ))� � è z v bv( ( ))� � , ëèáî ðåáðî ( , )u v íå ñîäåðæèòñÿ â G, ëèáî îíî â G ñó-
ùåñòâóåò è zuv �1. Ïîýòîìó â G íå ñóùåñòâóåò ïðîèçâîëüíîãî ðåáðà ( , )u v òàêîãî,
÷òî z u bu( ( ))� � , z v bv( ( ))� � . Ïóñòü ( , )s r — ðåáðà ãðàôà G . Åñëè z s bs( ( ))� � , òî
ëèáî z r br( ( ))� � (â ýòîì ñëó÷àå ( , )s r — ðåáðî ïàðîñî÷åòàíèÿ M â ãðàôå G ), ëèáî
z r br( ( ))� � (â ýòîì ñëó÷àå ( , )s r — ðåáðî íåêîòîðîé çâåçäû â G ).
Èç ëåììû ñëåäóåò, ÷òî çàäà÷à íàõîæäåíèÿ ìàêñèìàëüíîãî ïàðîñî÷åòàíèÿ â
ãðàôå G ñâîäèòñÿ ê òàêîé æå çàäà÷å â G . Ñ ó÷åòîì òîãî, ÷òî ãðàô G ñîäåðæèò ïà-
ðîñî÷åòàíèå è ïîäãðàôû òèïà çâåçäû, ìàêñèìàëüíîå ïàðîñî÷åòàíèå â G ìîæåò
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
îïðåäåëÿòüñÿ çà âðåìÿ O n( ). Ïîýòîìó âðåìåííàÿ ñëîæíîñòü ðåøåíèÿ çàäà÷è íà-
õîæäåíèÿ ìàêñèìàëüíîãî ïàðîñî÷åòàíèÿ â ãðàôå G â îñíîâíîì îïðåäåëÿåòñÿ
òðóäîåìêîñòüþ àëãîðèòìà ðåøåíèÿ çàäà÷è (5)–(7).
 çàêëþ÷åíèå îòìåòèì, ÷òî òåîðåìà 2 ìîæåò áûòü îáîáùåíà íà ñëó÷àé ñó-
ùåñòâîâàíèÿ â ãðàôå G íåïåðåñåêàþùèõñÿ ïî ðåáðàì k ñîâåðøåííûõ ïàðîñî÷åòà-
íèé äëÿ âñåõ 1 � �k dr , ãäå d d w UVr w� �min{ }, . Ðàññìîòðèì îãðàíè÷åíèÿ (3),
(4) íà ãðàôå G ïðè b bw w
k
� , ãäå b d kw
k
w� � äëÿ âñåõ 1 � �k dr è w UV� . Ñ ïî-
ìîùüþ èíäóêöèè ïî k àíàëîãè÷íî äîêàçàòåëüñòâó òåîðåìû 2 ìîæíî äîêàçàòü
ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 3. Â ãðàôå G ñóùåñòâóþò k (1 � �k dr ) íåïåðåñåêàþùèõñÿ ïî ðåá-
ðàì ñîâåðøåííûõ ïàðîñî÷åòàíèé òîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóåò ðåøå-
íèå ñèñòåìû îãðàíè÷åíèé (3), (4) íà ãðàôå G ïðè b bw w
k
� .
Èçâåñòíî, ÷òî ïðè b d kw
k
w� � äëÿ ïðîèçâîëüíîãî 1 � �k dr ñèñòåìà îãðàíè÷å-
íèé (3), (4) èìååò íà ãðàôå G ðåøåíèå òîãäà è òîëüêî òîãäà, êîãäà b A b Nk k A( ) ( )�
äëÿ âñåõ A U� . Èç äàííîé òåîðåìû ñëåäóåò, ÷òî â ãðàôå G ñóùåñòâóåò k íåïåðåñå-
êàþùèõñÿ ïî ðåáðàì ñîâåðøåííûõ ïàðîñî÷åòàíèé òîãäà è òîëüêî òîãäà, êîãäà ýòî
íåðàâåíñòâî âûïîëíÿåòñÿ äëÿ ïðîèçâîëüíîãî A U� .
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. A l t H . , B l u m N . , M e h l h o r n K . , P a u l M . Computing maximum cardinality matching in time
O n m V( / | |).1 5 log // Inform. Processing Letters. — 1991. — 37. — P. 237–240.
2. B u r k a r d R . E . Selected topics on assignment problems // Discrete Appl. Math. — 2002. — 123. —
P. 257–302.
3. B a l i n s k i M . L . Signature methods for the assignment problem // Oper. Res. — 1985. — 33. —
P. 527–536.
4. Ø à ð è ô î â Ô . À . Íàõîæäåíèå ìèíèìàëüíîãî ðàçðåçà ñ èñïîëüçîâàíèåì áàçû ðàñøèðåííîãî
ïîëèìàòðîèäà // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1996. — ¹ 6. — Ñ. 138–152.
5. G r o t s c h e l M . , L o v a s z L . , S c h r i j v e r A . Geometric algorithms and combinatorial optimiza-
tion. — Berlin: Springer, 1988. — 345 p.
Ïîñòóïèëà 18.01.2007
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 179
|
| id | nasplib_isofts_kiev_ua-123456789-72218 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| language | Russian |
| last_indexed | 2025-12-07T13:16:13Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шарифов, Ф.А. 2014-12-19T22:24:13Z 2014-12-19T22:24:13Z 2008 Совершенные паросочетания и расширенный полиматроид / Ф.А. Шарифов // Кибернетика и системный анализ. — 2008. — № 3. — С. 173-179. — Бібліогр.: 5 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/72218 519.8 Зазначено, що у відомих алгоритмах розв'язування задачі про призначення в явному вигляді чи опосередковано використовуються відомі класичні умови існування перфектного паросполучення в дводольному графі. Показано, що кожному дводольному графу можна співставити деякий вектор і розширений поліматроїд таким чином, що даний вектор є базою цього розширеного поліматроїда тоді та тільки тоді, коли даний граф містить перфектие паросполучення. Работа выполнена при частичной финансовой поддержке INTAS, грант 06–1000017–8909. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Совершенные паросочетания и расширенный полиматроид Article published earlier |
| spellingShingle | Совершенные паросочетания и расширенный полиматроид Шарифов, Ф.А. Системный анализ |
| title | Совершенные паросочетания и расширенный полиматроид |
| title_full | Совершенные паросочетания и расширенный полиматроид |
| title_fullStr | Совершенные паросочетания и расширенный полиматроид |
| title_full_unstemmed | Совершенные паросочетания и расширенный полиматроид |
| title_short | Совершенные паросочетания и расширенный полиматроид |
| title_sort | совершенные паросочетания и расширенный полиматроид |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/72218 |
| work_keys_str_mv | AT šarifovfa soveršennyeparosočetaniâirasširennyipolimatroid |