Áîëüøàÿ êîëëåêöèÿ ðåôåðàòîâ

Ãëàâíàÿ Êîíòàêòû
Ãëàâíîå ìåíþ Ãëàâíàÿ Àñòðîíîìèÿ è êîñìîíàâòèêà Àêöèîíåðíîå ïðàâî Àíãëèéñêèé Àíòèêðèçèñíûé ìåíåäæìåíò Àðáèòðàæíûé ïðîöåññ Àðõèòåêòóðà Àóäèò Ãåîãðàôèÿ è ýêîíîìè÷åñêàÿ ãåîãðàôèÿ Ãåîëîãèÿ ãèäðîëîãèÿ è ãåîäåçèÿ Ìåæäóíàðîäíîå ïóáëè÷íîå ïðàâî Ìåæäóíàðîäíîå ÷àñòíîå ïðàâî Ìåæäóíàðîäíûå îòíîøåíèÿ Íîâåéøàÿ èñòîðèÿ ïîëèòîëîãèÿ Îñòàëüíûå ðåôåðàòû Ïðîìûøëåííîñòü ïðîèçâîäñòâî Þðèñïðóäåíöèÿ Ðåêëàìà Ñ÷åò÷èêè Îïðîñû Îöåíèòå íàø ñàéò? Õîðîøî Îòëè÷íî Ïîëåçíî áûëî ïîñåòèòü Äîáàâèë â çàêëàäêè Åùå çàéäó íå ðàç Òåïåðü ÿ çäåñü ïîñòîÿííûé Äèñêðåòíàÿ ìàòåìàòèêà: "Ãðàôû" Äèñêðåòíàÿ ìàòåìàòèêà: "Ãðàôû"   Gîð(V,X)   Ðèñ. 1             Çàäà÷à1          Äëÿ íåîðèåíòèðîâàííîãî ãðàôà G, àññîöèèðîâàííîãî ñ ãðàôîì Gîð âûïèñàòü (ïåðåíóìåðîâàâ âåðøèíû) : à) ìíîæåñòâî âåðøèí V è ìíîæåñòâî ðåáåð X, G(V,X); á) ñïèñêè ñìåæíîñòè; â) ìàòðèöó èíöèäåíòíîñòè; ã) ìàòðèöó âåñîâ. ä) Äëÿ ãðàôà Gîð âûïèñàòü ìàòðèöó ñìåæíîñòè.             Íóìåðàöèÿ âåðøèí - ñì. Ðèñ 1 à)         V={0,1,2,3,4,5,6,7,8,9}             X={{0,1},{0,2},{0,3},{1,2},{1,4},{1,5},{1,6},{1,7},{2,3},{2,5},{3,8},{3,9},{4,5},{4,6},{5,3},{5,6},{5,8},{6,9},{7,8},{7,9},{8,9}}              äàëüíåéøåì ðåáðà áóäóò îáîçíà÷àòüñÿ íîìåðàìè â óêàçàííîì ïîðÿäêå íà÷èíàÿ ñ íóëÿ. á)         Ã0={1,2,3};             Ã1={0,2,4,5,6,7};             Ã2={0,1,3,5};             Ã3={0,2,5,8,9};             Ã4={1,5,6};             Ã5={1,2,3,4,6,8};             Ã6={1,4,5,9};             Ã7={1,8,9};             Ã8={1,3,5,7,9};             Ã9={3,6,7,8}; â)         Íóìåðàöèÿ âåðøèí è ðåáåð ñîîòâåòñòâåííî ï. à)   0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 3 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 4 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 5 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 6 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 7 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 9 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 ã)         Ïîêàçàíà âåðõíÿÿ ïîëîâèíà ìàòðèöû, ò.ê. ìàòðèöà âåñîâ íåîðèåíòèðîâàííîãî ãðàôà ñèììåòðè÷íà îòíîñèòåëüíî ãëàâíîé äèàãîíàëè.   0 1 2 3 4 5 6 7 8 9 0 8 3 5 1   1 2 2 4 5 2     2 5 3       1 1 6 4         4 2 5           2 1 6             2 7               1 1 8                 6 9                   ä)         Ìàòðèöà ñìåæíîñòè äëÿ ãðàôà Gîð.   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

8

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

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

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

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

y4

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. Ýòî íå óâåëè÷èò îöåíêó.

             èòîãå èìååì ñîâåðøåííîå ïàðîñî÷åòàíèå ñ ìèíèìàëüíûì âåñîì:

            Ïðàäåðåâî ðàçáèåíèé:

Âñå ïðàâà çàùèùåíû © 2010