Настоящее пособие написано по материалам курсов “Проектирование эффективных алгоритмов" и “Алгоритмы па графах”, которые автор неоднократно в 1990-2012гг. читал в Тверском государственном университете. Основное внимание уделено рассмотрению широко используемых в различных приложениях типовых алгоритмических задач, таких, как представления графов, отношение достижимости и транзитивное замыкание графа, компоненты сильной связности ориентированного графа и его базы, деревья и их обходы, минимальные остовные деревья, поиск в глубину, поиск кратчайших путей и потоки в транспортных сетях. Рассмотрены также многие сложные (NP-полные) задачи на графах и возможные подходы к их решению. В последней главе продемонстрировано применение теории графов к анализу социальных сетей. Каждая глава завершается разделом с задачами, которые могут служить материалом для проведения практических занятий и домашних заданий. Ряд задач содержат дополнительный материал, по тем или иным причинам нс вошедший в основной текст. Список литературы заведомо неполон, он включает лишь учебники, монографии и статьи, непосредственно использованные при написании этого пособия. В них можно найти дальнейшие ссылки на многочисленные источники, посвященные алгоритмам на графах.
