Составители:
Рубрика:
9
Классификация задач теории графов
Как уже было отмечено выше, в значительной мере, задачи теории графов
берут свое начало в химии, физике, биологии, социологии и других прикладных
дисциплинах. Формулировка задач на языке теории графов часто облегчает
процесс вычислений и, что более важно, позволяет на едином языке
формулировать задачи, кажущиеся далекими друг от друга в своей
первоначальной постановке. Задачи, возникающие в теории графов, условно
можно разбить на два класса:
1. Собственные задачи теории графов, в частности, задачи подсчета числа
объектов с заданными свойствами.
2. Задачи, связанные с построением того или иного объекта на графе,
явного задания некоторой “ наилучшей” конфигурации на графе. Это, так
называемые, алгоритмы на графах.
Приведем примеры некоторых задач, принадлежащих этим классам.
Начнем с задач первого класса.
Сколько существует графов с некоторыми заданными свойствами? Вот
общая задача подсчета.
§ 1.2. Задача о минимальном числе аварий
Вернемся к сформулированной во введении задачи о нанесении схемы на
печатную плату. Заменяя эту схему соответствующим графом, мы приходим к
выводу, что поставленная задача будет разрешима только в том случае, если в
графе нет подграфов типа Понтрягина-Куратовского, о которых шла речь выше.
Ослабим требование на пересечение проводников во внутренних точках и
разрешим им пересекаться, но так, чтобы получилось минимальное число
пересечений. Тогда приходим к известной прикладной задаче о минимальном
числе аварий, которая формулируется следующим образом:
На кирпичном заводе имеется m печей и n платформ, на которые
укладываются кирпичи для последующей их транспортировки. От каждой печи
кирпичи можно перевозить вагонетками ко всем платформам (рис.2).
m печей
Страницы
- « первая
- ‹ предыдущая
- …
- 7
- 8
- 9
- 10
- 11
- …
- следующая ›
- последняя »
