В математика, а граф продукта это бинарная операция на графики. В частности, это операция, которая занимает два графика грамм1 и грамм2 и строит график ЧАС со следующими свойствами:
В набор вершин из ЧАС это Декартово произведениеV(грамм1) × V(грамм2), куда V(грамм1) и V(грамм2) - множества вершин грамм1 и грамм2, соответственно.
Две вершины (а1, а2) и (б1, б2) из ЧАС связаны край, если только условие о а1, б1 в грамм1 и а2, б2 в грамм2 выполняется.
Графические произведения различаются тем, что это за условие. Всегда важно, действительно ли вершины ап, бп в граммп равны или соединены ребром.
Терминология и обозначения для конкретных графических продуктов в литературе довольно сильно различаются; даже если нижеследующее может считаться несколько стандартным, читателям рекомендуется проверить, какое определение конкретный автор использует для графического продукта, особенно в старых текстах.
В следующей таблице показаны наиболее распространенные графические продукты с означает «соединен ребром с», и означает отсутствие связи. Перечисленные здесь символы операторов ни в коем случае не являются стандартными, особенно в старых работах.
В общем, графическое произведение определяется любым условием для что может быть выражено через и .
Мнемонический
Позволять - полный граф с двумя вершинами (то есть с одним ребром). Графики продукта , , и выглядят точно так же, как график, представляющий оператора. Например, представляет собой четырехцикл (квадрат) и - полный граф с четырьмя вершинами. В Обозначение для лексикографического произведения служит напоминанием о том, что данное произведение не коммутативно.
^ абРоберсон, Дэвид Э .; Манчинска, Лаура (2012). «Гомоморфизмы графов для квантовых игроков». Журнал комбинаторной теории, серия B. 118: 228–267. arXiv:1212.1724. Дои:10.1016 / j.jctb.2015.12.009.
^Bačík, R .; Махаджан, С. (1995). «Полуопределенное программирование и его приложения к задачам NP». Вычислительная техника и комбинаторика. Конспект лекций по информатике. 959. п. 566. Дои:10.1007 / BFb0030878. ISBN978-3-540-60216-3.
^Домашний продукт [2] является графическим дополнением гомоморфного произведения.[1]
Рекомендации
Имрих, Вильфрид; Клавжар, Санди (2000). Графики продуктов: структура и узнаваемость. Вайли. ISBN978-0-471-37039-0 {{противоречивые цитаты}}CS1 maint: ref = harv (связь).