Список практических заданий. 1.Расписание одного дня содержит 5 уроков

1.Расписание одного дня содержит 5 уроков. Определить количество таких расписаний при выборе из одиннадцати дисциплин.

2.Комиссия состоит из председателя, его заместителя и еще пяти человек. Сколькими способами члены комиссии могут распределять между собой обязанности.

3.Сколькими способами можно выбрать трех дежурных из группы в 20 человек.

4.Сколько различных звукосочетаний можно взять на десяти выбранных клавишах рояля, если каждое звукосочетание может содержать от трех до десяти звуков.

5.В вазе стоят 10 красных и 5 розовых гвоздик. Сколькими способами можно выбрать из вазы пять гвоздик одного цвета.

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

7.Из группы в 15 человек выбирают четырех участников эстафеты 800+400+200+100. Сколькими способами можно расставить спортсменов по этапам эстафеты.

8.Команда из пяти человек выступает на соревнованиях по плаванию, в которых участвуют еще 20 спортсменов. Сколькими способами могут распределиться места, занятые членами этой команды.

9.Из группы в 12 человек ежедневно в течение 6 дней выбирают двух дежурных. Определить количество различных списков дежурных, если каждый человек дежурит один раз.

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

Вопросы для обсуждения на форуме

1. Решение задач комбинаторики.

Список дополнительной литературы:

1. Горбатов В.А. Фундаментальные основы дискретной математики. М.: Высшая школа, 2000. – 544с.

2. Кофман В. А. Введение в прикладную комбинаторику. М.: Радио и связь, 1982. 431с.

Семинар №7.Теория графов

Цель семинара:

Рассмотреть вопросы, связанные с практическим применением теории графов в принятии решений.

План занятия:

Семина посвящен теории графов. Первой рассматривается тема основные понятия и операции на графах, затем тема посвященная маршрутам и деревьям. На семинар отводится 2 часа.

Задача 1.На рис.7.1 изображены графы - с четырьмя вершинами в каждом. Сравнить графы.

Рис. 7.1. Графы -

Решение.

Результаты сравнения графов таковы:

- - неориентированные;

- - ориентированные;

, - полные, причем = ;

- не является полным, так как хотя каждая пара вершин и соединена ребром, но имеется петля. Иногда полным графом называют граф с петлями во всех вершинах, каждая пара которых соединена ребром. Граф не отвечает этому определению.

- все вершины этого графа являются изолированными (граф с пустым множеством ребер, т.е. 0);

и являются дополнением друг к другу: = и = ;

- мультиграф, так как содержит кратные ребра a и b, а также e и f;

- ориентированный, канонически соответствующий неориентированному графу ;

и не является равными, так как имеют отличающиеся ребра (4,1) - и (1,4) в ;

- ориентированный мультиграф: ребра a и b – кратные, тогда как мультиграфом не является, поскольку в нем ребра a и b различно ориентированы.

Задача 2.Чему равны степени вершин графов , на рис.7.2.

Рис. 7.2. Графы и

Решение.

Оба графа имеют по четыре вершины: . Степени вершин неориентированного графа : , , , , если условиться считать вклад петли в степень вершины. Сумма степеней всех вершин графа равна 14, т.е. вдвое больше числа ребер графа:

, где m=7 – число ребер графа.

Степени вершин ориентированного графа :

, , , ;

, , , .

Суммы степеней вершин первого и второго типа графа совпадают и равны числу m ребер графа: .

Задача 3.На рис. 7.3 изображен сетевой граф (сетевая модель) выполнения комплекса операций (работ) некоторой программы. В нем стрелки обозначают операции, вершины – события, характеризующие окончание одних работ и начало других. Направленность стрелок отражает последовательность наступления этих событий. Задать сетевой граф различными способами.

Рис. 7.3. Сетевой граф

Решение.

Изображенная сетевая модель представляет собой ориентированный граф, который может быть полностью задан различными способами:

1) графически(см.рис. выше);

