Графические операции

Процедуры построения новых графов в теории графов

В математической области теории графов графовые операции — это операции , которые производят новые графы из исходных. Они включают как унарные (один вход), так и бинарные (два входа) операции.

Унарные операции

Унарные операции создают новый граф из одного исходного графа.

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

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

Расширенные операции

Расширенные операции создают новый граф из исходного путем сложного изменения, например:

• транспонировать граф ;
• дополнительный граф ;
• линейный график ;
• граф минор ;
• переписывание графа ;
• мощность графика ;
• двойной график ;
• медиальный график ;
• график частного ;
• Преобразование Y-Δ ;
• Мыцельский .

Бинарные операции

Бинарные операции создают новый граф из двух исходных графов G ₁ = ( V ₁ , E ₁ ) и G ₂ = ( V ₂ , E ₂ ) , например:

• Объединение графов: G ₁ ∪ G ₂ . Существует два определения. В наиболее распространенном из них, непересекающемся объединении графов , объединение предполагается непересекающимся. Реже (хотя и более соответствующим общему определению объединения в математике) объединение двух графов определяется как граф ( V ₁ ∪ V ₂ , E ₁ ∪ E ₂ ) .
• пересечение графов: G ₁ ∩ G ₂ = ( V ₁ ∩ V ₂ , E ₁ ∩ E ₂ ) ; ^[1]
• graph join: . Граф со всеми ребрами, которые соединяют вершины первого графа с вершинами второго графа. Это коммутативная операция (для непомеченных графов); ^[2] ${\displaystyle G_{1}\nabla G_{2}}$
• Графические произведения, основанные на декартовом произведении множеств вершин:
  • Декартово произведение графов : это коммутативная и ассоциативная операция (для непомеченных графов), ^[2]
  • лексикографическое графовое произведение (или графовая композиция): это ассоциативная (для непомеченных графов) и некоммутативная операция, ^[2]
  • сильное графовое произведение : это коммутативная и ассоциативная операция (для непомеченных графов),
  • произведение тензорных графов (или прямое произведение графов, категориальное произведение графов, кардинальное произведение графов, произведение графов Кронекера): это коммутативная и ассоциативная операция (для непомеченных графов),
  • зигзагообразный граф-продукт ; ^[3]
• Графический продукт на основе других продуктов:
  • произведение корневых графов : это ассоциативная операция (для непомеченных, но корневых графов),
  • Произведение коронного графа: это некоммутативная операция; ^[4]
• Состав последовательно-параллельного графа :
  • параллельная композиция графов: это коммутативная операция (для непомеченных графов),
  • Составление графа ряда: это некоммутативная операция,
  • композиция исходного графа: это коммутативная операция (для непомеченных графов);
• Строительство Хайош .

Примечания

1. Бонди, JA; Мурти, USR (2008). Теория графов . Выпускные тексты по математике. Springer. стр. 29. ISBN 978-1-84628-969-9.
2. Харари, Ф. Теория графов . Рединг, Массачусетс: Addison-Wesley, 1994.
3. Рейнгольд, О.; Вадхан, С.; Вигдерсон, А. (2002). «Волны энтропии, произведение зигзагообразных графов и новые расширители постоянной степени». Annals of Mathematics . 155 (1): 157–187. arXiv : math/0406038 . doi :10.2307/3062153. JSTOR  3062153. MR  1888797.
4. Фрухт, Роберт ; Харари, Фрэнк (1970). «О короне двух графов». Математические уравнения . 4 : 322–324. дои : 10.1007/bf01844162. hdl : 2027.42/44326 .