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