Учебное пособие 1714
.pdfВариант 8
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
10 |
a2 |
— |
12 |
a3 |
— |
9 |
a4 |
a1 |
6 |
a5 |
a1 , a3 |
7 |
a6 |
a2 , a4 |
9 |
a7 |
a1 , a2 , a4 , a5 |
5 |
|
Вариант 9 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
5 |
a2 |
— |
7 |
a3 |
a1 |
10 |
a4 |
a1 , a2 |
11 |
a5 |
a1 , a2 |
5 |
a6 |
a3 |
7 |
a7 |
a3 |
10 |
a8 |
a1 , a4 , a6 |
7 |
a9 |
a1 , a4 , a5 , a6 |
12 |
|
Вариант 10 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
12 |
a2 |
— |
10 |
a3 |
— |
13 |
a4 |
a1 |
7 |
a5 |
a1 , a2 |
9 |
a6 |
a1 , a2 , a3 |
14 |
a7 |
a6 |
16 |
a8 |
a4 , a5 , a7 |
11 |
a9 |
a6 |
9 |
141
Вариант 11
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
7 |
a2 |
a1 |
5 |
a3 |
— |
11 |
a4 |
|
14 |
a5 |
a1 , a3 |
4 |
a6 |
a2 , a4 |
7 |
a7 |
a1 , a4 , a5 |
6 |
|
Вариант 12 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
5 |
a2 |
— |
7 |
a3 |
a1 , a2 |
12 |
a4 |
a1 , a2 |
4 |
a5 |
a2 |
6 |
a6 |
a3 , a4 , a5 |
10 |
a7 |
a3 |
9 |
|
Вариант 13 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
7 |
a2 |
— |
11 |
a3 |
a1 |
9 |
a4 |
a1 |
6 |
a5 |
a1 , a2 |
12 |
a6 |
a1 , a2 |
15 |
a7 |
a3 |
8 |
a8 |
a4 , a5 |
7 |
a9 |
a3 , a4 , a5 , a6 |
6 |
|
142 |
|
Вариант 14
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
6 |
a2 |
— |
7 |
a3 |
— |
9 |
a4 |
a1 , a2 |
11 |
a5 |
a2 , a3 |
8 |
a6 |
a2 |
7 |
a7 |
a4 , a5 |
6 |
a8 |
a6 |
10 |
a9 |
a2 , a3 |
7 |
|
Вариант 15 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
7 |
a2 |
— |
8 |
a3 |
— |
12 |
a4 |
a1 , a2 |
6 |
a5 |
a2 , a3 |
7 |
a6 |
a3 |
14 |
a7 |
a3 , a4 , a5 |
5 |
|
Вариант 16 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
6 |
a2 |
— |
7 |
a3 |
a1 |
8 |
a4 |
a1 , a2 |
9 |
a5 |
a2 , a3 |
8 |
a6 |
a1 , a3 , a4 |
4 |
a7 |
a4 |
5 |
|
143 |
|
Вариант 17
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
7 |
a2 |
— |
9 |
a3 |
— |
10 |
a4 |
a3 |
7 |
a5 |
a2 , a4 |
12 |
a6 |
a1 , a2 , a3 |
14 |
a7 |
a2 , a5 |
6 |
|
Вариант 18 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
9 |
a2 |
— |
10 |
a3 |
a1 |
7 |
a4 |
a1 , a2 |
12 |
a5 |
a2 |
8 |
a6 |
a3 , a4 , a5 |
10 |
a7 |
a3 , a4 |
8 |
|
Вариант 19 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
14 |
a2 |
— |
14 |
a3 |
a2 |
16 |
a4 |
a1 , a2 |
17 |
a5 |
a1 , a3 |
10 |
a6 |
a2 , a4 , a5 |
15 |
a7 |
a2 |
18 |
|
144 |
|
Вариант 20
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
7 |
a2 |
— |
6 |
a3 |
— |
8 |
a4 |
a1 , a2 |
10 |
a5 |
a2 |
10 |
a6 |
a2 , a3 |
18 |
a7 |
a3 , a4 , a5 |
5 |
|
Вариант 21 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
16 |
a2 |
— |
14 |
a3 |
a2 |
10 |
a4 |
a1 , a2 |
5 |
a5 |
a3 |
7 |
a6 |
a2 , a4 , a5 |
14 |
a7 |
a2 |
3 |
|
Вариант 23 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
11 |
a2 |
— |
12 |
a3 |
— |
10 |
a4 |
a1 , a2 |
9 |
a5 |
a2 , a3 |
7 |
a6 |
a2 , a3 |
14 |
a7 |
a1 , a2 |
8 |
a8 |
a2 , a4 , a5 |
9 |
a9 |
a6 |
12 |
145
Вариант 22
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
8 |
a2 |
— |
5 |
a3 |
— |
7 |
a4 |
a3 |
9 |
a5 |
a2 , a4 |
10 |
a6 |
a1 , a2 , a3 |
15 |
a7 |
a2 , a5 |
7 |
|
Вариант 24 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
13 |
a2 |
— |
12 |
a3 |
a1 |
15 |
a4 |
a1 |
16 |
a5 |
a1 , a2 |
14 |
a6 |
a3 |
14 |
a7 |
a4 , a5 |
16 |
a8 |
a6 , a7 |
17 |
a9 |
a4 , a5 |
15 |
|
Вариант 25 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
3 |
a2 |
— |
2 |
a3 |
a1 |
4 |
a4 |
a1 , a2 |
11 |
a5 |
a1 , a2 |
7 |
a6 |
a1 , a4 |
5 |
a7 |
a3 |
9 |
a8 |
a1 , a4 |
7 |
a9 |
a5 , a6 |
8 |
146
Вариант 26
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
8 |
a2 |
— |
7 |
a3 |
a2 |
9 |
a4 |
a1 , a2 |
10 |
a5 |
a1 , a3 |
8 |
a6 |
a2 , a4 , a5 |
6 |
a7 |
a2 |
10 |
|
Вариант 27 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
8 |
a2 |
— |
9 |
a3 |
a1 , a2 |
7 |
a4 |
a2 |
12 |
a5 |
a3 , a4 |
5 |
a6 |
a2 |
10 |
a7 |
a3 , a4 , a6 |
7 |
a8 |
a2 , a5 |
13 |
|
Вариант 28 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
15 |
a2 |
— |
14 |
a3 |
a1 |
16 |
a4 |
a1 , a2 |
15 |
a5 |
a2 , a3 |
17 |
a6 |
a2 , a3 , a4 |
19 |
a7 |
a4 |
14 |
a8 |
a5 , a6 |
17 |
|
147 |
|
Вариант 29
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
17 |
a2 |
— |
15 |
a3 |
— |
10 |
a4 |
a3 |
14 |
a5 |
a2 , a4 |
18 |
a6 |
a1 , a2 , a3 |
10 |
a7 |
a2 , a5 |
16 |
|
Вариант 30 |
|
Исходная |
Предшествующие |
Продолжительность |
работа |
ей работы |
работ |
a1 |
— |
10 |
a2 |
— |
11 |
a3 |
— |
13 |
a4 |
a1 |
19 |
a5 |
a1 , a2 |
17 |
a6 |
a1 , a2 , a3 |
15 |
a7 |
a4 |
16 |
a8 |
a4 , a5 , a6 |
12 |
a9 |
a1 , a7 , a8 |
15 |
Заключение
Пособие в первую очередь предназначено для студентов ВГАСУ специальности 270115 «Экспертиза и управление недвижимостью», хотя может быть использовано и студентами других специальностей, изучающих теорию графов.
Пособие позволит студентам выполнить расчетно-графическую работу и подготовиться к сдаче экзамена, так как включает и необходимые теоретические сведения по курсу «Теория графов» и примеры решений всех типов задач, входящих в расчетно-графическую работу.
148
Библиографический список рекомендуемой литературы
1.Кирсанов, М.Н. Математический центр московского метро / М.Н. Кирса-
нов // Exponenta Pro. Математика в приложениях. 2003. № 4(4).– С. 60 – 62.
2.Аляев, Ю.Л. Дискретная математика и математическая логика / Ю.А. Аляев, С.Ф. Тюрин. – М.: Финансы и статистика, 2006. – 368 с.
3.Балюкевич, Э.Л. Дискретная математика / Э.Л. Балюкевич, Л.Ф. Ковалева,
А.Н Романчиков.– Московский государственный университет экономики, статистики и информатики, – М., 2003. – 127 с.
4.Дьяконов, В.П. Maple 7: учебный курс / В.П. Дьяконов. – СПб.: Питер, 2002. – 672 с.
5.Канцедал, С.А. Дискретная математика / С.А. Канцедал. – М.: ИД
«ФОРУМ»: ИНФРА-М, 2007. – 224 с.
6.Кирсанов, М.Н. Графы в Maple. Задачи, алгоритмы, программы / М.Н.
Кирсанов.– М.: ФИЗМАТЛИТ, 2007. – 168 с.
7.Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристо-
фидес. – М.:Наука, 1990. – 432 с.
8.Кузнецов, О.П. Дискретная математика для инженера / О.П. Кузнецов. – СПб: Издательство «Лань», 2007. – 400 с.
9.Оре, О. Графы и их применение / О. Оре. – М.: Мир, 1965 г. – 175 с.
10.Осипова, В.А. Основы дискретной математики / В.А. Осипова. – М.:
ФОРУМ: ИНФРА-М, 2006. –160 с.
11.Плотников, А.Д. Дискретная математика /А.Д. Плотников. – М.: Новое знание, 2006. – 304 с.
12.Редькин, Н.П. Дискрегная математика / Н.П. Редькин. – СПб.: Издатель-
ство «Лань», 2003. – 96 с.
13.Сдвижков, О.А. Математика на компьютере: Maple 8 / О.А. Сдвижков. –
М.: СОЛДОН-Пресс, 2003. – 176 с.
14.Справочник по математике для экономистов / В.Е. Барбаумов, В.И. Ермаков, Н.Н. Кривенцова и др.; под ред. В.И. Ермакова. – М.: Высш. шк., 1987. – 336 с.
15.Судоплатов, С.В. Дискретная математика / С.В. Судоплатов, Е.В. Овчин-
никова. – М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2007. – 256 с. 16.Уилсон, Р. Введение в теорию графов / Р. Уилсон. – М.: Мир. 1977 г. – 208
с., 17.Харари, Ф. Теория графов / Ф. Харари. – М.: Мир. 1973 г. – 301 с.
18.Шапорев, С.Д. Дискретная математика. Курс лекций и практических занятий / С.Д. Шапорев. – СПб.: БХВ-Петербург, 2007. – 400 с.
149
Приложение 1
Пакет символьной математики Maple для работы с графами
Долгое время задачи теории графов решались вручную. С появлением компьютеров появилась возможность написания специальных программ на алгоритмических языках. Позднее появились пакеты аналитических вычислений
Mathematica, MATLAB, Mathcad и Maple, позволяющие выполнять аналитиче-
ские символьные преобразования.
В программе Maple есть специализированная библиотека networks, составленная из операторов для работы с графами. Вызов пакета networks производится командой with(networks). Рассмотрим здесь его операторы, которые могут потребоваться для решения задач, описанных в данном пособии (более подробно с пакетом networks можно ознакомиться в руководствах по программе Maple):
●addedge([{1,2},[3,4]],G) – добавить в граф G ребра или дуги.
Ребра в неорграфе задаются как множества – с вершинами в фигурных скобках,
адуги в орграфе – списком вершин в квадратных скобках. Если требуется задать вес дуги в орграфе, то дуги надо обозначать только квадратными скобками. Если вес можно не указывать, то для сокращения ввода две дуги, соединяющие вершины в разных направлениях, проще ввести как ребро;
●addvertex(seq(i,i=l..n),G) – добавить к графу G вершины
1,2,...,n. В опции weights можно в списке указать веса вершин. По умолчанию веса нулевые;
●adjacency(G) – матрица смежности графа G. Данный оператор правильно работает в случае мультиграфов, но для псевдографов он непригоден. Главная диагональ этой матрицы нулевая;
●allpairs(G) – матрица пар расстояний между вершинами графа G;
●arrivals(v,G) – множество ребер, входящих в вершину v орграфа G;
●complement(G) – дополнение графа G;
●complete(n) – полный граф Kn ;
●complete(n,m) – полный двудольный граф Kn,m ;
150