Дискретная математика: 'Графы'

Дискретная математика: 'Графы'

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         (Çàäà÷à î êîììèâîÿæåðå) Äàí ïîëíûé îðèåíòèðîâàííûé ñèììåòðè÷åñêèé ãðàô  ñ âåðøèíàìè x₁, x₂,...x_n.Âåñ äóãè x_ix_j çàäàí ýëåìåíòàìè V_ij ìàòðèöû âåñîâ. Èñïîëüçóÿ àëãîðèòì ìåòîäà âåòâåé è ãðàíèö, íàéòè Ãàìèëüòîíîâ êîíòóð ìèíèìàëüíîãî (ìàêñèìàëüíîãî) âåñà. Çàäà÷ó íà ìàêñèìàëüíîå çíà÷åíèå Ãàìèëüòîíîâà êîíòóðà ñâåñòè ê çàäà÷å íà ìèíèìàëüíîå çíà÷åíèå, ðàññìîòðåâ ìàòðèöó ñ ýëåìåíòàìè ,ãäå . Âûïîëíèòü ðèñóíîê.

Èñõîäíàÿ òàáëèöà.

x₁

x₂

x₃

x₄

x₅

x₆

x₁

3

7

2

11

x₂

8

0⁶

4

3

x₃

6

0⁵

7

2

x₄

6

13

5

x₅

3

3

3

4

5

x₆

8

6

2

2

Òàáëèöà Å       14

x₁

x₂

x₃

x₄

x₅

x₆

x₁

1

5

0¹

7

2

x₂

8

0¹

4

1

x₃

6

0⁰

7

0⁰

x₄

1

8

0¹

5

x₅

0¹

0⁰

0⁰

1

0⁰

3

x₆

6

4

0⁰

0⁰

2

2

Äðîáèì ïî ïåðåõîäó x₂-x₃:

Òàáëèöà 23  =14+0=14

x₁

x₂

x₄

x₅

x₆

x₁

1

0¹

7

x₃

6

7

0⁶

x₄

1

0¹

x₅

0¹

0¹

1

0⁰

x₆

6

4

0⁰

0⁰

Òàáëèöà 23  =14+1=15

x₁

x₂

x₃

x₄

x₅

x₆

x₁

1

5

0¹

7

x₂

7

3

0³

1

x₃

6

0⁰

7

0⁰

x₄

1

8

0¹

x₅

0¹

0⁰

0⁵

1

0⁰

x₆

6

4

0⁰

0⁰

Ïðîäîëæàåì ïî 23. Äðîáèì ïî ïåðåõîäó x₃-x₆:

Òàáëèöà 23E36        =14+0=14

x₁

x₂

x₄

x₅

x₁

1

0¹

x₄

1

0¹

x₅

0¹

0¹

1

x₆

6

0⁰

0⁰

Òàáëèöà 2336       =14+6=20

x₁

x₂

x₄

x₅

x₆

x₁

1

0¹

7

x₃

0¹

1

6

x₄

1

0¹

x₅

0⁰

0¹

1

0⁷

x₆

6

4

0⁰

0⁰

Ïðîäîëæàåì ïî 2336. Äðîáèì ïî ïåðåõîäó x₄-x₅:

Òàáëèöà 23E3645 =14+0=14

x₁

x₂

x₄

x₁

1

0¹

x₅

0¹

0¹

1

x₆

6

0⁰

Òàáëèöà 233645            =14+1=15

x₁

x₂

x₄

x₅

x₁

1

0¹

x₄

0⁰

1

x₅

0¹

0¹

1

x₆

6

0⁰

0⁰

Ïðîäîëæàåì ïî 233645. Äðîáèì ïî ïåðåõîäó x₅-x₁:

Òàáëèöà 23364551    =14+1=15

x₂

x₄

x₁

1

1

x₆

0⁰

Òàáëèöà 23364551    =14+6=20

x₁

x₂

x₄

x₁

1

0¹

x₅

0¹

x₆

0

0⁰

