Операции над графами (Khyjgenn ug; ijgsgbn)

Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

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

[править | править код]

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

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

[править | править код]

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

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

[править | править код]

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

Пусть [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]). Это определение используется для построения экспандеров.

  • Другие операции над графами с именем «произведение»:
  • Создание параллельно-последовательных графов:
    • Параллельная композиция. Операция является коммутативной (для непомеченных графов)[4].
    • Последовательная композиция. Операция некоммутативна[4].
    • Композиция источников (слияние источников). Коммутативная операция (для непомеченных графов).
  • графа Хайоша.

Примечания

[править | править код]
  1. 1 2 3 4 Ф. Харари. Теория графов = 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. 1 2 Евстигнеев В. А., Касьянов В. Н. Series-parallel poset // Словарь по графам в информатике / Под редакцией проф. Виктора Николаевича Касьянова. — Новосибирск: ООО «Сибирское Научное Издательство», 2009. — Т. 17. — (Конструирование и оптимизация программ). — ISBN 978-591124-036-3.