Граф продукта
В теории графов произведение графов — это бинарная операция над графами . В частности, это операция, которая берет два графа G 1 и G 2 и создает граф H со следующими свойствами:
- Множество вершин H ( — это декартово произведение V ( G 1 ) × V ( G 2 ) , где V и G 1 ) и V ( G 2 ) — множества вершин G 1 . G 2 соответственно
- Две вершины ( a 1 , a 2 ) и ( b 1 , b 2 ) графа H соединены ребром , если и только если условие относительно a 1 , b 1 в G 1 и a 2 , b 2 в G 2 выполнено.
Произведения графа различаются тем, в чем именно заключается это условие. равны или нет вершины an , , bn Всегда речь идет о том в G n или соединены ребром.
Терминология и обозначения для конкретных графовых продуктов в литературе довольно сильно различаются; даже если следующее можно считать несколько стандартным, читателям рекомендуется проверить, какое определение конкретный автор использует для графического продукта, особенно в старых текстах.
Даже для более стандартных определений в литературе не всегда единообразно, как обращаться с циклами . Приведенные ниже формулы для количества ребер в продукте также могут не работать при включении петель. Например, тензорное произведение одиночной вершинной петли на себя представляет собой другую одиночную вершинную петлю с , и не как формула предложил бы.
Обзорная таблица
[ редактировать ]В следующей таблице показаны наиболее распространенные графические продукты с обозначающее «соединено ребром с», и обозначающий несмежность. Пока допускает равенство, означает, что они должны быть различными и несмежными. Перечисленные здесь символы операторов ни в коем случае не являются стандартными, особенно в старых статьях.
Имя | Условие для | Количество ребер | Пример | |
---|---|---|---|---|
с сокращенно | ||||
Декартово произведение (коробочный продукт) | ||||
Тензорное произведение (произведение Кронекера, категориальный товар) | ||||
Лексикографический продукт или | ||||
Сильный продукт (Нормальный продукт, И продукт) | ||||
Со-нормальный продукт (дизъюнктивное произведение, произведение ИЛИ) | ||||
Модульный продукт | ||||
Укорененный продукт | см. статью | |||
Зигзагообразное изделие | см. статью | см. статью | см. статью | |
Запасной продукт | ||||
Гомоморфный продукт [1] [3] |
В общем случае произведение графа определяется любым условием для что можно выразить через и .
Мнемоника
[ редактировать ]Позволять быть полным графом с двумя вершинами (т.е. с одним ребром). Графики продуктов , , и выглядеть точно так же, как график, представляющий оператор. Например, представляет собой четырехцикл (квадрат) и — полный граф на четырех вершинах.
The обозначение лексикографического произведения служит напоминанием о том, что это произведение не коммутативно. Полученный график выглядит как замена копии для каждой вершины .
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Jump up to: а б Роберсон, Дэвид Э.; Манчинска, Лаура (2012). «Гомоморфизмы графов для квантовых игроков». Журнал комбинаторной теории, серия B. 118 : 228–267. arXiv : 1212.1724 . дои : 10.1016/j.jctb.2015.12.009 .
- ^ Бачик Р.; Махаджан, С. (1995). «Полуопределенное программирование и его приложения к задачам NP». Вычисления и комбинаторика . Конспекты лекций по информатике. Том. 959. с. 566. дои : 10.1007/BFb0030878 . ISBN 978-3-540-60216-3 .
- ^ Домашний продукт [2] является графическим дополнением гомоморфного произведения. [1]
Ссылки
[ редактировать ]- Имрих, Вильфрид; Клавжар, Санди (2000). Графики продуктов: структура и узнаваемость . Уайли. ISBN 978-0-471-37039-0 .