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

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

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

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

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

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

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

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

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

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

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

• объединение графов: грамм₁ ∪ грамм₂. Есть два определения. В наиболее распространенном несвязное объединение графов, объединение предполагается непересекающимся. Реже (хотя в большей степени соответствует общему определению союз в математике) объединение двух графов определяется как граф (V₁ ∪ V₂, E₁ ∪ E₂).
• пересечение графа: грамм₁ ∩ грамм₂ = (V₁ ∩ V₂, E₁ ∩ E₂);^[1]
• соединение графа: граф со всеми ребрами, которые соединяют вершины первого графа с вершинами второго графа. Это коммутативная операция (для немаркированных графов);^[2]
• графические продукты на основе декартово произведение наборов вершин:
  • декартово графическое произведение: это коммутативная и ассоциативная операция (для немеченых графов),^[2]
  • лексикографический граф произведение (или композиция графа): это ассоциативная (для немаркированных графов) и некоммутативная операция,^[2]
  • продукт с сильным графом: это коммутативная и ассоциативная операция (для немеченых графов),
  • произведение тензорного графа (или произведение прямого графа, произведение категориального графа, произведение кардинального графа, произведение графа Кронекера): это коммутативная и ассоциативная операция (для немаркированных графов),
  • зигзагообразный граф продукта;^[3]
• Графический продукт на основе других продуктов:
  • продукт с корневым графом: это ассоциативная операция (для немаркированных, но корневых графов),
  • корона граф продукта: это некоммутативная операция;^[4]
• композиция последовательно-параллельного графа:
  • композиция параллельного графа: это коммутативная операция (для немаркированных графов),
  • композиция графа серии: это некоммутативная операция,
  • композиция исходного графа: это коммутативная операция (для немаркированных графов);
• Строительство Hajós.

Примечания

1. Bondy, J. A .; Мурти, США (2008). Теория графов. Тексты для выпускников по математике. Springer. п. 29. ISBN  978-1-84628-969-9.
2. Харари, Ф. Теория графов. Ридинг, Массачусетс: Аддисон-Уэсли, 1994.
3. Reingold, O .; Vadhan, S .; Вигдерсон, А. (2002). «Энтропийные волны, зигзагообразный граф и новые расширители постоянной степени». Анналы математики. 155 (1): 157–187. arXiv:математика / 0406038. Дои:10.2307/3062153. JSTOR  3062153. МИСТЕР  1888797.
4. Фрухт, Роберт; Харари, Фрэнк (1970). «О короне двух графов». Aequationes Mathematicae. 4: 322–324. Дои:10.1007 / bf01844162. HDL:2027.42/44326.