Produto gráfico - Graph product

Em matemática , um produto gráfico é uma operação binária em gráficos . Especificamente, é uma operação que pega dois gráficos G ₁ e G ₂ e produz um gráfico H com as seguintes propriedades:

• O conjunto de vértices de H é o produto cartesiano V ( G ₁ ) ×  V ( G ₂ ), onde V ( G ₁ ) e V ( G ₂ ) são os conjuntos de vértices de G ₁ e G ₂ , respectivamente.
• Dois vértices ( a ₁ ,  a ₂ ) e ( b ₁ ,  b ₂ ) de H são conectados por uma aresta , se uma condição sobre a ₁ , b ₁ em G ₁ e a ₂ , b ₂ em G ₂ for satisfeita.

Os produtos gráficos diferem no que exatamente é essa condição. É sempre sobre se os vértices a _n , b _n em G _n são iguais ou conectados por uma aresta.

A terminologia e a notação para produtos gráficos específicos na literatura variam bastante; mesmo que o seguinte possa ser considerado padrão, os leitores são aconselhados a verificar qual definição um autor em particular usa para um produto gráfico, especialmente em textos mais antigos.

Tabela de visão geral

A tabela a seguir mostra os produtos gráficos mais comuns, denotando “está conectado por uma aresta a” e denotando não-conexão. Os símbolos do operador listados aqui não são de forma alguma padrão, especialmente em papéis mais antigos. ${\ displaystyle \ sim}$${\ displaystyle \ not \ sim}$

Nome	Condição para ${\ displaystyle (a_ {1}, a_ {2}) \ sim (b_ {1}, b_ {2})}$		Número de arestas ${\ displaystyle {\ begin {array} {cc} v_ {1} = \ vert \ mathrm {V} (G_ {1}) \ vert & v_ {2} = \ vert \ mathrm {V} (G_ {2}) \ vert \\ e_ {1} = \ vert \ mathrm {E} (G_ {1}) \ vert & e_ {2} = \ vert \ mathrm {E} (G_ {2}) \ vert \ end {array}} }$	Exemplo
		com abreviado como${\ displaystyle a_ {n} ~ {\ text {rel}} ~ b_ {n}}$ ${\ displaystyle {\ text {rel}} _ {n}}$
