Операции с графами
В математической области графов теории операции над графами — это операции , которые создают новые графы из исходных. Они включают как унарные (один вход), так и двоичные (два входа) операции.
Унарные операции
[ редактировать ]Унарные операции создают новый граф из одного исходного графа.
Элементарные операции
[ редактировать ]Элементарные операции или операции редактирования, которые также известны как операции редактирования графа, создают новый граф из исходного путем простого локального изменения, такого как добавление или удаление вершины или ребра, слияние и разделение вершин, сжатие ребра. , и т. д.Расстояние редактирования графа между парой графов — это минимальное количество элементарных операций, необходимых для преобразования одного графа в другой.
Расширенные операции
[ редактировать ]Расширенные операции создают новый график из исходного путем сложного изменения, например:
- транспонировать график ;
- дополняющий граф ;
- линейный график ;
- граф минор ;
- перезапись графа ;
- мощность графика ;
- двойной граф ;
- медиальный график ;
- график коэффициентов ;
- преобразование Y-Δ ;
- Мицельский .
Бинарные операции
[ редактировать ]Бинарные операции создают новый граф из двух исходных графов G 1 = ( V 1 , E 1 ) и G 2 = ( V 2 , E 2 ) , например:
- объединение графов: G 1 ∪ G 2 . Есть два определения. В наиболее распространенном из них — непересекающемся объединении графов — объединение предполагается непересекающимся. Реже (хотя и более соответствует общему определению объединения в математике) объединение двух графов определяется как граф ( V 1 ∪ V 2 , E 1 ∪ E 2 ) .
- пересечение графа: г 1 ∩ г 2 знак равно ( V 1 ∩ V 2 , E 1 ∩ E 2 ) ; [1]
- соединение графа: . граф со всеми ребрами, соединяющими вершины первого графа с вершинами второго графа. Это коммутативная операция (для неразмеченных графов); [2]
- графические продукты на основе декартова произведения наборов вершин:
- декартово произведение графа : это коммутативная и ассоциативная операция (для немаркированных графов), [2]
- лексикографическое произведение графа (или композиция графа): это ассоциативная (для неразмеченных графов) и некоммутативная операция, [2]
- сильное произведение графа : это коммутативная и ассоциативная операция (для немаркированных графов),
- произведение тензорного графа (или произведение прямого графа, произведение категориального графа, произведение кардинального графа, произведение графа Кронекера): это коммутативная и ассоциативная операция (для немаркированных графов),
- произведение зигзагообразного графика ; [3]
- график продукта на основе других продуктов:
- произведение корневого графа : это ассоциативная операция (для немаркированных, но корневых графов),
- произведение графа короны : это некоммутативная операция; [4]
- последовательно-параллельная композиция графа :
- параллельная композиция графов: это коммутативная операция (для немаркированных графов),
- композиция графа серий: это некоммутативная операция,
- композиция исходного графа: это коммутативная операция (для неразмеченных графов);
- Судостроение .
Примечания
[ редактировать ]- ^ Бонди, Дж.А.; Мурти, USR (2008). Теория графов . Тексты для аспирантов по математике. Спрингер. п. 29. ISBN 978-1-84628-969-9 .
- ^ Перейти обратно: а б с Харари, Ф. Теория графов . Ридинг, Массачусетс: Аддисон-Уэсли, 1994.
- ^ Рейнгольд, О.; Вадхан, С.; Вигдерсон, А. (2002). «Волны энтропии, произведение зигзагообразного графа и новые расширители постоянной степени». Анналы математики . 155 (1): 157–187. arXiv : math/0406038 . дои : 10.2307/3062153 . JSTOR 3062153 . МР 1888797 .
- ^ Фрухт, Роберт ; Харари, Фрэнк (1970). «О короне двух графов». Математические уравнения . 4 : 322–324. дои : 10.1007/bf01844162 . hdl : 2027.42/44326 .