В математике , А график , продукт представляет собой бинарную операцию на графиках . В частности, это операция, которая берет два графа G 1 и G 2 и создает граф 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 .
Графические произведения различаются тем, что это за условие. Всегда важно, равны ли вершины a n , b n в G n или соединены ли они ребром.
Терминология и обозначения для конкретных графических продуктов в литературе довольно сильно различаются; даже если нижеследующее может считаться несколько стандартным, читателям рекомендуется проверить, какое определение конкретный автор использует для графического продукта, особенно в более старых текстах.
Обзорная таблица
В следующей таблице показаны наиболее распространенные графические продукты с обозначающий «соединен ребром с», и означает отсутствие связи. Перечисленные здесь символы операторов ни в коем случае не являются стандартными, особенно в старых работах.
Имя | Условие для | Количество ребер | Пример | |
---|---|---|---|---|
с участием сокращенно | ||||
Декартово произведение | ||||
Тензорное произведение ( произведение Кронекера, категориальное произведение) | ||||
Лексикографический продукт или же | ||||
Сильный продукт (нормальный продукт И продукт) | ||||
Сопутствующий продукт (дизъюнктивный продукт, ИЛИ продукт) | ||||
Модульный продукт | ||||
Укоренившийся продукт | см. статью | |||
Зигзагообразный продукт | см. статью | см. статью | см. статью | |
Заменяемый продукт | ||||
Гомоморфное произведение [1] [3] |
В общем, графическое произведение определяется любым условием для что может быть выражено в терминах а также .
Мнемонический
Позволять полный граф с двумя вершинами (т.е. с одним ребром). Графики продукта, , а также выглядят точно так же, как график, представляющий оператора. Например, представляет собой четыре цикла (квадрат) и полный граф с четырьмя вершинами. В Обозначение для лексикографического произведения служит напоминанием о том, что это произведение не коммутативно
Смотрите также
Заметки
- ^ a b Роберсон, Дэвид Э .; Манчинска, Лаура (2012). «Гомоморфизмы графов для квантовых игроков». Журнал комбинаторной теории, серии B . 118 : 228–267. arXiv : 1212,1724 . DOI : 10.1016 / j.jctb.2015.12.009 .
- ^ Bačík, R .; Махаджан, С. (1995). «Полуопределенное программирование и его приложения к задачам NP». Вычислительная техника и комбинаторика . Конспект лекций по информатике. 959 . п. 566. DOI : 10.1007 / BFb0030878 . ISBN 978-3-540-60216-3.
- ^ Гом-произведение [2] является графическим дополнением гомоморфного произведения. [1]
Рекомендации
- Имрих, Вильфрид; Клавжар, Санди (2000). Графики продуктов: структура и узнаваемость . Вайли. ISBN 978-0-471-37039-0{{противоречивые цитаты}}CS1 maint: postscript ( ссылка ).