Operaciones en gráficos

Las operaciones en gráficos forman nuevos gráficos a partir de los antiguos. Las operaciones se pueden dividir en las siguientes categorías principales.

Operaciones simples (unarias)

Una sola operación crea un nuevo gráfico a partir de uno antiguo.

Operaciones elementales

A veces, esta clase de operaciones se denominan operaciones de edición de gráficos. Crean un nuevo gráfico a partir del gráfico original mediante cambios locales simples, como agregar o eliminar un vértice o un arco, fusionar o dividir vértices, reducir el gráfico , etc.

Operaciones complejas

Las operaciones compuestas crean un nuevo gráfico a partir del inicial con cambios complejos, como:

• gráfico de líneas
• gráfico doble
• Complemento gráfico
• conde menor
• Grado del grafo : El k-ésimo grado G k del grafo G es un supergrafo formado por la suma de todos los arcos entre todos los pares de vértices de G con distancia como máximo k . La segunda potencia de un gráfico también se llama su cuadrado .
• Conversión Delta-Estrella
• Conde Mychelski (Mychelskiano)

Operaciones dobles (binarias)

La operación binaria crea un nuevo gráfico a partir de los dos gráficos originales G1(V1, E1) y G2(V2, E2) :

• Una unión de gráficos disjuntos, o simplemente una unión de gráficos,  es un gráfico que contiene la unión de conjuntos de vértices (disjuntos) V1 y V2 de conjuntos de gráficos y arcos, es decir, [1] . La operación es conmutativa y asociativa (para grafos no etiquetados ).
• La conexión de dos grafos es la unión de dos grafos, en la que se suman todos los arcos que conectan los vértices de ambos grafos (es decir, los arcos cuyos vértices se toman de diferentes grafos) [1] . La operación es conmutativa (para grafos no etiquetados).
• El producto de grafos basado en el producto directo de conjuntos de vértices:
  • El producto directo de grafos [1] es una operación conmutativa y asociativa (para grafos no etiquetados).
  • Producto lexicográfico de grafos [1] . La operación no es conmutativa ni asociativa.
  • Producto fuerte de gráficos .
  • Producto tensorial de gráficos , a veces también llamado producto directo o producto de Kronecker . La operación es conmutativa (para grafos no etiquetados).
  • Producto en zig-zag [2] .

Sea [N] el conjunto de números enteros de 1 a N. Para determinar el producto en zigzag se utilizan grafos k-regulares , cuyos arcos están coloreados en k colores. Para cada color i y vértice v , sea v [ i ] el vecino del vértice v conectado por un arco de color i . Sea G1 un grafo regular D1 sobre [N1] y G2 un grafo regular D2 sobre [D1]. Entonces el producto en zigzag de H es el gráfico con el conjunto de vértices [N1] × [D1], en el que para cualquier n de [N1], d de [D1] e i, j de [D2], el vértice (n , d) está conectado a ( n [ d [ i ]], d [ i ][ j ]). Esta definición se utiliza para construir expansores .

• Otras operaciones en gráficos llamados "producto":
  • Producto raíz de gráficas . La operación no es conmutativa ni asociativa.
  • El producto coronal de los gráficos G1 y G2 (definido por Frucht y Harari [3] ) es un gráfico que es la unión de una copia del gráfico G1 y |V1| copias del gráfico G2 (|V1| es el número de vértices del gráfico G1), en el que cada vértice de la copia de G1 está conectado a todos los vértices de todas las copias de G2.
• Creación de grafos secuenciales paralelos :
  • composición paralela. La operación es conmutativa (para grafos no etiquetados) [4] .
  • composición secuencial. La operación no es conmutativa [4] .
  • Composición de fuentes (fusión de fuentes). Operación conmutativa (para grafos no etiquetados).
• Conde Hajosh .

Notas

1. ↑ 1 2 3 4 F. Harari . Graph Theory = Graph Theory / Traducción del inglés y prólogo de V.P. Kozyrev. - 2. - M. : Editorial URSS, 2003. - 296 p.
2. ↑ Reingold, O.; Vadhan, S.; Wigderson, A. Ondas de entropía, el producto gráfico en zig-zag y nuevos expansores de grado constante  // Annals of Mathematics . - 2002. - T. 155 , núm. 1 . - S. 157-187 . -doi : 10.2307/ 3062153 . — .
3. ↑ Robert Frucht y Frank Harary . “Sobre las coronas de dos grafos”, Aequationes Math. 4:322-324, 1970.
4. ↑ 1 2 Evstigneev V. A., Kasyanov V. N. Serie-paralelo poset // Diccionario de gráficos en informática / Editado por el prof. Viktor Nikolaevich Kasyanov. - Novosibirsk: LLC "Siberian Scientific Publishing House", 2009. - V. 17. - (Diseño y optimización de programas). - ISBN 978-591124-036-3 .