Introducción:
un gráfico G consta de vértices y aristas. Los bordes son líneas o arcos que conectan dos Nodes en el gráfico, y los Nodes también se conocen como vértices.
Un gráfico simple G = (V, E) consta de:
- V : Conjunto finito de vértices
- E : Conjunto de aristas
Ejemplo:
en el siguiente diagrama, el gráfico G consta de:
V = { A, B, C, D}
E = { {A, C}, {C, B}, {A, D}}
Suma de 2 grafos:
Si tenemos 2 grafos, G 1 y G 2 tales que la intersección de sus vértices es nula ( V(G 1 )∩ V(G 2 ) = ∅ ), entonces la suma :
G 1 + G 2 está definida como el gráfico cuyo conjunto de vértices V(G 1 +G 2 ) es V(G 1 ) + V(G 2 ) y el conjunto de aristas consta de estas aristas, que están en G 1 y en G 2 y las aristas contenidas al unir cada una vértice de G 1 a cada vértice de G 2 .
Ejemplo: La suma de 2 gráficos mostrados G 1 y G 2son :
Aquí: V(G 1 )∩ V(G 2 ) = ∅
Las aristas ya contenidas en G 1 son, E(G 1 ) : {{A, B}} y los vértices son : V(G 1 ) = {A, B}
Las aristas ya contenidas en G 2 son, E(G 2 ) : {{A’, B’} ,{B’,C’} }y los vértices son : V(G 2 ) = {A’, B’, C’}
Entonces la gráfica , G 1 + G 2 tendrá
(i) vértices como : V(G 1 +G 2 ) = V(G1) + V(G 2 ) = { A, B. A’, B’, C’}
(ii) y E(G 1 + G 2 ) = E(G 1 ) + E(G 2 ) + aristas contenidas al unir cada vértice de G 1a cada vértice de G 2 =
{ {A, B}, {A’, B’} ,{B’,C’} , {A,A’} , {A, B’}, {A, C’} , {B, A’} , {B, B’}, {B, C’}}
Producto de 2 Grafos:
Definimos el producto de 2 grafos, G1*G2, como (G 1 *G 2 )(V, E) tal que :
(i) Vértices : V(G 1 *G 2 ) = Producto cartesiano de V(G 1 ) & V(G 2 ) = V(G 1 ) * V(G 2 ) y
(ii) Aristas: Considerando 2 vértices cualesquiera en el conjunto de vértices del gráfico G 1 *G 2 (es decir, el producto cartesiano de V(G 1 ) & V(G 2 ) ) , digamos A & V (Nota : A & V son vértices que son un par de 2 elementos) tal que : A = (a1, a2) & V = ( v1,v2) , entonces {A, V} es una arista en el gráfico G 1 *G 2si se cumple uno de los siguientes:
(i) a1 = v1 (el primer elemento del par es el mismo) y a2 es adyacente a v2
(ii) a2 = v2 (el segundo elemento del par es el mismo) y a1 es adyacente a v1
Ejemplo: Considere 2 gráficos, G 1 y G 2 tales que:
V(G 1 ) = {A, B}
E(G 1 ) = { {A, B} }
V(G 2 ) = {A’, B’ , C’}
E(G 2 ) ={ {A’, B’} ,{B’,C’} }
Entonces el Gráfico G 1 *G 2 tendrá:
(i) Vértices: V(G 1 *G 2 ) = producto cartesiano de V(G 1 ) & V(G 2 ) = V(G 1 ) * V(G 2 ) = { (A, A’) , (A, B’), (A, C’), (B, A’) , (B, B’), (B, C’) }
(ii) Aristas : Nosotros necesita verificar que cada par de vértices en G 1 * G 2 pueda formar un borde / no. Como sabemos, si tenemos 2 vértices A y V en (G 1 * G 2 ) tales que: A = (a1, a2) & V = (v1,v2), entonces {A, V} es una arista en gráfico G 1 *G 2 si se cumple uno de los siguientes:
(i) a1 = v1 (el primer elemento del par es el mismo) Y a2 es adyacente a v2
(ii) a2 = v2 (el segundo elemento del par es el mismo) Y a1 es adyacente a v1
Gráfico Producto G 1 * G 2
Encontramos que:
1. { (A, A’) , (A, B’) } es una arista porque el primer elemento del par es el mismo (A = A) y A’ es adyacente a B’ en G 2
2 { (A, C’) , (A, B’) } es una arista porque el primer elemento del par es el mismo (A = A) y C’ es adyacente a B’ en G 2
3. { (B, A’) , (B, B’) } es una arista porque el primer elemento del par es el mismo (B = B) y A’ es adyacente a B’ en G 2
4. { (B, C’) , ( B, B’) } es una arista porque el primer elemento del par es el mismo (A = A) y C’ es adyacente a B’ en G 2
5. { (A, A’) , (B, A’) } es una arista porque el segundo elemento del par es el mismo (A’ = A’) y A es adyacente a B en G 1
6. { (A, B’) , (B, B’) } es una arista porque el segundo elemento del par es el mismo (B’ = B’) y A es adyacente a B en G 1
7. { (A , C’) , (B, C’) } es una arista porque el segundo elemento del par es el mismo (C’ = C’) y A es adyacente a B en G 1
Entonces E(G 1 *G 2 ) = { { (A, A’) , (A, B’) } , { (A, C’) , (A, B’) } , { (B, A’) , (B, B’) } , { (B, C’) , (B, B’) } , { (A, A’) , (B, A’) } , { (A, B’) , ( B, B’) } , { (A, C’) , (B, C’) } }
De esta manera podemos encontrar la suma y el producto de 2 gráficos cualesquiera.
Rango y nulidad de un gráfico:
Sea G(V,E) un gráfico con n vértices y m aristas y K componentes.
es decir; |G(V)| = n & |G(E)| = m definimos el rango P(G) y la nulidad μ(G) de la siguiente manera:
If G Is not connected : P(G) = Rank of G = n - k μ(G) = Nullity of G = m - n + k If G Is connected : P(G) = Rank of G = n - 1 μ(G) = Nullity of G = m - n + 1
Ejemplo 1: el gráfico que se muestra a continuación está conectado:
Gráfica G
|G(V)| = n = 4 &
|G(E)| = m = 3
P(G) = Rango de G = n – 1 = 4 -1 = 3
μ(G) = Nulidad de G = m – n + 1 = 3 – 4 + 1 = 0
Ejemplo 2: el gráfico que se muestra a continuación no está conectado:
|G(V)| = n = 6 &
|G(E)| = m = 4 &
No de componentes = k = 2
P(G) = Rango de G = n – k = 6 – 2 = 4
μ(G) = Nulidad de G = m – n + k = 4 – 6 + 2 = 0
Publicación traducida automáticamente
Artículo escrito por sameekshakhandelwal1712 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA