Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Типовой расчет графов
Раздел: Рефераты по математике
Тип: реферат Добавлен 19:22:05 12 июня 2010 Похожие работы
Просмотров: 353 Комментариев: 3 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

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

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

Исходная вершина - 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

Таблица 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 с.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:27:18 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:13:56 29 ноября 2015
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
13:04:39 25 ноября 2015

Работы, похожие на Реферат: Типовой расчет графов

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(151082)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru