В информатике и математике используются следующие операции над графами:
Одноместные (унарные) операции: 1
- Элементарные операции. 1 Создают новый граф из исходного путём простых, локальных изменений. 1 Например, добавление или удаление вершины или дуги, слияние или расщепление вершин, стягивание графа. 1
- Сложные операции. 1 Создают новый граф из начального при помощи комплексных изменений. 1 Например, рёберный граф, двойственный граф, дополнение графа, минор графа, степень графа. 1
Двуместные (бинарные) операции: 1
- Объединение графов. 13 В один граф добавляются все вершины и рёбра одного и второго графа. 3
- Пересечение графов. 3 В один граф добавляются только те вершины и рёбра, которые одинаковые и у одного, и у второго графа. 3
- Кольцевая сумма. 3 В кольцевой граф добавляются те рёбра, которые разные у обоих графов, а одинаковые убираются (вершины остаются все). 3
- Замыкание или отождествление. 3 Пара вершин замыкается новой вершиной, после чего дуга или ребро, находящееся между ними, станет петлёй. 3
- Стягивание. 3 Операция удаления дуги или ребра и отождествления его концевых вершин. 3 Две вершины совмещаются в одну, а ребро или дуга, находящаяся между ними, удаляется. 3