Вход

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

Реферат* по математике
Дата добавления: 23 января 2002
Язык реферата: Русский
Word, rtf, 1.9 Мб (архив zip, 275 кб)
Реферат можно скачать бесплатно
Скачать
Данная работа не подходит - план Б:
Создаете заказ
Выбираете исполнителя
Готовый результат
Исполнители предлагают свои условия
Автор работает
Заказать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу
* Данная работа не является научным трудом, не является выпускной квалификационной работой и представляет собой результат обработки, структурирования и форматирования собранной информации, предназначенной для использования в качестве источника материала при самостоятельной подготовки учебных работ.
Очень похожие работы




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


Данная работа является типовым расчетом N2 по курсу "Дискретная математика" по теме "Графы", предлагаемая студентам МГТУ им. Баумана. (Вариант N 17).

Сразу хочу сказать для своих коллег: Граждане! Имейте терпение и совесть, поймите, что я это делаю для Вас с целью помочь разобраться в этой теме, а не просто свалить очередной предмет. Мне известно, как непросто сейчас с литературой, и с информацией вообще. Поиски неизвестно какой книги занимают много времени, поэтому в конце я привел небольшой список литературы, составленный мной из различных источников в дополнение к списку, написанному ранее в работе по графам (о постановке лаб. работ по алгоритму Прима и Дейкстра), которая, я надеюсь, есть в сети.


Содержание работы:

Типовой расчет состоит из 11-ти задач:

1, 2 и 3 задачи относятся к способам задания графов и опредению их характеристик, таких как диаметр, радиус и т.д.

4 и 5 задачи соответственно на алгоритм Прима и Дейкстра. Здесь я снова отсылаю Вас к более ранней работе (см. выше).

6-я задача о поиске максим ального потока в сети (метод Форда-Фалкерсона).

7-я задача - Эйлерова цепь (задача о почтальоне).

8-я задача - Гамильтонова цепь.

9-я задача - метод ветвей и границ применительно к задаче о коммивояжере.

10-я задача - задача о назначениях; венгерский алгоритм.

11-я задача - тоже методом ветвей и границ.



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. Это не увеличит оценку.

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

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


Литература


1. Грешилов А.А. Как принять наилучшее решение в реальных условиях:-М.:Радио и связь, 1991.-320с.:ил.

2. Беллман Р. Динамическое программирование: Пер. с англ./Под ред. Н.Н. Воробьева.-М.: ИЛ, 1960.-400 с.

3. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования: Пер с англ./Под ред. А.А. Первозванского.-М.: Наука, 1965.-458 с.

4. Вентцель Е.С. Исследование операций.-М.: Сов. радио, 1972.-551 с.

5. Вильямс Н.Н. Параметрическое программирование в экономике (методы оптимальных решений):-М.:Статистика, 1976.-96с.

6. Гольштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании:-М.: Сов радио, 1966.- 524 с.

7. Зангвилл У.И. Нелинейное программирование: Пер. с англ./Под ред. Е.Г. Гольштейна.-М.: Сов радио, 1973.- 312 с.

8. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование (справочное руководство).-М.: Наука, 1964.-348 с.

9. Исследование операций. Методологические основы и математические методы: Пер. с англ./ Под ред. И.М. Макарова, И.М. Бескровного.-М.: Мир, 1981.- Т.1.-712 с.

10. Исследование операций. Модели и применение: Пер. с англ./ Под ред. И.М. Макарова, И.М. Бескровного.-М.: Мир, 1981.- Т.1.-712 с.

11. Лазарев В.Г., Лазарев Ю.В. Динамическое управление потоками информации в сетях связи.-М.: Радио и связь, 1983.- 216 с.

12. Мартин Дж. Системный анализ передачи данных.: Пер с англ./ Под ред. В.С. Лапина.-М.: Мир, 1975.- М.2.- 431 с.

13. Монаков В.М., Беляева Э.С., Краснер Н.Я. Методы оптимизации. Пособие для учителя.-М.: Просвещение, 1978.- 175с.

14. Муртаф Б. Современное линейное программирование: Теория и практика. Пер. с англ./Под ред. И.А. Станевичуса.- М.: Мир, 1984.- 224 с.

15. Рокафеллор Р. Выпуклый анализ: Пер. с англ./Под ред. А.Д. Иоффе, В.М. Тихомирова.-М.: Мир, 1973.- 469 с.

16. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации.- М.:- Наука, Физматгиз, 1986.- 326 с.

17. Ху Т. Целочисленное программирование и потоки в сетях: Пер. с англ./Под ред. А.А. Фридмана.- М.: Мир, 1974.-419 с.

18. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации: Пер. с англ./Под ред. Е.Г. Гольштейна. -М.:- Мир, 1972.- 240 с.

19. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей: Пер. с англ./ Под ред. Б.Г. Сушкова.- М.: Мир, 1984.- 496 с.

20. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория и конечные методы,- М.:- Физматгиз, 1963.- 775 с.



© Рефератбанк, 2002 - 2024