Глава 17. Свойства и типы графов. чае обработки графов, решение таких задач сопряжено с особыми трудностями ввиду сложности определения характеристик всех типов графов

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

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

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

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