Operaciones gráficas

Procedimientos para construir nuevas gráficas en teoría de grafos.

En el campo matemático de la teoría de grafos , las operaciones de gráficos son operaciones que producen nuevos gráficos 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, que también se conocen comooperaciones de edición de gráficos, cree un nuevo gráfico a partir de uno inicial mediante un simple cambio local, como la adición o eliminación de un vértice o de un borde, fusión y división de vértices, contracción de bordes , etc. La distancia de edición del gráfico entre un par de gráficos es el número mínimo de operaciones elementales necesarias para transformar un gráfico en otro.

Operaciones avanzadas

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

• transponer gráfico ;
• gráfico complementario ;
• gráfico de líneas ;
• gráfico menor ;
• reescritura de gráficos ;
• poder del gráfico ;
• gráfico dual ;
• gráfico medial ;
• gráfico de cocientes ;
• Transformada Y-Δ ;
• mycielskiano .

Operaciones binarias

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

• unión gráfica: G ₁ ∪ G ₂ . Hay dos definiciones. En el 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 gráficas se define como la gráfica ( V ₁ ∪ V ₂ , E ₁ ∪ E ₂ ) .
• intersección del gráfico: G ₁ ∩ G ₂ = ( V ₁ ∩ V ₂ , E ₁ ∩ E ₂ ) ; ^[1]
• unión de gráficos: . gráfico con todas las aristas que conectan los vértices del primer gráfico con los vértices del segundo gráfico. Es una operación conmutativa (para gráficas sin etiquetar); ^[2] ${\displaystyle G_{1}\nabla G_{2}}$
• productos gráficos basados ​​​​en el producto cartesiano de los conjuntos de vértices:
  • producto gráfico cartesiano : es una operación conmutativa y asociativa (para gráficos 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 sin etiquetar),
  • producto gráfico tensorial (o producto gráfico directo, producto gráfico categórico, producto gráfico cardinal, producto gráfico de Kronecker): es una operación conmutativa y asociativa (para gráficos no etiquetados),
  • producto gráfico en zig-zag ; ^[3]
• Producto gráfico basado en otros productos:
  • producto de gráfico enraizado : es una operación asociativa (para gráficos no etiquetados pero enraizados),
  • producto del gráfico corona: es una operación no conmutativa; ^[4]
• composición de gráficos en series-paralelas :
  • composición de grafos paralelos: es una operación conmutativa (para grafos sin etiquetar),
  • composición del gráfico en serie: es una operación no conmutativa,
  • composición del gráfico fuente: es una operación conmutativa (para gráficos sin etiquetar);
• Construcción de Hajós .

Notas

1. Bondy, JA; Murty, USR (2008). Teoría de grafos . Textos de Posgrado en Matemáticas. Saltador. pag. 29.ISBN​ 978-1-84628-969-9.
2. Harary, F. Teoría de grafos . Lectura, MA: Addison-Wesley, 1994.
3. Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Ondas de entropía, el producto del gráfico en zig-zag y nuevos expansores de grado constante". Anales de Matemáticas . 155 (1): 157–187. arXiv : matemáticas/0406038 . doi :10.2307/3062153. JSTOR  3062153. SEÑOR  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 .