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.

YouTube Encyclopedic

1/3
Views:
88 984
1 278
11 568 937

Transcription

Definición formal

Sean los grafos $G_{1}(V_{1},A_{1})\,$ y $G_{2}(V_{2},A_{2})\,$ , la suma de los grafos $G_{1}+G_{2}\,$ da como resultado $G'(V',A')$ donde $V'=V_{1}\cup V_{2}$ y $A'=A_{1}\cup A_{2}\cup \{\{x,y\}:x\in V_{1}\land y\in V_{2}\}\,$ .

Ejemplos

Entre los ejemplos más destacados de suma de grafos nos encontramos con los grafos ruedas W_n que se pueden definir como la suma de un grafo singleton K₁ y un ciclo C_n: W_n = K₁ + C_n. Otro ejemplo es la suma de un grafo completo K_n y un punto aislado K₁, resultando el grafo completo K_n + K₁ = K_n+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.

Véase también

Anexo:Operaciones en grafos

Datos: Q6135442

Esta página se editó por última vez el 12 oct 2019 a las 08:35.

De Wikipedia, la enciclopedia libre