WikiSort.ru - Не сортированное

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

• Множество вершин графа H — это прямое произведение V(G₁) × V(G₂), где V(G₁) и V(G₂) являются множествами вершин G₁ и G₂ соответственно.
• Две вершины (u₁, u₂) и (v₁, v₂) графа H соединены ребром тогда и только тогда, когда вершины u₁, u₂, v₁, v₂ удовлетворяют определённым условиям, соответствующим типу произведения (смотрите ниже).

Виды произведений

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

Название	Условие для (${\displaystyle u_{1}}$ , ${\displaystyle u_{2}}$ ) ∼ (${\displaystyle v_{1}}$ , ${\displaystyle v_{2}}$ ).	Размеры	Пример
Декартово произведение[en] ${\displaystyle G\square H}$	( ${\displaystyle u_{1}}$  = ${\displaystyle v_{1}}$  и ${\displaystyle u_{2}}$  ${\displaystyle \sim }$  ${\displaystyle v_{2}}$  ) или ( ${\displaystyle u_{1}}$  ${\displaystyle \sim }$  ${\displaystyle v_{1}}$  и ${\displaystyle u_{2}}$  = ${\displaystyle v_{2}}$  )	${\displaystyle 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})}}$
Тензорное произведение?! (Категорийное произведение) ${\displaystyle G\times H}$	${\displaystyle u_{1}}$  ${\displaystyle \sim }$  ${\displaystyle v_{1}}$  и ${\displaystyle u_{2}}$  ${\displaystyle \sim }$  ${\displaystyle v_{2}}$	${\displaystyle G_{V_{1},E_{1}}\times H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(2E_{1}E_{2})}}$
Лексикографическое произведение[en] ${\displaystyle G\cdot H}$ или ${\displaystyle G[H]}$	u1 ∼ v1 или ( u1 = v1 и u2 ∼ v2 )	${\displaystyle 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})}}$
Сильное произведение (Нормальное произведение) ${\displaystyle G\boxtimes H}$	( u1 = v1 и u2 ∼ v2 ) или ( u1 ∼ v1 и u2 = v2 ) или ( u1 ∼ v1 и u2 ∼ v2 )	${\displaystyle G_{V_{1},E_{1}}\boxtimes H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(V_{1}E_{2}+V_{2}E_{1}+2E_{1}E_{2})}}$
Конормальное произведение графов (Дизъюнктное произведение) ${\displaystyle G*H}$	u1 ∼ v1 или u2 ∼ v2
Модулярное произведение[en]	${\displaystyle (u_{1}\sim v_{1}}$ и ${\displaystyle u_{2}\sim v_{2})}$ или ${\displaystyle (u_{1}\not \sim v_{1}}$ и ${\displaystyle u_{2}\not \sim v_{2})}$
Корневое произведение[en]	см. статью	${\displaystyle G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_{1}+E_{1})}}$
Произведение Кронекера	см. статью	см. статью	см. статью
Зигзаг-произведение	см. статью	см. статью	см. статью
Заменяющее произведение[en]
Гомоморфное произведение[1][2][1] ${\displaystyle G\ltimes H}$	${\displaystyle (u_{1}=v_{1})}$ или ${\displaystyle (u_{1}\sim v_{1}}$ и ${\displaystyle u_{2}\not \sim v_{2})}$

В общем случае произведение графов определяется любым условием для (u₁, u₂) ∼ (v₁, v₂), которое может быть выражено в терминах утверждений u₁ ∼ v₁, u₂ ∼ v₂, u₁ = v₁ и u₂ = v₂.

Мнемоника

Пусть ${\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}}$ является циклом длины 4 (квадрат), а ${\displaystyle K_{2}\boxtimes K_{2}}$ является полным графом с четырьмя вершинами. Нотация ${\displaystyle G[H]}$ для лексикографического произведения напоминает, что произведение не коммутативно.

См. также

• Операции над графами

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.