2) с помощью задания двух множеств: и ;

3) матрицей инцидентности (табл. 7.1). Особенностью сетевой модели является то, что из начального события 1 стрелки выходят, а в конечное 6 – только входят. Поэтому в первой строке матрицы инцидентности имеются единицы только со знаком «минус», а в последней – только со знаком «плюс»;

Таблица 7.1. Матрица инцидентности

4) матрицей смежности (табл. 7.2). По причине, указанной в п.3, в последней строке матрицы смежности поставлены только нули;

Таблица 7.2. Матрица смежности

5) списком ребер сетевой граф задается очевидным образом, поскольку ребра графа обозначены через свои концевые вершины. В таком случае в столбце «вершины» списка будут повторяться номера вершин, указанных в столбце «ребра», причем в той последовательности, в какой в данном случае стрелки – ребра обозначены.

Задача 4.Имеют ли графы на рис. 7.4 ниже гамильтоновы циклы, цепи.

Рис. 7.4. Графы и

Решение.

Гамильтонов цикл как простой цикл, проходящий через все вершины графа, существует на графе - он проходит по ребрам (a, b, c, d, e, f, g, q, n, m, l, h, a). В существует и гамильтонова цепь, для чего в гамильтоновом цикле достаточно удалить любое ребро.

В графе гамильтонова цикла нет: чтобы пройти через вершины a, b, c внешнего треугольника графа должен содержать все лежащие на этих сторонах ребра, но тогда он не проходит через расположенную в центре треугольника вершину d.Однако гамильтонова цепь в графе существует, например с началом в вершине a, концом d и последовательностью ребер, соединяющих вершины a, f, b, g, c, e, d.

Задача 5. Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую. В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б. Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим граф приведенный на рис. 7.5.

Рис. 7.5. Граф

Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (см. табл. ниже). В этой таблице двум вершинам – началу пути и концу пути – ставится в соответствие время в пути. В табл. 7.3 рассматриваются пути без промежуточных остановок. Более сложные маршруты составляются из элементарных отрезков, перечисленных в таблице.

Таблица 7.3. Исходные данные к задаче о кратчайшем пути.

Начало дуги	Конец дуги	Время в пути

Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4.

Решение.Введем обозначение: С(Т) - длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рис. выше и в табл. выше, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С(3) = 1. Кроме того, очевидно, что С(1) = 0.

В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение

С(4) = min {С(2) + 4; С(5) + 5}.

Таким образом, проведена реструктуризация (упрощение) задачи - нахождение С(4) сведено к нахождению С(2) и С(5).

В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение

С(5) = min {С(3) + 2; С(6) + 3}.

Мы знаем, что С(3) = 1. Поэтому

С(5) = min {3; С(6) + 3}.

Поскольку очевидно, что С(6) - положительное число, то из последнего соотношения вытекает, что С(5) = 3.

В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение

С(2) = min {С(1) + 7; С(3) + 5; С(5) + 2}.

Нам известно, что С(1) = 0, С(3) = 1, С(5) = 3. Поэтому

С(2) = min {0 + 7; 1 + 5; 3 + 2} = 5.

Теперь мы можем найти С(4):

С(4) = min {С(2) + 4; С(5) + 5} = min {5 + 4; 3 + 5} = 8.

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:

1 → 3 → 5 → 4 .

Задача 6.Задача о максимальном потоке.Как (т.е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена.

Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть сопоставлено число - пропускная способность этой дуги. Рассмотрим граф рис. 7.6.

Рис. 7.6. Граф

Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. 7.6., можно также задать таблицей табл.7.4.

Таблица 7.4. Исходные данные к задаче о кратчайшем пути.

Пункт отправления	Пункт назначения	Пропускная способность

Решение.

Решение задачи о максимальном потоке может быть получено из следующих соображений.

Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.

Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 2. Их направляем в пункт 4.

Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.

Решение можно представить в виде табл. 7.5.

Таблица 7.5. Решение задачи о максимальном потоке