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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Одноместные (унарные) операции[править | править вики-текст]

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

Элементарные операции[править | править вики-текст]

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

Сложные операции[править | править вики-текст]

Двуместные (бинарные) операции[править | править вики-текст]

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

  • Несвязанное объединение графов или просто объединение графов - это граф, содержащий объединение (непересекающихся) множеств вершин V1 и V2 графов и множеств дуг, то есть, U(V1 \cup V2, E1 \cup E2) .[1]

Операция является коммутативной и ассоциативной (для непомеченных графов[en]).

Пусть [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]:
    • Параллельная композиция. Операция является коммутативной (для непомеченных графов)[4]
    • Последовательная композиция. Операция некоммутативна.[4]
    • Композиция источников (слияние источников). Коммутативная операция (для непомеченных графов)
  • Построение графа Хайоша[en]

Ссылки[править | править вики-текст]

  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. — В. 1. — Т. 155. — С. 157–187. — DOI:10.2307/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