6

            Îêîí÷àòåëüíî èìååì Ãàìèëüòîíîâ êîíòóð: 2,3,6,4,5,1,2.

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

            Çàäà÷à 10       (Çàäà÷à î íàçíà÷åíèÿõ) Äàí ïîëíûé äâóäîëüíûé ãðàô K_nn ñ âåðøèíàìè ïåðâîé äîëè x₁, x₂,...x_n.è âåðøèíàìè äðóãîé äîëè y₁, y₂,...y_n..Âåñ ðåáðà {xi_,y_j} çàäàåòñÿ ýëåìåíòàìè v_ij ìàòðèöû âåñîâ. Èñïîëüçóÿ âåíãåðñêèé àëãîðèòì, íàéòè ñîâåðøåííîå ïàðîñî÷åòàíèå ìèíèìàëüíîãî (ìàêñèìàëüíîãî âåñà). Âûïîëíèòü ðèñóíîê.

            Ìàòðèöà âåñîâ äâóäîëüíîãî ãðàôà K₅₅  :

y₁

y₂

y₃

y₄

y₅

x₁

2

0

0

0

0

x₂

0

7

9

8

6

x₃

0

1

3

2

2

x₄

0

8

7

6

4

x₅

0

7

6

3

            Ïåðâûé ýòàï - ïîëó÷åíèå íóëåé íå íóæåí, ò. ê. íóëè óæå åñòü âî âñåõ ñòðîê è ñòîëáöàõ.

            Âòîðîé ýòàï - íàõîæäåíèå ïîëíîãî ïàðîñî÷åòàíèÿ.

y₁

y₂

y₃

y₄

y₅

x₁

2

0

0

0

0

x₂

0

7

9

8

6

x₃

0

1

3

2

2

x₄

0

8

7

6

4

x₅

0

7

6

8

3

            Òðåòèé ýòàï - íàõîæäåíèå ìàêñèìàëüíîãî ïàðîñî÷åòàíèÿ.

y₁

y₂

y₃

y₄

y₅

x₁

2

0

0

0

0

X

x₂

0

7

9

8

6

X

x₃

0

1

3

2

2

x₄

0

8

7

6

4

x₅

0

7

6

8

3

X

X

            ×åòâåðòûé ýòàï - íàõîæäåíèå ìèíèìàëüíîé îïîðû.

y₁

y₂

y₃

y₄

y₅

x₁

2

0

0

0

0

x₂

0

7

9

8

6

5

x₃

0

1

3

2

2

1

x₄

0

8

7

6

4

2

x₅

0

7

6

8

3

3

4

            Ïÿòûé ýòàï - âîçìîæíàÿ ïåðåñòàíîâêà íåêîòîðûõ íóëåé.

y₁

y₂

y₃

y₄

y₅

x₁

3

0

0

0

0

x₂

0

6

8

7

5

5

x₃

0

0

2

1

1

x₄

0

7

6

5

3

2

x₅

0

6

5

7

2

3

4

            Ðåøåíèå ñ íåíóëåâûì çíà÷åíèåì. Ïåðåõîä êî âòîðîìó ýòàïó.

            Ïîëíîå ïàðîñî÷åòàíèå:

y₁

y₂

y₃

y₄

y₅

x₁

3

0

0

0

0

x₂

0

6

8

7

5

x₃

0

0

2

1

1

x₄

0

7

6

5

3

x₅

0

6

5

7

2

            Ìàêñèìàëüíîå ïàðîñî÷åòàíèå:

y₁

y₂

y₃

y₄

y₅

x₁

3

0

0

0

0

X

x₂

0

6

8

7

5

X

x₃

0

0

2

1

1

x₄

0

7

6

5

3

x₅

0

6

5

7

2

X

X

            Ìèíèìàëüíàÿ îïîðà:

y₁

y₂

y₃

y₄

y₅

x₁

3

0

0

0

0

6

x₂

0

6

8

7

5

7

x₃

0

0

2

1

1

1

x₄

0

7

6

5

3

2

x₅

0

6

5

7

3

4

5

            Ïåðåñòàíîâêà íóëåé:

y₁

