Операции над графами образуют новые графы из старых. Операции можно разделить на следующие основные категории.
Одноместные (унарные) операции
Одноместная операция создаёт новый граф из старого.
Элементарные операции
Иногда этот класс операций называют «операции редактирования» графов. Они создают новый граф из исходного графа путём простых, локальных изменений, таких как добавление или удаление вершины или дуги, слияние или расщепление вершин, стягивание графа, и т.д.
Сложные операции
- Рёберный граф
- Двойственный граф
- Дополнение графа
- Минор графа
- Возведение в степень: k-я степень Gk графа G — это суперграф, сформированный добавлением всех дуг между всеми парами вершин G с расстоянием не более k. Вторая степень графа также называется его квадратом.
- Граф Мычельского (Мычельскиан)
Двуместные (бинарные) операции
Двуместная операция создаёт новый граф из двух исходных графов G1(V1, E1) и G2(V2, E2):
- Несвязанное объединение графов или просто объединение графов — это граф, содержащий объединение (непересекающихся) множеств вершин V1 и V2 графов и множеств дуг, то есть [1]. Операция является коммутативной и ассоциативной (для непомеченных графов).
- Соединением двух графов называется объединение двух графов, в которое добавлены все дуги, соединяющие вершины обоих графов (то есть дуги, вершины которых взяты из разных графов)[1]. Операция является коммутативной (для непомеченных графов).
- Произведение графов основанное на прямом произведении множеств вершин:
- Прямое произведение графов[en][1] является коммутативной и ассоциативной операцией (для непомеченных графов).
- Лексикографическое произведение графов[en][1]. Операция не является ни коммутативной, ни ассоциативной.
- Строгое произведение графов[en].
- Тензорное произведение графов?!, иногда также называемое прямым произведением или произведением Кронекера. Операция является коммутативной (для непомеченных графов).
- Зигзаг-произведение[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]). Это определение используется для построения экспандеров.
- Другие операции над графами с именем «произведение»:
- Корневое произведение графов. Операция не является ни коммутативной, ни ассоциативной.
- Коронарное произведение[en] графов G1 и G2 (определение введено Фрухтом[en] и Харари[3]) — это граф, являющийся объединением одной копии графа G1 и |V1| копий графа G2 (|V1| — число вершин графа G1), в котором каждая вершина копии G1 соединена со всеми вершинами всех копий G2.
- Создание параллельно-последовательных графов:
- Построение графа Хайоша[en].
Примечания
- 1 2 3 4 Ф. Харари. Теория графов = Graph Theory / Перевод с английского и предисловие В. П. Козырева. — 2. — М.: Едиториал УРСС, 2003. — 296 с.
- ↑ 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.
- ↑ Robert Frucht and Frank Harary. «On the coronas of two graphs», Aequationes Math., 4:322-324, 1970.
- 1 2 Евстигнеев В. А., Касьянов В. Н. Series-parallel poset // Словарь по графам в информатике / Под редакцией проф. Виктора Николаевича Касьянова. — Новосибирск: ООО «Сибирское Научное Издательство», 2009. — Т. 17. — (Конструирование и оптимизация программ). — ISBN 978-591124-036-3.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .