|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
0
|
|
1
|
1
|
1
|
|
|
|
|
|
|
1
|
-1
|
|
1
|
|
1
|
1
|
1
|
1
|
|
|
2
|
-1
|
-1
|
|
1
|
|
1
|
|
|
|
|
3
|
-1
|
|
-1
|
|
|
-1
|
|
|
1
|
1
|
4
|
|
-1
|
|
|
|
1
|
1
|
|
|
|
5
|
|
-1
|
-1
|
1
|
-1
|
|
1
|
|
1
|
|
6
|
|
-1
|
|
|
-1
|
-1
|
|
|
|
1
|
7
|
|
-1
|
|
|
|
|
|
|
1
|
1
|
8
|
|
|
|
-1
|
|
-1
|
|
-1
|
|
1
|
9
|
|
|
|
-1
|
|
|
-1
|
-1
|
-1
|
|
Çàäà÷à
2 Íàéòè
äèàìåòð D(G),
ðàäèóñ R(G),
êîëè÷åñòâî
öåíòðîâ Z(G) äëÿ
ãðàôà G ;
óêàçàòü
âåðøèíû,
ÿâëÿþùèåñÿ
öåíòðàìè
ãðàôà G.
D(G)=2
R(G)=2
Z(G)=10
Âñå
âåðøèíû
ãðàôà G(V,X)
ÿâëÿþòñÿ
öåíòðàìè.
Çàäà÷à
3 Ïåðåíóìåðîâàòü
âåðøèíû
ãðàôà G,
èñïîëüçóÿ àëãîðèòìû:
à) "ïîèñêà
â ãëóáèíó";
á) "ïîèñêà
â øèðèíó".
Èñõîäíàÿ
âåðøèíà - .
à)
á)
Çàäà÷à
4 Èñïîëüçóÿ
àëãîðèòì
Ïðèìà íàéòè
îñòîâ ìèíèìàëüíîãî
âåñà ãðàôà G.
âûïèñàòü êîä
óêëàäêè íà
ïëîñêîñòè
íàéäåííîãî
äåðåâà, ïðèíÿâ
çà êîðíåâóþ
âåðøèíó .
Âåñ
íàéäåííîãî
äåðåâà - 14.
Êîä
óêëàäêè
äåðåâà: 000011000001111111.
Çàäà÷à
5 Èñïîëüçóÿ
àëãîðèòì
Äåéêñòðà
íàéòè äåðâî
êðàò÷àéøèõ
ïóòåé èç
âåðøèíû ãðàôà G.
Âåñ
íàéäåííîãî
ïóòè - 8.
Çàäà÷à
6 Èñïîëüçóÿ
àëãîðèòì
Ôîðäà -
Ôàëêåðñîíà,
íàéòè
ìàêñèìàëüíûé
ïîòîê âî
âçâåøåííîé
äâóïîëþñíîé
îðèåíòèðîâàííîé
ñåòè {Gîð , , w}.
Óêàçàòü
ðàçðåç
ìèíèìàëüíîãî
âåñà.
Ïîñëåäîâàòåëüíîñòü
íàñûùåíèÿ
ñåòè (íàñûùåííûå
ðåáðà
îòìå÷åíû
êðóæå÷êàìè):
1-é
øàã
2-é
øàã
3-é
øàã
4-é
øàã
5-é
øàã
6-é
øàã
7-é
øàã
Îêîí÷àòåëüíî
èìååì:
Êàê
âèäíî èç
ðèñóíêà,
ðåáðà {6,9},{7,9},{3,9},
ïèòàþùèå âåðøèíó
, íàñûùåííû,
à
îñòàâøååñÿ
ðåáðî {8,9},
ïèòàþùååñÿ
îò âåðøèíû 8,
íå ìîæåò ïîëó÷èòü
áîëüøåå
çíà÷åíèå
âåñîâîé
ôóíêöèè, òàê
êàê
íàñûùåííû
âñå ðåáðà,
ïèòàþùèå âåðøèíó
8. Äðóãèìè
ñëîâàìè -
åñëè
îòáðîñèòü âñå
íàñûùåííûå
ðåáðà, òî
âåðøèíà íåäîñòèæèìà,
÷òî ÿâëÿåòñÿ
ïðèçíàêîì
ìàêñèìàëüíîãî
ïîòîêà â
ñåòè.
Ìàêñèìàëüíûé
ïîòîê â ñåòè
ðàâåí 12.
Ìèíèìàëüíûé
ðàçðåç ñåòè
ïî ÷èñëó
ðåáåð: {{0,1},{0,2},{0,3}}. Åãî
ïðîïóñêíàÿ
ñïîñîáíîñòü
ðàâíà 16
Ìèíèìàëüíûé
ðàçðåç ñåòè
ïî
ïðîïóñêíîé ñïîñîáíîñòè:
{{6,9}, {7,9}, {3,9}, {3,8}, {5,8}, {7,8}}. Åãî
ïðîïóñêíàÿ
ñïîñîáíîñòü
ðàâíà 12.
Çàäà÷à
7 (Çàäà÷à î
ïî÷òàëüîíå)
Âûïèñàòü
ñòåïåííóþ
ïîñëåäîâàòåëüíîñòü
âåðøèí
ãðàôà G.
à)
Óêàçàòü â
ãðàôå G
Ýéëåðîâó
öåïü. Åñëè
òàêîâîé
öåïè íå
ñóùåñòâóåò,
òî â ãðàôå G
äîáàâèòü
íàèìåíüøåå
÷èñëî ðåáåð
òàêèì
îáðàçîì,
÷òîáû â
íîâîì ãðàôå
ìîæíî áûëî
óêàçàòü Ýéëåðîâó
öåïü.
á)
Óêàçàòü â
ãðàôå G
Ýéëåðîâ öèêë.
Åñëè òàêîãî
öèêëà íå
ñóùåñòâóåò,
òî â ãðàôå G
äîáàâèòü
íàèìåíüøåå
÷èñëî ðåáåð
òàêèì
îáðàçîì,
÷òîáû â
íîâîì ãðàôå
ìîæíî áûëî
óêàçàòü Ýéëåðîâ
öèêë.
Ñòåïåííàÿ
ïîñëåäîâàòåëüíîñòü
âåðøèí ãðàôà
G:
(3,6,4,5,3,6,4,3,4,4)
à) Äëÿ
ñóùåñòâîâàíèÿ
Ýéëåðîâîé
öåïè äîïóñòèìî
òîëüêî äâå
âåðøèíû ñ
íå÷åòíûìè
ñòåïåíÿìè,
ïîýòîìó
íåîáõîäèìî
äîáàâèòü
îäíî ðåáðî,
ñêàæåì
ìåæäó
âåðøèíàìè 4 è
7.
Ïîëó÷åííàÿ
Ýéëåðîâà
öåïü: 0,3,2,0,1,2,5,1,4,5,6,1,7,4,6,9,7,8,9,3,8,5,3.
Ñõåìà
Ýéëåðîâîé
öåïè
(äîáàâëåííîå
ðåáðî ïîêàçàíî
ïóíêòèðîì):
á) Àíàëîãè÷íî
ïóíêòó à)
äîáàâëÿåì
ðåáðî {3,0}, çàìûêàÿ
Ýéëåðîâó
öåïü (ïðè ýòîì
âûïîëíÿÿ óñëîâèå
ñóùåñòâîâàíèÿ
Ýéëåðîâà
öèêëà - ÷åòíîñòü
ñòåïåíåé âñåõ
âåðøèí). Ðåáðî
{3,0} êðàòíîå,
÷òî íå
ïðîòèâîðå÷èò
çàäàíèþ, íî
ïðè
íåîáõîäèìîñòè
ìîæíî
ââåñòè ðåáðà
{0,7} è {4,3} âìåñòî
ðàíåå
ââåäåííûõ.
Ïîëó÷åííûé
Ýéëåðîâ öèêë:
0,3,2,0,1,2,5,1,4,5,6,1,7,4,6,9,7,8,9,3,8,5,3,0.
Ñõåìà
Ýéëåðîâà
öèêëà
(äîáàâëåííûå
ðåáðà ïîêàçàíû
ïóíêòèðîì):
Çàäà÷à
8
à)
Óêàçàòü â
ãðàôå Gîð
Ãàìèëüòîíîâ
ïóòü. Åñëè
òàêîé ïóòü
íå ñóùåñòâóåò,
òî â ãðàôå Gîð
èçìåíèòü
îðèåíòàöèþ
íàèìåíüøåãî
÷èñëà ðåáåð
òàêèì
îáðàçîì,
÷òîáû â
íîâîì ãðàôå
Ãàìèëüòîíîâ
ïóòü ìîæíî
áûëî
óêàçàòü.
á)
Óêàçàòü â
ãðàôå Gîð
Ãàìèëüòîíîâ
öèêë. Åñëè
òàêîé öèêë
íå ñóùåñòâóåò,
òî â ãðàôå Gîð
èçìåíèòü
îðèåíòàöèþ
íàèìåíüøåãî
÷èñëà ðåáåð
òàêèì
îáðàçîì,
÷òîáû â
íîâîì ãðàôå
Ãàìèëüòîíîâ
öèêë ìîæíî
áûëî
óêàçàòü.
à) Ãàìèëüòîíîâ
ïóòü (ðåáðà ñ
èçìåíåííîé
îðèåíòàöèåé
ïîêàçàíû
ïóíêòèðîì):
á) Ãàìèëüòîíîâ
öèêë (ðåáðà ñ
èçìåíåííîé
îðèåíòàöèåé
ïîêàçàíû
ïóíêòèðîì):
Çàäà÷à
9 (Çàäà÷à î
êîììèâîÿæåðå)
Äàí ïîëíûé
îðèåíòèðîâàííûé
ñèììåòðè÷åñêèé
ãðàô ñ
âåðøèíàìè x1, x2,...xn.Âåñ
äóãè xixj
çàäàí
ýëåìåíòàìè Vij
ìàòðèöû
âåñîâ.
Èñïîëüçóÿ
àëãîðèòì
ìåòîäà
âåòâåé è
ãðàíèö,
íàéòè
Ãàìèëüòîíîâ
êîíòóð
ìèíèìàëüíîãî
(ìàêñèìàëüíîãî)
âåñà. Çàäà÷ó
íà
ìàêñèìàëüíîå
çíà÷åíèå
Ãàìèëüòîíîâà
êîíòóðà
ñâåñòè ê
çàäà÷å íà
ìèíèìàëüíîå
çíà÷åíèå,
ðàññìîòðåâ
ìàòðèöó ñ ýëåìåíòàìè
,ãäå
.
Âûïîëíèòü
ðèñóíîê.
Èñõîäíàÿ
òàáëèöà.
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
|
x1
|
|
3
|
7
|
2
|
|
11
|
|
x2
|
8
|
|
06
|
|
4
|
3
|
|
x3
|
6
|
05
|
|
7
|
|
2
|
|
x4
|
6
|
|
13
|
|
5
|
|
|
x5
|
3
|
3
|
3
|
4
|
|
5
|
|
x6
|
8
|
6
|
|
2
|
2
|
|
|
|
|
|
|
|
|
|
|
Òàáëèöà Å 14
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
|
x1
|
|
1
|
5
|
01
|
|
7
|
2
|
x2
|
8
|
|
01
|
|
4
|
1
|
|
x3
|
6
|
00
|
|
7
|
|
00
|
|
x4
|
1
|
|
8
|
|
01
|
|
5
|
x5
|
01
|
00
|
00
|
1
|
|
00
|
3
|
x6
|
6
|
4
|
|
00
|
00
|
|
2
|
|
|
|
|
|
|
2
|
|
Äðîáèì ïî
ïåðåõîäó x2-x3:
Òàáëèöà 23 =14+0=14
|
x1
|
x2
|
x4
|
x5
|
x6
|
|
x1
|
|
1
|
01
|
|
7
|
|
x3
|
6
|
|
7
|
|
06
|
|
x4
|
1
|
|
|
01
|
|
|
x5
|
01
|
01
|
1
|
|
00
|
|
x6
|
6
|
4
|
00
|
00
|
|
|
|
|
|
|
|
|
|
Òàáëèöà 23 =14+1=15
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
|
x1
|
|
1
|
5
|
01
|
|
7
|
|
x2
|
7
|
|
|
|
3
|
03
|
1
|
x3
|
6
|
00
|
|
7
|
|
00
|
|
x4
|
1
|
|
8
|
|
01
|
|
|
x5
|
01
|
00
|
05
|
1
|
|
00
|
|
x6
|
6
|
4
|
|
00
|
00
|
|
|
|
|
|
|
|
|
|
|
Ïðîäîëæàåì
ïî 23.
Äðîáèì ïî
ïåðåõîäó x3-x6:
Òàáëèöà 23E36 =14+0=14
|
x1
|
x2
|
x4
|
x5
|
|
x1
|
|
1
|
01
|
|
|
x4
|
1
|
|
|
01
|
|
x5
|
01
|
01
|
1
|
|
|
x6
|
6
|
|
00
|
00
|
|
|
|
|
|
|
|
Òàáëèöà 2336 =14+6=20
|
x1
|
x2
|
x4
|
x5
|
x6
|
|
x1
|
|
1
|
01
|
|
7
|
|
x3
|
01
|
|
1
|
|
|
6
|
x4
|
1
|
|
|
01
|
|
|
x5
|
00
|
01
|
1
|
|
07
|
|
x6
|
6
|
4
|
00
|
00
|
|
|
|
|
|
|
|
|
|
Ïðîäîëæàåì
ïî 2336.
Äðîáèì ïî
ïåðåõîäó x4-x5:
Òàáëèöà 23E3645 =14+0=14
|
x1
|
x2
|
x4
|
|
x1
|
|
1
|
01
|
|
x5
|
01
|
01
|
1
|
|
x6
|
6
|
|
00
|
|
|
|
|
|
|
Òàáëèöà 233645 =14+1=15
|
x1
|
x2
|
x4
|
x5
|
|
x1
|
|
1
|
01
|
|
|
x4
|
00
|
|
|
|
1
|
x5
|
01
|
01
|
1
|
|
|
x6
|
6
|
|
00
|
00
|
|
|
|
|
|
|
|
Ïðîäîëæàåì
ïî 233645.
Äðîáèì ïî
ïåðåõîäó x5-x1:
Òàáëèöà 23364551 =14+1=15
|
x2
|
x4
|
|
x1
|
1
|
|
1
|
x6
|
|
00
|
|
|
|
|
|
Òàáëèöà 23364551 =14+6=20
|
x1
|
x2
|
x4
|
|
x1
|
|
1
|
01
|
|
x5
|
|
01
|
|
|
x6
|
0
|
|
00
|
|
|
6
|
|
|
|
Îêîí÷àòåëüíî
èìååì
Ãàìèëüòîíîâ
êîíòóð: 2,3,6,4,5,1,2.
Ïðàäåðåâî
ðàçáèåíèé:
Çàäà÷à
10 (Çàäà÷à î
íàçíà÷åíèÿõ)
Äàí ïîëíûé
äâóäîëüíûé
ãðàô Knn ñ
âåðøèíàìè
ïåðâîé äîëè x1, x2,...xn.è
âåðøèíàìè
äðóãîé äîëè y1, y2,...yn..Âåñ
ðåáðà {xi,yj}
çàäàåòñÿ
ýëåìåíòàìè vij
ìàòðèöû
âåñîâ.
Èñïîëüçóÿ
âåíãåðñêèé
àëãîðèòì,
íàéòè
ñîâåðøåííîå
ïàðîñî÷åòàíèå
ìèíèìàëüíîãî
(ìàêñèìàëüíîãî
âåñà). Âûïîëíèòü
ðèñóíîê.
Ìàòðèöà
âåñîâ
äâóäîëüíîãî
ãðàôà K55 :
|
y1
|
y2
|
y3
|
y4
|
y5
|
x1
|
2
|
0
|
0
|
0
|
0
|
x2
|
0
|
7
|
9
|
8
|
6
|
x3
|
0
|
1
|
3
|
2
|
2
|
x4
|
0
|
8
|
7
|
6
|
4
|
x5
|
0
|
7
|
6
|
3
|
Ïåðâûé
ýòàï -
ïîëó÷åíèå
íóëåé íå
íóæåí, ò. ê. íóëè
óæå åñòü âî
âñåõ ñòðîê è
ñòîëáöàõ.
Âòîðîé
ýòàï -
íàõîæäåíèå
ïîëíîãî
ïàðîñî÷åòàíèÿ.
|
y1
|
y2
|
y3
|
y4
|
y5
|
x1
|
2
|
0
|
0
|
0
|
0
|
x2
|
0
|
7
|
9
|
8
|
6
|
x3
|
0
|
1
|
3
|
2
|
2
|
x4
|
0
|
8
|
7
|
6
|
4
|
x5
|
0
|
7
|
6
|
8
|
3
|
Òðåòèé
ýòàï -
íàõîæäåíèå
ìàêñèìàëüíîãî
ïàðîñî÷åòàíèÿ.
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
2
|
0
|
0
|
0
|
0
|
X
|
x2
|
0
|
7
|
9
|
8
|
6
|
X
|
x3
|
0
|
1
|
3
|
2
|
2
|
|
x4
|
0
|
8
|
7
|
6
|
4
|
|
x5
|
0
|
7
|
6
|
8
|
3
|
|
|
X
|
X
|
|
|
|
|
×åòâåðòûé
ýòàï -
íàõîæäåíèå
ìèíèìàëüíîé
îïîðû.
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
2
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
7
|
9
|
8
|
6
|
5
|
x3
|
0
|
1
|
3
|
2
|
2
|
1
|
x4
|
0
|
8
|
7
|
6
|
4
|
2
|
x5
|
0
|
7
|
6
|
8
|
3
|
3
|
|
4
|
|
|
|
|
|
Ïÿòûé
ýòàï -
âîçìîæíàÿ
ïåðåñòàíîâêà
íåêîòîðûõ
íóëåé.
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
3
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
6
|
8
|
7
|
5
|
5
|
x3
|
0
|
0
|
2
|
1
|
1
|
x4
|
0
|
7
|
6
|
5
|
3
|
2
|
x5
|
0
|
6
|
5
|
7
|
2
|
3
|
|
4
|
|
|
|
|
|
Ðåøåíèå
ñ íåíóëåâûì
çíà÷åíèåì.
Ïåðåõîä êî
âòîðîìó
ýòàïó.
Ïîëíîå
ïàðîñî÷åòàíèå:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
3
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
6
|
8
|
7
|
5
|
|
x3
|
0
|
0
|
2
|
1
|
1
|
|
x4
|
0
|
7
|
6
|
5
|
3
|
|
x5
|
0
|
6
|
5
|
7
|
2
|
|
|
|
|
|
|
|
|
Ìàêñèìàëüíîå
ïàðîñî÷åòàíèå:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
3
|
0
|
0
|
0
|
0
|
X
|
x2
|
0
|
6
|
8
|
7
|
5
|
X
|
x3
|
0
|
0
|
2
|
1
|
1
|
|
x4
|
0
|
7
|
6
|
5
|
3
|
|
x5
|
0
|
6
|
5
|
7
|
2
|
|
|
X
|
X
|
|
|
|
|
Ìèíèìàëüíàÿ
îïîðà:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
3
|
0
|
0
|
0
|
0
|
6
|
x2
|
0
|
6
|
8
|
7
|
5
|
7
|
x3
|
0
|
0
|
2
|
1
|
1
|
1
|
x4
|
0
|
7
|
6
|
5
|
3
|
2
|
x5
|
0
|
6
|
5
|
7
|
3
|
|
4
|
5
|
|
|
|
|
Ïåðåñòàíîâêà
íóëåé:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
3
|
0
|
0
|
0
|
0
|
6
|
x2
|
0
|
6
|
8
|
7
|
5
|
7
|
x3
|
0
|
0
|
2
|
1
|
1
|
1
|
x4
|
0
|
7
|
6
|
5
|
3
|
2
|
x5
|
0
|
6
|
5
|
7
|
2
|
3
|
|
4
|
5
|
|
|
|
|
Ïîëíîå
ïàðîñî÷åòàíèå:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
3
|
0
|
0
|
0
|
0
|
6
|
x2
|
0
|
6
|
8
|
7
|
5
|
7
|
x3
|
0
|
0
|
2
|
1
|
1
|
1
|
x4
|
0
|
7
|
6
|
5
|
3
|
2
|
x5
|
0
|
6
|
5
|
7
|
2
|
3
|
|
4
|
5
|
|
|
|
|
Ìàêñèìàëüíîå
ïàðîñî÷åòàíèå:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
3
|
0
|
0
|
0
|
0
|
X
|
x2
|
0
|
6
|
8
|
7
|
5
|
|
x3
|
0
|
0
|
2
|
1
|
1
|
X
|
x4
|
0
|
7
|
6
|
5
|
3
|
X
|
x5
|
0
|
6
|
5
|
7
|
2
|
|
|
X
|
X
|
X
|
|
|
|
Ìèíèìàëüíàÿ
îïîðà:
|
y1
|
y2
|
y3
|
y5
|
|
x1
|
3
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
6
|
8
|
7
|
5
|
1
|
x3
|
0
|
0
|
2
|
1
|
1
|
|
x4
|
0
|
7
|
6
|
5
|
3
|
|
x5
|
0
|
6
|
5
|
7
|
2
|
2
|
|
3
|
|
|
|
|
|
Ïåðåñòàíîâêà
íóëåé:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
5
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
4
|
6
|
5
|
3
|
1
|
x3
|
2
|
0
|
2
|
1
|
1
|
|
x4
|
2
|
7
|
6
|
5
|
3
|
|
x5
|
0
|
4
|
3
|
5
|
0
|
2
|
|
3
|
|
|
|
|
|
Ïîëíîå
ïàðîñî÷åòàíèå:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
5
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
4
|
6
|
5
|
3
|
|
x3
|
2
|
0
|
2
|
1
|
1
|
|
x4
|
2
|
7
|
6
|
5
|
3
|
|
x5
|
0
|
4
|
3
|
5
|
0
|
|
|
|
|
|
|
|
|
Ìàêñèìàëüíîå
ïàðîñî÷åòàíèå:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
5
|
0
|
0
|
0
|
0
|
X
|
x2
|
0
|
4
|
6
|
5
|
3
|
X
|
x3
|
2
|
0
|
2
|
1
|
1
|
X
|
x4
|
2
|
7
|
6
|
5
|
3
|
|
x5
|
0
|
4
|
3
|
5
|
0
|
X
|
|
X
|
X
|
X
|
|
X
|
|
Ìèíèìàëüíàÿ
îïîðà:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
5
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
4
|
6
|
5
|
3
|
|
x3
|
2
|
0
|
2
|
1
|
1
|
|
x4
|
2
|
7
|
6
|
5
|
3
|
1
|
x5
|
0
|
4
|
3
|
5
|
0
|
|
|
|
|
|
|
|
|
Ïåðåñòàíîâêà
íóëåé:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
5
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
4
|
6
|
5
|
3
|
|
x3
|
2
|
0
|
2
|
1
|
1
|
|
x4
|
0
|
5
|
4
|
3
|
1
|
1
|
x5
|
0
|
4
|
3
|
5
|
0
|
|
|
|
|
|
|
|
|
Ïîëíîå
ïàðîñî÷åòàíèå:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
5
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
4
|
6
|
5
|
3
|
|
x3
|
2
|
0
|
2
|
1
|
1
|
|
x4
|
0
|
5
|
4
|
3
|
1
|
1
|
x5
|
0
|
4
|
3
|
5
|
0
|
|
|
|
|
|
|
|
|
Ìàêñèìàëüíîå
ïàðîñî÷åòàíèå:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
5
|
0
|
0
|
0
|
0
|
X
|
x2
|
0
|
4
|
6
|
5
|
3
|
X
|
x3
|
2
|
0
|
2
|
1
|
1
|
X
|
x4
|
0
|
5
|
4
|
3
|
1
|
|
x5
|
0
|
4
|
3
|
5
|
0
|
X
|
|
X
|
X
|
X
|
|
X
|
|
Ìèíèìàëüíàÿ
îïîðà:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
5
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
4
|
6
|
5
|
3
|
3
|
x3
|
2
|
0
|
2
|
1
|
1
|
|
x4
|
0
|
5
|
4
|
3
|
1
|
1
|
x5
|
0
|
4
|
3
|
5
|
0
|
|
|
2
|
|
|
|
|
|
Ïåðåñòàíîâêà
íóëåé:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
6
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
3
|
5
|
4
|
2
|
3
|
x3
|
3
|
0
|
2
|
1
|
1
|
|
x4
|
0
|
4
|
3
|
2
|
0
|
1
|
x5
|
1
|
4
|
3
|
5
|
0
|
|
|
2
|
|
|
|
|
|
Ïîëíîå
ïàðîñî÷åòàíèå:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
6
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
3
|
5
|
4
|
2
|
3
|
x3
|
3
|
0
|
2
|
1
|
1
|
|
x4
|
0
|
4
|
3
|
2
|
0
|
1
|
x5
|
1
|
4
|
3
|
5
|
0
|
|
|
2
|
|
|
|
|
|
Ìàêñèìàëüíîå
ïàðîñî÷åòàíèå:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
6
|
0
|
0
|
0
|
0
|
X
|
x2
|
0
|
3
|
5
|
4
|
2
|
X
|
x3
|
3
|
0
|
2
|
1
|
1
|
X
|
x4
|
0
|
4
|
3
|
2
|
0
|
|
x5
|
1
|
4
|
3
|
5
|
0
|
X
|
|
X
|
X
|
X
|
|
X
|
|
Ìèíèìàëüíàÿ
îïîðà:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
6
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
3
|
5
|
4
|
2
|
4
|
x3
|
3
|
0
|
2
|
1
|
1
|
|
x4
|
0
|
4
|
3
|
2
|
0
|
1
|
x5
|
1
|
4
|
3
|
5
|
0
|
5
|
|
2
|
|
|
|
3
|
|
Â
ðåçóëüòàòå
èìååì:
|
y1
|
y2
|
y3
|
y4
|
y5
|
|
x1
|
6
|
0
|
0
|
0
|
0
|
|
x2
|
0
|
1
|
3
|
2
|
2
|
4
|
x3
|
3
|
0
|
2
|
1
|
1
|
|
x4
|
0
|
2
|
1
|
0
|
0
|
1
|
x5
|
1
|
4
|
3
|
5
|
0
|
5
|
|
2
|
|
|
|
3
|
|
Èñõîäíûé
ãðàô
Ïîëó÷åííûé
ãðàô:
Âåñ
íàéäåííîãî
ñîâåðøåííîãî
ïàðîñî÷åòàíèÿ
= 12.
Çàäà÷à
11 Ðåøèòü
çàäà÷ó 10,
èñïîëüçóÿ
àëãîðèòì
âåòâåé è
ãðàíèö
(îòîæäåñòâèâ
âåðøèíû xi è yj).
Òàáëèöà
Å (èñõîäíàÿ).
Ñòðîêè - xi ,
ñòîëáöû - yj. =0
|
1
|
2
|
3
|
4
|
5
|
|
1
|
2
|
01
|
03
|
02
|
02
|
|
2
|
06
|
7
|
9
|
8
|
6
|
|
3
|
01
|
1
|
3
|
2
|
2
|
|
4
|
04
|
8
|
7
|
6
|
4
|
|
5
|
03
|
7
|
6
|
8
|
3
|
|
|
|
|
|
|
|
|
Äðîáèì
ïî ïåðåõîäó x2 - y1:
Òàáëèöà
Å21 =0+8=8
|
2
|
3
|
4
|
5
|
|
1
|
00
|
02
|
01
|
00
|
|
3
|
01
|
2
|
1
|
1
|
1
|
4
|
4
|
3
|
2
|
02
|
4
|
5
|
4
|
3
|
5
|
03
|
3
|
|
|
|
|
|
|
Òàáëèöà
21 =0+6=6
|
1
|
2
|
3
|
4
|
5
|
|
1
|
2
|
01
|
03
|
02
|
00
|
|
2
|
|
1
|
3
|
2
|
01
|
6
|
3
|
01
|
1
|
3
|
2
|
2
|
|
4
|
04
|
8
|
7
|
6
|
4
|
|
5
|
03
|
7
|
6
|
8
|
3
|
|
|
|
|
|
|
|
|
Ïðîäîëæàåì
ïî 21:
Äðîáèì
ïî ïåðåõîäó x4 - y1:
Òàáëèöà
21Å41 =6+4=10
|
2
|
3
|
4
|
5
|
|
1
|
00
|
02
|
01
|
00
|
|
2
|
1
|
3
|
2
|
01
|
|
3
|
01
|
2
|
1
|
1
|
1
|
5
|
4
|
3
|
5
|
03
|
3
|
|
|
|
|
|
|
Òàáëèöà
2141 =6+4=10
|
1
|
2
|
3
|
4
|
5
|
|
1
|
2
|
01
|
03
|
02
|
00
|
|
2
|
|
1
|
3
|
2
|
01
|
|
3
|
01
|
1
|
3
|
2
|
2
|
|
4
|
|
4
|
3
|
2
|
02
|
4
|
5
|
03
|
7
|
6
|
8
|
3
|
|
|
|
|
|
|
|
|
Ïðîäîëæàåì
ïî Å21:
Äðîáèì
ïî ïåðåõîäó x5 - y5:
Òàáëèöà
Å21Å55 =8+2=10
|
2
|
3
|
4
|
|
1
|
00
|
01
|
00
|
|
3
|
01
|
2
|
1
|
|
4
|
2
|
1
|
01
|
2
|
|
|
|
|
|
Òàáëèöà
Å2155 =8+3=11
|
2
|
3
|
4
|
5
|
|
1
|
00
|
02
|
01
|
00
|
|
3
|
01
|
2
|
1
|
1
|
|
4
|
4
|
3
|
2
|
02
|
|
5
|
1
|
01
|
2
|
|
3
|
|
|
|
|
|
Ïðîäîëæàåì
ïî Å21Å55:
Äðîáèì
ïî ïåðåõîäó x3 - y2:
Òàáëèöà
Å21Å55Å32 =10+0=10
|
3
|
4
|
|
1
|
01
|
00
|
|
4
|
1
|
01
|
|
|
|
|
|
Äàëåå
ðåøåíèå
î÷åâèäíî: x1 - y3 è x4 - y4.
Ýòî íå
óâåëè÷èò
îöåíêó.
Â
èòîãå èìååì
ñîâåðøåííîå
ïàðîñî÷åòàíèå
ñ
ìèíèìàëüíûì
âåñîì:
Ïðàäåðåâî
ðàçáèåíèé: