Русская Википедия:Произведение графов
Произведение графов — это бинарная операция на графах. Конкретнее, это операция, которая двум графам G1 и G2 сопоставляет граф H со следующими свойствами:
- Множество вершин графа H — это прямое произведение V(G1) × V(G2), где V(G1) и V(G2) являются множествами вершин G1 и G2 соответственно.
- Две вершины (u1, u2) и (v1, v2) графа H соединены ребром тогда и только тогда, когда вершины u1, u2, v1, v2 удовлетворяют определённым условиям, соответствующим типу произведения (смотрите ниже).
Виды произведений
Следующая таблица показывает наиболее употребительные произведения графов. В таблице <math>\sim</math> означает «соединены ребром» и <math>\not\sim</math> означает «не соединены ребром». Символы операций, приведённые ниже, не всегда означают стандарт, особенно в ранних работах.
| Название | Условие для (<math>u_1</math>, <math>u_2</math>) ∼ (<math>v_1</math>, <math>v_2</math>). | Размеры | Пример |
|---|---|---|---|
| Декартово произведение <math>G \square H</math> |
( <math>u_1</math> = <math>v_1</math> и <math>u_2</math> <math>\sim</math> <math>v_2</math> ) или ( <math>u_1</math> <math>\sim</math> <math>v_1</math> и <math>u_2</math> = <math>v_2</math> ) |
<math>G_{V_1, E_1} \square H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (E_2 V_1 + E_1 V_2)}</math> | Файл:Graph-Cartesian-product.svg |
| Тензорное произведение (Категорийное произведение) <math>G \times H</math> |
<math>u_1</math> <math>\sim</math> <math>v_1</math> и <math>u_2</math> <math>\sim</math> <math>v_2</math> | <math>G_{V_1, E_1} \times H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (2 E_1 E_2)}</math> | Файл:Graph-tensor-product.svg |
| Лексикографическое произведение <math>G \cdot H</math> или <math>G[H]</math> |
u1 ∼ v1 или ( u1 = v1 и u2 ∼ v2 ) |
<math>G_{V_1, E_1} \cdot H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (E_2 V_1 + E_1 V_2^2)}</math> | Файл:Graph-lexicographic-product.svg |
| Сильное произведение (Нормальное произведение) <math>G \boxtimes H</math> |
( u1 = v1 и u2 ∼ v2 ) или ( u1 ∼ v1 и u2 = v2 ) или ( u1 ∼ v1 и u2 ∼ v2 ) |
<math>G_{V_1, E_1} \boxtimes H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (V_1 E_2 + V_2E_1 + 2 E_1 E_2)}</math> | |
| Конормальное произведение графов (Дизъюнктное произведение) <math>G * H</math> |
u1 ∼ v1 или u2 ∼ v2 |
||
| Шаблон:Не переведено 5 | <math>(u_1 \sim v_1</math> и <math>u_2 \sim v_2)</math> или <math>(u_1 \not\sim v_1</math> и <math>u_2 \not\sim v_2)</math> |
||
| Корневое произведение | см. статью | <math>G_{V_1, E_1} \cdot H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (E_2 V_1 + E_1)}</math> | Файл:Graph-rooted-product.svg |
| Произведение Кронекера | см. статью | см. статью | см. статью |
| Зигзаг-произведение | см. статью | см. статью | см. статью |
| Шаблон:Не переведено 5 | |||
| Гомоморфное произведение[1][2][1] <math>G \ltimes H</math> |
<math>(u_1 = v_1)</math> или <math>(u_1 \sim v_1</math> и <math>u_2 \not\sim v_2)</math> |
В общем случае произведение графов определяется любым условием для (u1, u2) ∼ (v1, v2), которое может быть выражено в терминах утверждений u1 ∼ v1, u2 ∼ v2, u1 = v1 и u2 = v2.
Мнемоника
Пусть <math>K_2</math> — полный граф с двумя вершинами (т.е. единственное ребро). Произведения графов <math>K_2 \square K_2</math>, <math>K_2 \times K_2</math>, и <math>K_2 \boxtimes K_2</math> выглядят в точности как знак операции умножения. Например, <math>K_2 \square K_2</math> является циклом длины 4 (квадрат), а <math>K_2 \boxtimes K_2</math> является полным графом с четырьмя вершинами. Нотация <math>G[H]</math> для лексикографического произведения напоминает, что произведение не коммутативно.
См. также
Примечания
Литература
