ЧАСТЬ II. ПРИЛОЖЕНИЯ ТЕОРИИ ГРАФОВ

Во второй части книги обсуждается широкий круг прикладных задач теории графов. Наиболее длинная глава 6 посвящается краткому рассмотрению большого числа примеров, иллюстрирующих возможные приложения. Некоторые из задач, затронутых в этих примерах, сформулированы и решены, некоторые — только сформулированы. Часть же задач вообще дается на очень общем описательном уровне просто для того, чтобы читатель смог «почувствовать вкус» к использованию теории графов. Более подробное рассмотрение задач можно найти в соответствующей литературе.

В отличие от главы 6, материал главы 7, посвященный двум особенно важным прикладным разделам теории графов, дается на гораздо более глубоком уровне.

В этой главе рассмотрены линейные потоки в сетях, сформулированы с графотеоретической точки зрения общие методы максимизации потоков и минимизации стоимости.

Глава 6. ПРИКЛАДНЫЕ ЗАДАЧИ ТЕОРИИ ГРАФОВ

6.1. Введение

Изучать теорию графов без учета возможных приложений — значит потерять основную ее сущность. Учитывая важность сказанного, мы разделили книгу на две части. Вторая часть Полностью посвящена краткому из? ложению некоторых интересных прикладных задач. Цель настоящей главы состоит в том, чтобы с помощью

примеров научить читателя описывать модели научных и технических задач на языке теории графов и проиллю» стрировать различные способы использования графов для формулировки и решения задач. После проработки каждого раздела читателю рекомендуется исследовать основные свойства рассмотренных графов. В некоторых случаях, таких, например, как в задаче о раскрашенных кубах, использование простой идеи графа, при правильном его выборе, оказывается очень эффективным. Решение этой задачи с помощью графов дает четкое объяснение головоломке, известной под названием «танталовы» муки («ложные надежды»), решение которой методом проб и ошибки оказывается очень громоздким. В других случаях проявляются более сложные графотеоретические свойства. Некоторые из этих свойств нашли применение в промышленном и государственном управлении. Например, ПЕРТ является теперь основным инструментом планирования, который обеспечивает наиболее эффективное достижение поставленных целей. Простое понятие графа возникает и используется в очень многих случаях.

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