Графические операции - Graph operations
Графические операции производят новые графы из начальных. Их можно разделить на следующие основные категории.
Унарные операции
Унарные операции создают новый граф из единственного исходного графа.
Элементарные операции
Элементарные операции или операции редактирования, также известные как операции редактирования графа, создание нового графа из одного исходного простым локальным изменением, таким как добавление или удаление вершины или ребра, слияние и разделение вершин, сжатие ребер и т. д. Расстояние редактирования графа между парой Графы - это минимальное количество элементарных операций, необходимых для преобразования одного графа в другой.
Расширенные операции
Расширенные операции создают новый граф из начального путем сложных изменений, таких как:
- транспонировать график ;
- дополнительный граф ;
- линейный график ;
- граф минор ;
- переписывание графов ;
- мощность графа ;
- дуальный граф ;
- медиальный граф ;
- фактор-граф ;
- Y-Δ преобразование ;
- Мицельский .
Бинарные операции
Бинарные операции создают новый граф из двух исходных графов G 1 = ( V 1 , E 1 ) и G 2 = ( V 2 , E 2 ) , например:
- объединение графов: G 1 ∪ G 2 . Есть два определения. В наиболее распространенном - несвязном объединении графов объединение считается несвязным. Менее часто (хотя и более в соответствии с общим определением союза в области математики) объединение двух графов определяется как граф ( V 1 ∪ V 2 , Е 1 ∪ Е 2 ) .
- График пересечения: G 1 ∩ G 2 = ( V 1 ∩ V 2 , Е 1 ∩ Е 2 ) ;
- соединение графа: граф со всеми ребрами, которые соединяют вершины первого графа с вершинами второго графа. Это коммутативная операция (для немаркированных графов);
-
графические произведения, основанные на декартовом произведении множеств вершин:
- декартово графовое произведение : это коммутативная и ассоциативная операция (для немаркированных графов),
- лексикографическое графовое произведение (или композиция графа): это ассоциативная (для немаркированных графов) и некоммутативная операция,
- сильное графовое произведение : это коммутативная и ассоциативная операция (для немаркированных графов),
- произведение тензорного графа (или произведение прямого графа, произведение категориального графа, произведение кардинального графа, произведение графа Кронекера): это коммутативная и ассоциативная операция (для немаркированных графов),
- зигзагообразное графическое произведение ;
- Графический продукт на основе других продуктов:
- продукт корневого графа : это ассоциативная операция (для немаркированных, но корневых графов),
- произведение графа короны : это некоммутативная операция;
-
составление последовательно-параллельного графа :
- композиция параллельных графов: это коммутативная операция (для немаркированных графов),
- композиция графа серии: это некоммутативная операция,
- композиция исходного графа: это коммутативная операция (для немаркированных графов);
- Строительство 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 .