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

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

Унарные операции [ править ]

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

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

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

Расширенные операции [ править ]

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

Бинарные операции [ править ]

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

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

Заметки [ править ]

^ Бонди, JA; Мурти, USR (2008). Теория графов . Тексты для выпускников по математике. Springer. п. 29. ISBN 978-1-84628-969-9.
^ Б с Харари, F . Теория графов . Ридинг, Массачусетс: Аддисон-Уэсли, 1994.
^ Reingold, O .; Vadhan, S .; Вигдерсон, А. (2002). «Энтропийные волны, зигзагообразный граф и новые расширители постоянной степени». Анналы математики . 155 (1): 157–187. arXiv : math / 0406038 . DOI : 10.2307 / 3062153 . JSTOR 3062153 . MR 1888797 .
^ Frucht, Роберт ; Харари, Фрэнк (1970). «О короне двух графов». Aequationes Mathematicae . 4 : 322–324. DOI : 10.1007 / bf01844162 . ЛВП : 2027,42 / 44326 .

[bondy_murty-1] Бонди, JA; Мурти, USR (2008). Теория графов . Тексты для выпускников по математике. Springer. п. 29. ISBN 978-1-84628-969-9.

[harary-2] Б с Харари, F . Теория графов . Ридинг, Массачусетс: Аддисон-Уэсли, 1994.

[3] Reingold, O .; Vadhan, S .; Вигдерсон, А. (2002). «Энтропийные волны, зигзагообразный граф и новые расширители постоянной степени». Анналы математики . 155 (1): 157–187. arXiv : math / 0406038 . DOI : 10.2307 / 3062153 . JSTOR 3062153 . MR 1888797 .

[4] Frucht, Роберт ; Харари, Фрэнк (1970). «О короне двух графов». Aequationes Mathematicae . 4 : 322–324. DOI : 10.1007 / bf01844162 . ЛВП : 2027,42 / 44326 .

[1]