Операции с графами

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

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