ОБХОДЫ ГРАФА (ПОИСК В ГРАФЕ)

Цели и задачи лекции: Изучить методы поиска в графе.

Рассматриваемые вопросы: Поиск в ширину. Поиск в глубину.

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

Примеры приложений теории графов.

1. «Транспортные» задачи, в которых вершинами графа являются пункты, а ребрами - дороги (автомобильные, железные и др.) и/или другие транспортные (например, авиационные) маршруты. Другой пример - сети (информационные, энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства (источники) и потребления (получатели), а ребрами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоковгрузов, размещения пунктов производства и потребления и т.д., иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках.

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

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

4. Управление проектами. С точки зрения теории графов проект - совокупность операций и зависимостей между ними {сетевой график). Хрестоматийным примером является проектстроительства некоторого объекта. Совокупность моделей и методов, использующих язык и результаты теории графов и ориентированных на решение задач управления проектами, получила название календарно-сетевого планирования и управления (КСПУ). В рамках КСПУ решаются задачи определения последовательности выполнения операций и распределения ресурсов междуними, оптимальных с точки зрения тех или иных критериев (времени выполнения проекта, затрат, риска и др.).

5. Модели коллективов и групп, используемые в социологии,основываются на представлении людей или их групп в виде вершин, а отношений между ними (например, отношений знакомства,доверия, симпатии и т.д.) - в виде ребер или дуг. В рамках подобного описания решаются задачи исследования структуры социальных групп, их сравнения, определения агрегированных показателей, отражающих степень напряженности, согласованностивзаимодействия, и др.

6. Модели организационных структур, в которых вершинамиявляются элементы организационной системы, а ребрами или дугами - связи (информационные, управляющие, технологическиеи др.) между ними.

Рассмотрим задачаи анализа графов с целью выявления их структуры и вычисления метрических характеристик. Многие задачи такого рода могут быть решены путем систематического обхода графа с посещением всех его вершин и исследованием всех его ребер.