Operaciones gráficas

Procedimientos para construir nuevos gráficos en teoría de grafos

En el campo matemático de la teoría de grafos , las operaciones con grafos son operaciones que generan nuevos grafos a partir de los iniciales. Incluyen operaciones unarias (una entrada) y binarias (dos entradas).

Operaciones unarias

Las operaciones unarias crean un nuevo gráfico a partir de un único gráfico inicial.

Operaciones elementales

Operaciones elementales u operaciones de edición, también conocidas comooperaciones de edición de grafos, crear un nuevo grafo a partir de uno inicial mediante un simple cambio local, como la adición o eliminación de un vértice o de una arista, la fusión y división de vértices, la contracción de las aristas , etc. La distancia de edición de grafos entre un par de grafos es el número mínimo de operaciones elementales necesarias para transformar un grafo en otro.

Operaciones avanzadas

Las operaciones avanzadas crean un nuevo gráfico a partir de uno inicial mediante un cambio complejo, como por ejemplo:

• gráfico transpuesto ;
• gráfico complementario ;
• gráfico lineal ;
• gráfico menor ;
• reescritura de gráficos ;
• potencia del gráfico ;
• gráfico dual ;
• gráfico medial ;
• gráfico de cociente ;
• Transformada Y-Δ ;
• Micielskiano .

Operaciones binarias

Las operaciones binarias crean un nuevo gráfico a partir de dos gráficos iniciales G ₁ = ( V ₁ , E ₁ ) y G ₂ = ( V ₂ , E ₂ ) , como por ejemplo:

• unión de grafos: G ₁ ∪ G ₂ . Existen dos definiciones. En la más común, la unión disjunta de grafos , se supone que la unión es disjunta. Con menos frecuencia (aunque más consistente con la definición general de unión en matemáticas), la unión de dos grafos se define como el grafo ( V ₁ ∪ V ₂ , E ₁ ∪ E ₂ ) .
• intersección de gráficos: G ₁ ∩ G ₂ = ( V ₁ ∩ V ₂ , E ₁ ∩ E ₂ ) ; ^[1]
• unión de grafos: . Grafo con todas las aristas que conectan los vértices del primer grafo con los vértices del segundo grafo. Es una operación conmutativa (para grafos no etiquetados); ^[2] ${\displaystyle G_{1}\nabla G_{2}}$
• productos gráficos basados ​​en el producto cartesiano de los conjuntos de vértices:
  • producto de grafos cartesianos : es una operación conmutativa y asociativa (para grafos no etiquetados), ^[2]
  • producto gráfico lexicográfico (o composición gráfica): es una operación asociativa (para gráficos no etiquetados) y no conmutativa, ^[2]
  • producto gráfico fuerte : es una operación conmutativa y asociativa (para gráficos no etiquetados),
  • producto de grafos tensoriales (o producto de grafos directos, producto de grafos categóricos, producto de grafos cardinales, producto de grafos de Kronecker): es una operación conmutativa y asociativa (para grafos no etiquetados),
  • producto gráfico en zigzag ; ^[3]
• Producto gráfico basado en otros productos:
  • producto de grafos con raíz : es una operación asociativa (para grafos no etiquetados pero con raíz),
  • producto gráfico corona: es una operación no conmutativa; ^[4]
• Composición de gráficos en serie y paralelo :
  • Composición de grafos paralelos: es una operación conmutativa (para grafos no etiquetados),
  • Composición gráfica de series: es una operación no conmutativa,
  • composición del gráfico fuente: es una operación conmutativa (para gráficos no etiquetados);
• Construcción de Hajós .

Notas

1. Bondy, JA; Murty, USR (2008). Teoría de grafos . Textos de posgrado en matemáticas. Springer. pág. 29. ISBN 978-1-84628-969-9.
2. Harary, F. Teoría de grafos . Reading, MA: Addison-Wesley, 1994.
3. Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Ondas de entropía, el producto gráfico en zigzag y nuevos expansores de grado constante". Anales de Matemáticas . 155 (1): 157–187. arXiv : math/0406038 . doi :10.2307/3062153. JSTOR  3062153. MR  1888797.
4. Frucht, Robert ; Harary, Frank (1970). "Sobre la corona de dos gráficas". Aecuaciones Mathematicae . 4 : 322–324. doi :10.1007/bf01844162. hdl : 2027.42/44326 .