Уроки 80 - 83
Графы. Основные понятия
(§44. Графы)
Содержание урока
Некоторые задачи
Некоторые задачи
С графами связаны некоторые классические задачи. Самая известная из них — задача коммивояжёра (бродячего торговца).
Задача 3. Бродячий торговец должен посетить N городов по одному разу и вернуться в город, откуда он начал путешествие. Известны расстояния между городами (или стоимость переезда из одного города в другой). В каком порядке нужно посещать города, чтобы суммарная длина пути (или стоимость) оказалась наименьшей?
Эта задача оказалась одной из самых сложных задач оптимизации. По сей день известно только одно надёжное решение — полный перебор вариантов, число которых равно факториалу значения N - 1. Это число с увеличением N растёт очень быстро, быстрее, чем любая степень N. Уже для N = 20 такое решение требует огромного времени вычислений: компьютер, проверяющий 1000 вариантов в секунду, будет решать задачу «в лоб» около четырёх миллионов лет. Поэтому математики прилагали большие усилия для того, чтобы сократить перебор — не рассматривать те варианты, которые заведомо не дают лучших результатов, чем уже полученные. В реальных ситуациях нередко оказываются полезными приближённые решения, которые не гарантируют точного оптимального решения, но позволяют получить приемлемый вариант.
Приведём формулировки ещё некоторых задач, которые решаются с помощью теории графов. Алгоритмы их решения вы можете найти в литературе или в Интернете.
Задача 4 (о максимальном потоке). Есть система труб, которые имеют соединения в N узлах. Один узел S является источником, ещё один Т — стоком. Известны пропускные способности каждой трубы. Надо найти наибольший поток от источника к стоку.
Задача 5. Имеются N населённых пунктов, в каждом из которых живут pi школьников (i = 1, ..., N). В каком пункте нужно разместить школу, чтобы общее расстояние, проходимое всеми учениками по дороге в школу, было минимальным?
Задача 6 (о наибольшем паросочетании). Есть М мужчин и N женщин. Каждый мужчина указывает несколько женщин (от О до N), на которых он согласен жениться. Каждая женщина указывает несколько мужчин (от 0 до М), за которых она согласна выйти замуж. Требуется заключить наибольшее количество моногамных браков.
Следующая страница 
Вопросы и задания
Cкачать материалы урока
