идентности;

г) матрицу весов.

д) Для графа 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

SYMBOL 165 f "GreekMathSymbols"

8

3

5

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"



1



SYMBOL 165 f "GreekMathSymbols"

1

SYMBOL 165 f "GreekMathSymbols"

2

2

4

5

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"



2





SYMBOL 165 f "GreekMathSymbols"

2

SYMBOL 165 f "GreekMathSymbols"

5

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"



3







SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

1

6



4









SYMBOL 165 f "GreekMathSymbols"

4

2

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"



5











SYMBOL 165 f "GreekMathSymbols"

2

SYMBOL 165 f "GreekMathSymbols"

1

SYMBOL 165 f "GreekMathSymbols"



6













SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

2



7















SYMBOL 165 f "GreekMathSymbols"

1

1



8

















SYMBOL 165 f "GreekMathSymbols"

6



9



















SYMBOL 165 f "GreekMathSymbols"



д) Матрица смежности для графа Gор.

0

1

2

3

4

5

6

7

8

9



0

SYMBOL 165 f "GreekMathSymbols"

1

1

1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"



1

-1

SYMBOL 165 f "GreekMathSymbols"

1

SYMBOL 165 f "GreekMathSymbols"

1

1

1

1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"



2

-1

-1

SYMBOL 165 f "GreekMathSymbols"

1

SYMBOL 165 f "GreekMathSymbols"

1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"



3

-1

SYMBOL 165 f "GreekMathSymbols"

-1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

-1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

1

1



4

SYMBOL 165 f "GreekMathSymbols"

-1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

1

1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"



5

SYMBOL 165 f "GreekMathSymbols"

-1

-1

1

-1

SYMBOL 165 f "GreekMathSymbols"

1

SYMBOL 165 f "GreekMathSymbols"

1

SYMBOL 165 f "GreekMathSymbols"



6

SYMBOL 165 f "GreekMathSymbols"

-1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

-1

-1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

1



7

SYMBOL 165 f "GreekMathSymbols"

-1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

1

1



8

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

-1

SYMBOL 165 f "GreekMathSymbols"

-1

SYMBOL 165 f "GreekMathSymbols"

-1

SYMBOL 165 f "GreekMathSymbols"

1



9

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

-1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

-1

-1

-1

SYMBOL 165 f "GreekMathSymbols"







Задача 2 Найти диаметр D(G), радиус R(G), количество центров Z(G) для графа G ; указать вершины, являющиеся центрами графа G.

D(G)=2

R(G)=2

Z(G)=10

Все вершины графа G(V,X) являются центрами.

Задача 3 Перенумеровать вершины графа G, используя алгоритмы:

а) "поиска в глубину";

б) "поиска в ширину".

Исходная вершина - SYMBOL 97 f "Symbol" .

а)



б)



Задача 4 Используя алгоритм Прима найти остов минимального веса графа G. выписать код укладки на плоскости найденного дерева, приняв за корневую вершину SYMBOL 97 f "Symbol" .



Вес найденного дерева - 14.

Код укладки дерева: 000011000001111111.

Задача 5 Используя алгоритм Дейкстра найти дерво кратчайших путей из вершины SYMBOL 97 f "Symbol" графа G.



Вес найденного пути - 8.

Задача 6 Используя алгоритм Форда - Фалкерсона, найти максимальный поток во взвешенной двуполюсной ориентированной сети {Gор , SYMBOL 97 f "Symbol" , w}. Указать разрез минимального веса.

Последовательность насыщения сети (насыщенные ребра отмечены кружечками):

1-й шаг



2-й шаг



3-й шаг



4-й шаг



5-й шаг



6-й шаг



7-й шаг



Окончательно имеем:



Как видно из рисунка, ребра {6,9},{7,9},{3,9}, питающие вершину SYMBOL 119 f "GreekMathSymbols" , насыщенны, а оставшееся ребро {8,9}, питающееся от вершины 8, не может получить большее значение весовой функции, так как насыщенны все ребра, питающие вершину 8. Другими словами - если отбросить все насыщенные ребра, то вершина SYMBOL 119 f "GreekMathSymbols" недостижима, что является признаком максимального потока в сети.

