Las operaciones de gráficos producen nuevos gráficos a partir de los iniciales. Pueden dividirse en las siguientes categorías principales.
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 como operaciones de edición de gráficos, crear 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 del borde , etc. La distancia de edición del gráfico entre un par de gráficas es el número mínimo de operaciones elementales necesarias para transformar una gráfica en otra.
Operaciones avanzadas
Las operaciones avanzadas crean un nuevo gráfico a partir del inicial mediante cambios complejos, como:
Operaciones binarias
Las operaciones binarias crean un nuevo gráfico a partir de dos gráficos iniciales G 1 = ( V 1 , E 1 ) y G 2 = ( V 2 , E 2 ) , como por ejemplo:
- unión gráfica: G 1 ∪ G 2 . Hay dos definiciones. En el más común, la unión disjunta de gráficos , se supone que la unión es disjunta. Con menos frecuencia (aunque más coherente con la definición general de unión en matemáticas), la unión de dos gráficos se define como el gráfico ( V 1 ∪ V 2 , E 1 ∪ E 2 ) .
- intersección del gráfico: G 1 ∩ G 2 = ( V 1 ∩ V 2 , E 1 ∩ E 2 ) ; [1]
- unión de gráfico: 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áficos sin etiquetar); [2]
- graficar productos basados en el producto cartesiano de los conjuntos de vértices:
- producto de grafo cartesiano : es una operación conmutativa y asociativa (para grafos sin etiquetar), [2]
- Producto de gráfico lexicográfico (o composición de gráfico): es una operación asociativa (para gráficos sin etiquetar) y no conmutativa, [2]
- producto de gráfico fuerte : es una operación conmutativa y asociativa (para gráficos sin etiquetar),
- producto de gráfico tensorial (o producto de gráfico directo, producto de gráfico categórico, producto de gráfico cardinal, producto de 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 con raíz : es una operación asociativa (para gráficos sin etiquetar pero con raíz),
- producto corona gráfico : es una operación no conmutativa; [4]
- Composición de gráficos en serie-paralelo :
- Composición de grafos paralelos: es una operación conmutativa (para grafos sin etiquetar),
- 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
- ^ Bondy, JA; Murty, USR (2008). Teoría de grafos . Textos de Posgrado en Matemáticas. Saltador. pag. 29. ISBN 978-1-84628-969-9.
- ^ Un b c Harary, F . Teoría de grafos . Reading, MA: Addison-Wesley, 1994.
- ^ Reingold, O .; Vadhan, S .; Wigderson, A. (2002). "Ondas de entropía, el producto gráfico en zig-zag y nuevos expansores de grado constante". Annals of Mathematics . 155 (1): 157–187. arXiv : matemáticas / 0406038 . doi : 10.2307 / 3062153 . JSTOR 3062153 . Señor 1888797 .
- ^ Frucht, Robert ; Harary, Frank (1970). "Sobre la corona de dos gráficos". Aequationes Mathematicae . 4 : 322–324. doi : 10.1007 / bf01844162 . hdl : 2027,42 / 44326 .