Hispanopedia WikiEn el campo matemático de la teoría de grafos , las operaciones con grafos son aquellas que generan nuevos grafos a partir de grafos iniciales. Incluyen tanto operaciones unarias (de una entrada) como binarias (de dos entradas).
operaciones unarias
Las operaciones unarias crean un nuevo grafo a partir de un único grafo inicial.
Operaciones elementales
Operaciones elementales u operaciones de edición, que también se conocen comoLas operaciones de edición de grafos crean 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 una arista, la fusión o división de vértices, la contracción de aristas , etc. La distancia de edición entre un par de grafos es el número mínimo de operaciones elementales necesarias para transformar un grafo en el otro.
Operaciones avanzadas
Las operaciones avanzadas crean un nuevo gráfico a partir de uno inicial mediante un cambio complejo, como por ejemplo:
Operaciones binarias
Las operaciones binarias crean un nuevo grafo a partir de dos grafos iniciales G 1 = ( V 1 , E 1 ) y G 2 = ( V 2 , E 2 ) , tales como:
- Unión de grafos: G 1 ∪ G 2 . Hay dos definiciones. En la más común, la unión disjunta de grafos , se supone que la unión es disjunta. Menos común (aunque más coherente con la definición general de unión en matemáticas) la unión de dos grafos se define como el grafo ( V 1 ∪ V 2 , E 1 ∪ E 2 ) .
- intersección de grafos: G 1 ∩ G 2 = ( V 1 ∩ V 2 , E 1 ∩ E 2 ) ; [ 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 sin etiquetas); [ 2 ]
- Productos de grafos basados en el producto cartesiano de los conjuntos de vértices:
- producto cartesiano de grafos : es una operación conmutativa y asociativa (para grafos no etiquetados), [ 2 ]
- producto de grafos lexicográficos (o composición de grafos): es una operación asociativa (para grafos no etiquetados) y no conmutativa, [ 2 ]
- producto gráfico fuerte : es una operación conmutativa y asociativa (para gráficos sin etiquetas),
- 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 de reemplazo ,
- producto gráfico en zigzag ; [ 3 ]
- Producto gráfico basado en otros productos:
- producto de grafos enraizados : es una operación asociativa (para grafos no etiquetados pero enraizados),
- producto gráfico corona : es una operación no conmutativa; [ 4 ]
- Composición de grafos serie-paralelo :
- Composición paralela de grafos: es una operación conmutativa (para grafos sin etiquetar),
- Composición de grafos en serie: es una operación no conmutativa,
- Composición de grafos fuente: es una operación conmutativa (para grafos sin etiquetar);
- Construcción Hajós .
Notas
- ↑ 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.
- 1 2 3 Harary, F. Teoría de grafos . Reading, MA: Addison-Wesley, 1994.
- ↑ Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Ondas de entropía, el producto de grafos en zigzag y nuevos expansores de grado constante". Annals of Mathematics . 155 (1): 157– 187. arXiv : math/0406038 . doi : 10.2307/3062153 . JSTOR 3062153 . MR 1888797 .
- ↑ 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 .
- operaciones gráficas