y₂

y₃

y₄

y₅

x₁

3

0

0

0

0

6

x₂

0

6

8

7

5

7

x₃

0

0

2

1

1

1

x₄

0

7

6

5

3

2

x₅

0

6

5

7

2

3

4

5

            Ïîëíîå ïàðîñî÷åòàíèå:

y₁

y₂

y₃

y₄

y₅

x₁

3

0

0

0

0

6

x₂

0

6

8

7

5

7

x₃

0

0

2

1

1

1

x₄

0

7

6

5

3

2

x₅

0

6

5

7

2

3

4

5

            Ìàêñèìàëüíîå ïàðîñî÷åòàíèå:

y₁

y₂

y₃

y₄

y₅

x₁

3

0

0

0

0

X

x₂

0

6

8

7

5

x₃

0

0

2

1

1

X

x₄

0

7

6

5

3

X

x₅

0

6

5

7

2

X

X

X

            Ìèíèìàëüíàÿ îïîðà:

y₁

y₂

y₃

y₅

x₁

3

0

0

0

0

x₂

0

6

8

7

5

1

x₃

0

0

2

1

1

x₄

0

7

6

5

3

x₅

0

6

5

7

2

2

3

            Ïåðåñòàíîâêà íóëåé:

y₁

y₂

y₃

y₄

y₅

x₁

5

0

0

0

0

x₂

0

4

6

5

3

1

x₃

2

0

2

1

1

x₄

2

7

6

5

3

x₅

0

4

3

5

0

2

3

            Ïîëíîå ïàðîñî÷åòàíèå:

y₁

y₂

y₃

y₄

y₅

x₁

5

0

0

0

0

x₂

0

4

6

5

3

x₃

2

0

2

1

1

x₄

2

7

6

5

3

x₅

0

4

3

5

0

            Ìàêñèìàëüíîå ïàðîñî÷åòàíèå:

y₁

y₂

y₃

y₄

y₅

x₁

5

0

0

0

0

X

x₂

0

4

6

5

3

X

x₃

2

0

2

1

1

X

x₄

2

7

6

5

3

x₅

0

4

3

5

0

X

X

X

X

X

            Ìèíèìàëüíàÿ îïîðà:

y₁

y₂

y₃

y₄

y₅

x₁

5

0

0

0

0

x₂

0

4

6

5

3

x₃

2

0

2

1

1

x₄

2

7

6

5

3

1

x₅

0

4

3

5

0

            Ïåðåñòàíîâêà íóëåé:

y₁

y₂

y₃

y₄

y₅

x₁

5

0

0

0

0

x₂

0

4

6

5

3

x₃

2

0

2

1

1

x₄

0

5

4

3

1

1

x₅

0

4

3

5

0

            Ïîëíîå ïàðîñî÷åòàíèå:

y₁

y₂

y₃

y₄

y₅

x₁

5

0

0

0

0

x₂

0

4

6

5

3

x₃

2

0

2

1

1

x₄

0

5

4

3

1

1

x₅

0

4

3

5

0

            Ìàêñèìàëüíîå ïàðîñî÷åòàíèå:

y₁

y₂

y₃

y₄

y₅

x₁

5

0

0

0

0

X

x₂

0

4

6

5

3

X

x₃

2

0

2

1

1

X

x₄

0

5

4

3

1

x₅

0

4

3

5

0

X

X

X

X

X

            Ìèíèìàëüíàÿ îïîðà:

y₁

y₂

y₃

y₄

y₅

x₁

5

0

0

0

0

x₂

0

4

6

5

3

3

x₃

2

0

2

1

1

x₄

0

5

4

3

1

1

x₅

0

4

3

5

0

2

            Ïåðåñòàíîâêà íóëåé:

y₁

y₂

y₃

y₄

y₅

x₁

6

0

0

0

0

x₂

0

3

5

4

2

3

x₃

3

0

2

1

1

x₄

0

4

3

2

0

1

x₅

1

4

3

5

0

2

            Ïîëíîå ïàðîñî÷åòàíèå:

y₁

y₂

