Операции над графами

Операции над графами образуют новые графы из старых. Операции можно разделить на следующие основные категории.

Одноместные (унарные) операции

Одноместная операция создаёт новый граф из старого.

Элементарные операции

Иногда этот класс операций называют «операции редактирования» графов. Они создают новый граф из исходного графа путём простых, локальных изменений, таких как добавление или удаление вершины или дуги, слияние или расщепление вершин, стягивание графа, и т.д.

Сложные операции

Сложные операции создают новый граф из начального при помощи комплексных изменений, таких как:

• Рёберный граф
• Двойственный граф
• Дополнение графа
• Минор графа
• Степень графа: k-я степень G^k графа G — это суперграф, сформированный добавлением всех дуг между всеми парами вершин G с расстоянием не более k. Вторая степень графа также называется его квадратом.
• Преобразование треугольник-звезда
• Граф Мычельского (Мычельскиан)

Двуместные (бинарные) операции

Двуместная операция создаёт новый граф из двух исходных графов G1(V1, E1) и G2(V2, E2):

• Несвязанное объединение графов или просто объединение графов — это граф, содержащий объединение (непересекающихся) множеств вершин V1 и V2 графов и множеств дуг, то есть ${\displaystyle U(V1\cup V2,E1\cup E2)}$^[1]. Операция является коммутативной и ассоциативной (для непомеченных графов).
• Соединением двух графов называется объединение двух графов, в которое добавлены все дуги, соединяющие вершины обоих графов (то есть дуги, вершины которых взяты из разных графов)^[1]. Операция является коммутативной (для непомеченных графов).
• Произведение графов основанное на прямом произведении множеств вершин:
  • Прямое произведение графов^[1] является коммутативной и ассоциативной операцией (для непомеченных графов).
  • Лексикографическое произведение графов^[1]. Операция не является ни коммутативной, ни ассоциативной.
  • Сильное произведение графов.
  • Тензорное произведение графов, иногда также называемое прямым произведением или произведением Кронекера. Операция является коммутативной (для непомеченных графов).
  • Зигзаг-произведение^[2].

Пусть [N] означает множество целых чисел от 1 до N. Для определения зигзаг-произведения используются k-регулярные графы, дуги которых раскрашены в k цветов. Для каждого цвета i и вершины v пусть v[i] означает соседа вершины v, соединённого дугой цвета i. Пусть G1 — D1-регулярный граф над [N1] и G2 — D2-регулярный граф над [D1]. Тогда зигзаг-произведением H будет граф со множеством вершин [N1] × [D1], в котором для любого n из [N1], d из [D1], и i, j из [D2] вершина (n, d) соединена с (n[d[i]], d[i][j]). Это определение используется для построения экспандеров.

• Другие операции над графами с именем «произведение»:
  • Корневое произведение графов. Операция не является ни коммутативной, ни ассоциативной.
  • Коронарное произведение^[англ.] графов G1 и G2 (определение введено Фрухтом и Харари^[3]) — это граф, являющийся объединением одной копии графа G1 и |V1| копий графа G2 (|V1| — число вершин графа G1), в котором каждая вершина копии G1 соединена со всеми вершинами всех копий G2.
• Создание параллельно-последовательных графов:
  • Параллельная композиция. Операция является коммутативной (для непомеченных графов)^[4].
  • Последовательная композиция. Операция некоммутативна^[4].
  • Композиция источников (слияние источников). Коммутативная операция (для непомеченных графов).
• графа Хайоша.

Примечания

1. Ф. Харари. Теория графов = Graph Theory / Перевод с английского и предисловие В. П. Козырева. — 2. — М.: Едиториал УРСС, 2003. — 296 с.
2. Reingold, O.; Vadhan, S.; Wigderson, A. Entropy waves, the zig-zag graph product, and new constant-degree expanders // Annals of Mathematics. — 2002. — Т. 155, вып. 1. — С. 157—187. — doi:10.2307/3062153. — JSTOR 3062153.
3. Robert Frucht and Frank Harary. «On the coronas of two graphs», Aequationes Math., 4:322-324, 1970.
4. Евстигнеев В. А., Касьянов В. Н. Series-parallel poset // Словарь по графам в информатике / Под редакцией проф. Виктора Николаевича Касьянова. — Новосибирск: ООО «Сибирское Научное Издательство», 2009. — Т. 17. — (Конструирование и оптимизация программ). — ISBN 978-591124-036-3.