Графический продукт

Бинарная операция над графами

В теории графов графовое произведение — это бинарная операция над графами . В частности, это операция, которая берет два графа G ₁ и G ₂ и производит граф H со следующими свойствами:

• Множество вершин H представляет собой декартово произведение V ( G ₁ ) × V ( G ₂ ) , где V ( G ₁ ) и V ( G ₂ ) являются множествами вершин G ₁ и G ₂ соответственно .
• Две вершины ( a ₁ , a ₂ ) и ( b ₁ , b ₂ ) графа H соединены ребром , если и только если выполняется условие относительно a ₁ , b ₁ в G ₁ и a ₂ , b ₂ в G _{2 .}

Графовые продукты различаются тем, что именно представляет собой это условие. Речь всегда идет о том, равны ли вершины a _n , b _n в G _n или соединены ребром.

Терминология и обозначения для конкретных графических продуктов в литературе существенно различаются; даже если приведенное ниже можно считать в некоторой степени стандартным, читателям рекомендуется проверить, какое определение графического продукта использует конкретный автор, особенно в старых текстах.

Даже для более стандартных определений в литературе не всегда единообразно, как обрабатывать самопетли . Формулы ниже для числа ребер в произведении также могут не работать при включении самопетлей. Например, тензорное произведение самопетли одной вершины с собой является другой самопетлей одной вершины с , а не так, как следует из формулы . ${\displaystyle E=1}$ ${\displaystyle E=2}$ ${\displaystyle E_{G\times H}=2E_{G}E_{H}}$

Обзорная таблица

В следующей таблице показаны наиболее распространенные графовые продукты, с обозначением «соединен ребром с», и обозначением несмежности. Хотя допускает равенство, означает, что они должны быть различны и несмежны. Перечисленные здесь символы операторов ни в коем случае не являются стандартными, особенно в старых работах. ${\displaystyle \sim }$ ${\displaystyle \not \sim }$ ${\displaystyle \not \sim }$ ${\displaystyle \not \simeq }$

В общем случае графическое произведение определяется любым условием для , которое можно выразить через и . ${\displaystyle (a_{1},a_{2})\sim (b_{1},b_{2})}$ ${\displaystyle a_{n}=b_{n}}$ ${\displaystyle a_{n}\sim b_{n}}$

Мнемонический

Пусть будет полным графом на двух вершинах (т.е. одним ребром). Графы произведений , , и выглядят точно так же, как граф, представляющий оператор. Например, является четырехциклом (квадрат), а является полным графом на четырех вершинах. ${\displaystyle K_{2}}$ ${\displaystyle K_{2}\square K_{2}}$ ${\displaystyle K_{2}\times K_{2}}$ ${\displaystyle K_{2}\boxtimes K_{2}}$ ${\displaystyle K_{2}\square K_{2}}$ ${\displaystyle K_{2}\boxtimes K_{2}}$

Обозначение для лексикографического произведения служит напоминанием о том, что это произведение не является коммутативным. Полученный граф выглядит как подстановка копии для каждой вершины . ${\displaystyle G_{1}[G_{2}]}$ ${\displaystyle G_{2}}$ ${\displaystyle G_{1}}$

Смотрите также

• Графические операции

Примечания

1. Roberson, David E.; Mancinska, Laura (2012). «Гомоморфизмы графов для квантовых игроков». Журнал комбинаторной теории, серия B. 118 : 228–267. arXiv : 1212.1724 . doi : 10.1016/j.jctb.2015.12.009.
2. Bačík, R.; Mahajan, S. (1995). "Полуопределенное программирование и его приложения к задачам NP". Computing and Combinatorics . Lecture Notes in Computer Science. Vol. 959. p. 566. doi :10.1007/BFb0030878. ISBN 978-3-540-60216-3.
3. Гомоморфное произведение ^[2] является графовым дополнением гомоморфного произведения ^{[1] .}

Ссылки

• Имрих, Вильфрид; Клавжар, Санди (2000). Графы продуктов: структура и распознавание . Wiley. ISBN 978-0-471-37039-0.