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