y₃

y₄

y₅

x₁

6

0

0

0

0

x₂

0

3

5

4

2

3

x₃

3

0

2

1

1

x₄

0

4

3

2

0

1

x₅

1

4

3

5

0

2

            Ìàêñèìàëüíîå ïàðîñî÷åòàíèå:

y₁

y₂

y₃

y₄

y₅

x₁

6

0

0

0

0

X

x₂

0

3

5

4

2

X

x₃

3

0

2

1

1

X

x₄

0

4

3

2

0

x₅

1

4

3

5

0

X

X

X

X

X

            Ìèíèìàëüíàÿ îïîðà:

y₁

y₂

y₃

y₄

y₅

x₁

6

0

0

0

0

x₂

0

3

5

4

2

4

x₃

3

0

2

1

1

x₄

0

4

3

2

0

1

x₅

1

4

3

5

0

5

2

3

            Â ðåçóëüòàòå èìååì:

y₁

y₂

y₃

y₄

y₅

x₁

6

0

0

0

0

x₂

0

1

3

2

2

4

x₃

3

0

2

1

1

x₄

0

2

1

0

0

1

x₅

1

4

3

5

0

5

2

3

Èñõîäíûé ãðàô

Ïîëó÷åííûé ãðàô:

            Âåñ íàéäåííîãî ñîâåðøåííîãî ïàðîñî÷åòàíèÿ = 12.

            Çàäà÷à 11       Ðåøèòü çàäà÷ó 10, èñïîëüçóÿ àëãîðèòì âåòâåé è ãðàíèö (îòîæäåñòâèâ âåðøèíû x_i è y_j).

Òàáëèöà Å (èñõîäíàÿ). Ñòðîêè - x_i , ñòîëáöû - y_j.          =0

1

2

3

4

5

1

2

0¹

0³

0²

0²

2

0⁶

7

9

8

6

3

0¹

1

3

2

2

4

0⁴

8

7

6

4

5

0³

7

6

8

3

            Äðîáèì ïî ïåðåõîäó x₂ - y₁:

Òàáëèöà Å21   =0+8=8

2

3

4

5

1

0⁰

0²

0¹

0⁰

3

0¹

2

1

1

1

4

4

3

2

0²

4

5

4

3

5

0³

3

Òàáëèöà 21  =0+6=6

1

2

3

4

5

1

2

0¹

0³

0²

0⁰

2

1

3

2

0¹

6

3

0¹

1

3

2

2

4

0⁴

8

7

6

4

5

0³

7

6

8

3

Ïðîäîëæàåì ïî 21:

            Äðîáèì ïî ïåðåõîäó x₄ - y₁:

Òàáëèöà 21Å41       =6+4=10

2

3

4

5

1

0⁰

0²

0¹

0⁰

2

1

3

2

0¹

3

0¹

2

1

1

1

5

4

3

5

0³

3

Òàáëèöà 2141       =6+4=10

1

2

3

4

5

1

2

0¹

0³

0²

0⁰

2

1

3

2

0¹

3

0¹

1

3

2

2

4

4

3

2

0²

4

5

0³

7

6

8

3

Ïðîäîëæàåì ïî Å21:

            Äðîáèì ïî ïåðåõîäó x₅ - y₅:

Òàáëèöà Å21Å55        =8+2=10

2

3

4

1

0⁰

0¹

0⁰

3

0¹

2

1

4

2

1

0¹

2

Òàáëèöà Å2155       =8+3=11

2

3

4

5

1

0⁰

0²

0¹

0⁰

3

0¹

2

1

1

4

4

3

2

0²

5

1

0¹

2

3

Ïðîäîëæàåì ïî Å21Å55:

            Äðîáèì ïî ïåðåõîäó x₃ - y₂:

Òàáëèöà Å21Å55Å32 =10+0=10

3

4

1

0¹

0⁰

4

1

0¹

            Äàëåå ðåøåíèå î÷åâèäíî: x₁ - y₃ è x₄ - y₄. Ýòî íå óâåëè÷èò îöåíêó.

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

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