Практические задания. 1. Постройте граф отношения x+y ≤7 на множестве М={1,2,3,4,5,6}

1. Постройте граф отношения x+y ≤7 на множестве М={1,2,3,4,5,6}. Определите его свойства.

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

3. Найти максимальный поток и минимальный разрез в транспортной сети, используя алгоритм Форда–Фалкерсона (алгоритм расстановки пометок) Построить граф приращений. Проверить выполнение условия максимальности построенного полного потока. Источник – вершина 1, сток – вершина 8.

4. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

5. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

6. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9?

7. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

8. Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту розно 1 раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист

а) не с него начал и не на нем закончил?

б) с него начал, но не на нем закончил?

в) с него начал и на нем закончил?

9. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

10.В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.

Литература

1. Берман, Г.Н. Сборник задач по курсу математического анализа: учебник / Г.Н. Берман. – М.: Лань, 2009. – 164 с.

2. Григорьев, В.П. Сборник задач по математике: учебное пособие для студентов учреждений среднего профессионального образования/ В.П. Григорьев, Т.Н. Сабурова. – М.: Академия, 2010. – 148 с.

3. Демидович, Б. П. Сборник задач и упражнений по матанализу: учебное пособие / Б. П. Демидович. – М.: АСТ, 2007. – 119 с.

4. Ященко, С.А. ЕГЭ. Математика: тематическая рабочая тетрадь / С.А. Ященко, П.И. Шестаков, И.В. Захаров. – М.: Экзамен, 2011. – 122 с.