Produto cartesiano (produto em caixa) ${\ displaystyle G_ {1} \ square G_ {2}}$	${\ displaystyle a_ {1} = b_ {1} ~ \ land ~ a_ {2} \ sim b_ {2}}$ ${\ displaystyle \ lor}$ ${\ displaystyle a_ {1} \ sim b_ {1} ~ \ land ~ a_ {2} = b_ {2}}$	${\ displaystyle = _ {1} ~ \ sim _ {2}}$ ${\ displaystyle \ lor}$ ${\ displaystyle \ sim _ {1} ~ = _ {2}}$	${\ displaystyle v_ {1} ~ e_ {2} ~ + ~ e_ {1} ~ v_ {2}}$
Produto tensor ( produto Kronecker, produto categórico) ${\ displaystyle G_ {1} \ vezes G_ {2}}$	${\ displaystyle a_ {1} \ sim b_ {1} ~ \ land ~ a_ {2} \ sim b_ {2}}$	${\ displaystyle \ sim _ {1} ~ \ sim _ {2}}$	${\ displaystyle 2 ~ e_ {1} ~ e_ {2}}$
Produto lexicográfico ou ${\ displaystyle G_ {1} \ cdot G_ {2}}$${\ displaystyle G_ {1} [G_ {2}]}$	${\ displaystyle a_ {1} \ sim b_ {1}}$ ${\ displaystyle \ lor}$ ${\ displaystyle a_ {1} = b_ {1} ~ \ land ~ a_ {2} \ sim b_ {2}}$	${\ displaystyle \ sim _ {1}}$ ${\ displaystyle \ lor}$ ${\ displaystyle = _ {1} ~ \ sim _ {2}}$	${\ displaystyle v_ {1} ~ e_ {2} ~ + ~ e_ {1} ~ v_ {2} ^ {2}}$
Produto forte ( produto normal E produto) ${\ displaystyle G_ {1} \ boxtimes G_ {2}}$	${\ displaystyle a_ {1} = b_ {1} ~ \ land ~ a_ {2} \ sim b_ {2}}$ ${\ displaystyle \ lor}$ ${\ displaystyle a_ {1} \ sim b_ {1} ~ \ land ~ a_ {2} = b_ {2}}$ ${\ displaystyle \ lor}$ ${\ displaystyle a_ {1} \ sim b_ {1} ~ \ land ~ a_ {2} \ sim b_ {2}}$	${\ displaystyle = _ {1} ~ \ sim _ {2}}$ ${\ displaystyle \ lor}$ ${\ displaystyle \ sim _ {1} ~ = _ {2}}$ ${\ displaystyle \ lor}$ ${\ displaystyle \ sim _ {1} ~ \ sim _ {2}}$	${\ displaystyle v_ {1} ~ e_ {2} ~ + ~ e_ {1} ~ v_ {2} ~ + ~ 2 ~ e_ {1} ~ e_ {2}}$
Produto co-normal (produto disjuntivo, OU produto) ${\ displaystyle G_ {1} * G_ {2}}$	${\ displaystyle a_ {1} \ sim b_ {1}}$ ${\ displaystyle \ lor}$ ${\ displaystyle a_ {2} \ sim b_ {2}}$	${\ displaystyle \ sim _ {1}}$ ${\ displaystyle \ lor}$ ${\ displaystyle \ sim _ {2}}$	${\ displaystyle v_ {1} ^ {2} ~ e_ {2} ~ + ~ e_ {1} ~ v_ {2} ^ {2} ~ - ~ 2 ~ e_ {1} ~ e_ {2}}$
Produto modular	${\ displaystyle a_ {1} \ sim b_ {1} ~ \ land ~ a_ {2} \ sim b_ {2}}$ ${\ displaystyle \ lor}$ ${\ displaystyle a_ {1} \ not \ sim b_ {1} ~ \ land ~ a_ {2} \ not \ sim b_ {2}}$	${\ displaystyle \ sim _ {1} ~ \ sim _ {2}}$ ${\ displaystyle \ lor}$ ${\ displaystyle \ not \ sim _ {1} ~ \ not \ sim _ {2}}$
Produto enraizado	ver artigo		${\ displaystyle v_ {1} ~ e_ {2} ~ + ~ e_ {1}}$
Produto zig-zag	ver artigo		ver artigo	ver artigo
Produto de reposição
Produto homomórfico ${\ displaystyle G_ {1} \ ltimes G_ {2}}$	${\ displaystyle a_ {1} = b_ {1}}$ ${\ displaystyle \ lor}$ ${\ displaystyle a_ {1} \ sim b_ {1} ~ \ land ~ a_ {2} \ not \ sim b_ {2}}$	${\ displaystyle = _ {1}}$ ${\ displaystyle \ lor}$ ${\ displaystyle \ sim _ {1} ~ \ not \ sim _ {2}}$
Produto de vizinhança comum	${\ displaystyle a_ {1} \ sim b_ {1} ~ \ land ~ a_ {2} \ sim b_ {2}}$ ${\ displaystyle \ lor}$${\ displaystyle b_ {1} \ sim a_ {1} ~ \ land ~ b_ {2} \ sim a_ {2}}$		ver artigo	ver artigo

Em geral, um produto gráfico é determinado por qualquer condição para que possa ser expressa em termos de e . ${\ displaystyle (a_ {1}, a_ {2}) \ sim (b_ {1}, b_ {2})}$${\ displaystyle a_ {n} = b_ {n}}$${\ displaystyle a_ {n} \ sim b_ {n}}$

Mnemônico

Let Ser o gráfico completo em dois vértices (ou seja, uma única aresta). O produto gráficos , e exatamente como o gráfico que representa o operador. Por exemplo, é um quatro ciclo (um quadrado) e é o gráfico completo em quatro vértices. A notação para produto lexicográfico serve como um lembrete de que este produto não é comutativo. ${\ displaystyle K_ {2}}$${\ displaystyle K_ {2} \ square K_ {2}}$${\ displaystyle K_ {2} \ vezes 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}]}$

Veja também

• Operações de gráfico

Notas

Referências