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

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

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

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

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

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

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

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

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

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

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

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