Xreferat.com » Рефераты по математике » Типовой расчет графов

Типовой расчет графов

¥

¥

-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, используя алгоритмы:

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

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

Исходная вершина - a .

а)

Типовой расчет графов

б)

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

Типовой расчет графов

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

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

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

Типовой расчет графов

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

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

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

1-й шаг

Типовой расчет графов

2-й шаг

Типовой расчет графов

3-й шаг

Типовой расчет графов

4-й шаг

Типовой расчет графов

5-й шаг

Типовой расчет графов

6-й шаг

Типовой расчет графов

7-й шаг

Типовой расчет графов

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

Типовой расчет графов

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

Максимальный поток в сети равен 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

 
           

Таблица Типовой расчет графов23Типовой расчет графов36 å =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

¥

 
             

Продолжаем по Типовой расчет графов23Типовой расчет графов36. Дробим по переходу x4-x5:

Таблица Типовой расчет графов23E36Типовой расчет графов45 å =14+0=14

 

x1

x2

x4

 

x1

¥

1

01

 

x5

01

01

1

 

x6

6

¥

00

 
         

Таблица Типовой расчет графов23Типовой расчет графов36Типовой расчет графов45 å =14+1=15

 

x1

x2

x4

x5

 

x1

¥

1

01

¥

 

x4

00

¥

¥

¥

1

x5

01

01

1

¥

 

x6

6

¥

00

00

 
           

Продолжаем по Типовой расчет графов23Типовой расчет графов36Типовой расчет графов45. Дробим по переходу x5-x1:

Таблица Типовой расчет графов23Типовой расчет графов36Типовой расчет графов45Типовой расчет графов51 å =14+1=15

 

x2

x4

 

x1

1

¥

1

x6

¥

00

 
       

Таблица Типовой расчет графов23Типовой расчет графов36Типовой расчет графов45Типовой расчет графов51 å =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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: