-

, ,
- -
 

: ""

: ""


 

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

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


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


 

- 2009