Реферат Типовий розрахунок графів

Td>

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