Jump to content

Граф продукта

В теории графов произведение графов — это бинарная операция над графами . В частности, это операция, которая берет два графа 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 обозначение лексикографического произведения служит напоминанием о том, что это произведение не коммутативно. Полученный график выглядит как замена копии для каждой вершины .

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Jump up to: а б Роберсон, Дэвид Э.; Манчинска, Лаура (2012). «Гомоморфизмы графов для квантовых игроков». Журнал комбинаторной теории, серия B. 118 : 228–267. arXiv : 1212.1724 . дои : 10.1016/j.jctb.2015.12.009 .
  2. ^ Бачик Р.; Махаджан, С. (1995). «Полуопределенное программирование и его приложения к задачам NP». Вычисления и комбинаторика . Конспекты лекций по информатике. Том. 959. с. 566. дои : 10.1007/BFb0030878 . ISBN  978-3-540-60216-3 .
  3. ^ Домашний продукт [2] является графическим дополнением гомоморфного произведения. [1]
  • Имрих, Вильфрид; Клавжар, Санди (2000). Графики продуктов: структура и узнаваемость . Уайли. ISBN  978-0-471-37039-0 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 09cb4ce02fc7d4397e4063b25d116a6c__1693221600
URL1:https://arc.ask3.ru/arc/aa/09/6c/09cb4ce02fc7d4397e4063b25d116a6c.html
Заголовок, (Title) документа по адресу, URL1:
Graph product - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)