Suma de grafos
En el campo matemático de la teoría de grafos, la suma de grafos o combinación de grafos es una operación binaria entre grafos que consiste en unir los conjuntos de vértices y los conjuntos de aristas de ambos grafos, más el conjunto de aristas que conectan los vértices del primer grafo con los del segundo grafo. Es una operación conmutativa para grafos no-etiquetados.
![](../I/Wheel_graphs.svg.png.webp)
![](../I/Complete_graph_K5.svg.png.webp)
Definición formal
|
Ejemplos
Entre los ejemplos más destacados de suma de grafos nos encontramos con los grafos ruedas Wn que se pueden definir como la suma de un grafo singleton K1 y un ciclo Cn: Wn = K1 + Cn. Otro ejemplo es la suma de un grafo completo Kn y un punto aislado K1, resultando el grafo completo Kn + K1 = Kn+1
Resolución por conjuntos (Unión)
Teniendo creados los grafos como una matriz de n columnas, en donde cada una de estas representa un vértice y los n renglones de cada columna representan las aristas (dirección de memoria del vértice al cual apunta); siendo esta matriz no necesariamente cuadrada. Y teniendo todos los grafos a sumar en una lista:
1.-Recorrer la lista de grafos buscando el grafo con el mayor número de vértices y si hubiera más de un grafo con ese mismo número de vértices mayor elegir por orden de entrada (puede al mismo tiempo de la búsqueda del mayor número de vértices crear una lista de grafos en donde inserte estos en orden).
2.-Una vez ubicado en el grafo de mayor número de vértices, crear un nuevo grafo el cual llamaremos GrafoSuma y será una copia idéntica del primer grafo seleccionado (creándolo también como una matriz).
3.-Desplazarse al siguiente grafo de mayor número de vértices y ubicarse en el primer vértice V(la primera columna de la matriz); simultáneamente se toma el GrafoSuma y se hace una búsqueda de V en sus vértices y si no se encuentra ese vértice en GrafoSuma, se agrega toda la columna (el vértice con sus aristas) a GrafoSuma. Pero en el caso de que "V" se encuentre en el GrafoSuma solo se agregan las aristas de V que no estén en ese vértice de GrafoSuma.
4.-Una vez recorridos todos los vértices del grafo que se va a sumar a GrafoSuma se selecciona el siguiente grafo (por orden de número de vértices) y se repite el paso 3 hasta que se sumen todos los grafos de la lista.