Максимальный поток в сети равен 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ор изменить ориентацию наименьшего числа ребер таким образом, чтобы в новом графе Гамильтонов цикл можно было указать.

а) Гамильтонов путь (ребра с измененной ориентацией показаны пунктиром):





б) Гамильтонов цикл (ребра с измененной ориентацией показаны пунктиром):



. Выполнить рисунок.

Исходная таблица.

x1

x2

x3

x4

x5

x6





x1

SYMBOL 165 f "GreekMathSymbols"

3

7

2

SYMBOL 165 f "GreekMathSymbols"

11





x2

8

SYMBOL 165 f "GreekMathSymbols"

06

SYMBOL 165 f "GreekMathSymbols"

4

3





x3

6

05

SYMBOL 165 f "GreekMathSymbols"

7

SYMBOL 165 f "GreekMathSymbols"

2





x4

6

SYMBOL 165 f "GreekMathSymbols"

13

SYMBOL 165 f "GreekMathSymbols"

5

SYMBOL 165 f "GreekMathSymbols"





x5

3

3

3

4

SYMBOL 165 f "GreekMathSymbols"

5





x6

8

6

SYMBOL 165 f "GreekMathSymbols"

2

2

SYMBOL 165 f "GreekMathSymbols"

























14

x1

x2

x3

x4

x5

x6





x1

SYMBOL 165 f "GreekMathSymbols"

1

5

01

SYMBOL 165 f "GreekMathSymbols"

7

2



x2

8

SYMBOL 165 f "GreekMathSymbols"

01

SYMBOL 165 f "GreekMathSymbols"

4

1





x3

6

00

SYMBOL 165 f "GreekMathSymbols"

7

SYMBOL 165 f "GreekMathSymbols"

00





x4

1

SYMBOL 165 f "GreekMathSymbols"

8

SYMBOL 165 f "GreekMathSymbols"

01

SYMBOL 165 f "GreekMathSymbols"

5



x5

01

00

00

1

SYMBOL 165 f "GreekMathSymbols"

00

3



x6

6

4

SYMBOL 165 f "GreekMathSymbols"

00

00

SYMBOL 165 f "GreekMathSymbols"

2















2







Дробим по переходу x2-x3:

23 SYMBOL 229 f "GreekMathSymbols" =14+0=14

x1

x2

x4

x5

x6





x1

SYMBOL 165 f "GreekMathSymbols"

1

01

SYMBOL 165 f "GreekMathSymbols"

7





x3

6

SYMBOL 165 f "GreekMathSymbols"

7

SYMBOL 165 f "GreekMathSymbols"

06





x4

1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

01

SYMBOL 165 f "GreekMathSymbols"





x5

01

01

1

SYMBOL 165 f "GreekMathSymbols"

00





x6

6

4

00

00

SYMBOL 165 f "GreekMathSymbols"























23 SYMBOL 229 f "GreekMathSymbols" =14+1=15

x1

x2

x3

x4

x5

x6





x1

SYMBOL 165 f "GreekMathSymbols"

1

5

01

SYMBOL 165 f "GreekMathSymbols"

7





x2

7

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

3

03

1



x3

6

00

SYMBOL 165 f "GreekMathSymbols"

7

SYMBOL 165 f "GreekMathSymbols"

00





x4

1

SYMBOL 165 f "GreekMathSymbols"

8

SYMBOL 165 f "GreekMathSymbols"

01

SYMBOL 165 f "GreekMathSymbols"





x5

01

00

05

1

SYMBOL 165 f "GreekMathSymbols"

00





x6

6

4

SYMBOL 165 f "GreekMathSymbols"

00

00

SYMBOL 165 f "GreekMathSymbols"























23. Дробим по переходу x3-x6:

23E36 SYMBOL 229 f "GreekMathSymbols" =14+0=14

x1

x2

x4

x5





x1

SYMBOL 165 f "GreekMathSymbols"

1

01

SYMBOL 165 f "GreekMathSymbols"





x4

1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

01





x5

01

01

1

SYMBOL 165 f "GreekMathSymbols"





x6

6

SYMBOL 165 f "GreekMathSymbols"

00

00



















36 SYMBOL 229 f "GreekMathSymbols" =14+6=20

x1

x2

x4

x5

x6





x1

SYMBOL 165 f "GreekMathSymbols"

1

01

SYMBOL 165 f "GreekMathSymbols"

7





x3

01

SYMBOL 165 f "GreekMathSymbols"

1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

6



x4

1

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

01

SYMBOL 165 f "GreekMathSymbols"





x5

00

01

1

SYMBOL 165 f "GreekMathSymbols"

07





x6

6

4

00

00

SYMBOL 165 f "GreekMathSymbols"























36. Дробим по переходу x4-x5:

45 SYMBOL 229 f "GreekMathSymbols" =14+0=14

x1

x2

x4





x1

SYMBOL 165 f "GreekMathSymbols"

1

01





x5

01

01

1





x6

6

SYMBOL 165 f "GreekMathSymbols"

00



















45 SYMBOL 229 f "GreekMathSymbols" =14+1=15

x1

x2

x4

x5





x1

SYMBOL 165 f "GreekMathSymbols"

1

01

SYMBOL 165 f "GreekMathSymbols"





x4

00

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

SYMBOL 165 f "GreekMathSymbols"

1



x5

01

01

1

SYMBOL 165 f "GreekMathSymbols"





x6

6

SYMBOL 165 f "GreekMathSymbols"

00

00





















45. Дробим по переходу x5-x1:

51 SYMBOL 229 f "GreekMathSymbols" =14+1=15

x2

x4





x1

1

SYMBOL 165 f "GreekMathSymbols"

1



x6

SYMBOL 165 f "GreekMathSymbols"

00

















51 SYMBOL 229 f "GreekMathSymbols" =14+6=20

x1

x2

x4





x1

SYMBOL 165 f "GreekMathSymbols"

1

01





x5

SYMBOL 165 f "GreekMathSymbols"

01

SYMBOL 165 f "GreekMathSymbols"





x6

0

SYMBOL 165 f "GreekMathSymbols"

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. SYMBOL 229 f "GreekMathSymbols" =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 SYMBOL 229 f "GreekMathSymbols" =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 SYMBOL 229 f "GreekMathSymbols" =0+6=6

1

2

3

4

5





1

2

01

03

02

00





2

SYMBOL 165 f "GreekMathSymbols"

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 SYMBOL 229 f "GreekMathSymbols" =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

















41 SYMBOL 229 f "GreekMathSymbols" =6+4=10

1

2

3

4

5





1

2

01

03

02

00





2

SYMBOL 165 f "GreekMathSymbols"

1

3

2

01





3

01

1

3

2

2





4

SYMBOL 165 f "GreekMathSymbols"

4

3

2

02

4



5

03

7

6

8

3





















Продолжаем по Е21:

Дробим по переходу x5 - y5:

Таблица Е21Е55 SYMBOL 229 f "GreekMathSymbols" =8+2=10

2

3

4





1

00

01

00





3

01

2

1





4

2

1

01

2















55 SYMBOL 229 f "GreekMathSymbols" =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

SYMBOL 165 f "GreekMathSymbols"

3

















Продолжаем по Е21Е55:

Дробим по переходу x3 - y2:

Таблица Е21Е55Е32 SYMBOL 229 f "GreekMathSymbols" =10+0=10

3

4





1

01

00





4

1

01















Далее решение очевидно: x1 - y3 и x4 - y4. Это не увеличит оценку.

В итоге имеем совершенное паросочетание с минимальным весом:



Прадерево разбиений:



hSymbols"
NURBIZ.KZ - каталог компаний и предприятий Казахстана и Алматы

Expert Oil / Эксперт Оил

Скидка 100%

Покупай масло MOTUL 4, 5 литров – получай мойку в подарок!

Санаторий для детей – куда отправить ненаглядное чадо

Студенческое общежитие: вещи первой необходимости