Download - Operaciones Entre Grafos
OPERACIONES ENTRE GRAFOS
Puesto que los grafos son definidos en términos de los conjuntos de vértices y aristas, es
natural que las operaciones definidas en la teoría de conjuntos puedan ser aplicadas a la
teoría de grafos.
Sean G1 = (V1,A1, fG1) y G2 = (V2,A2, fG2) dos subgrafos de un grafo G = (V,A, fG)
v1
v2 v3
v4v5
a b
c
d
e
v3
v4 v5
a h
c
d
e
g
v1
v2
v6
f
G1 G2
UNION
La unión de los subgrafos G, G1 y G2, es otro subgrafo G3 = (V3,A3, fG3) de G tal que
V3 =V1 UV2, A3 = A1 U A2 y FG3 asigna a toda arista de A3 un par de vértices deV3.
EJEMPLO
v1
v2v3
v4v5
a b
c
d
e
v3
v4
a h
c
d
e
g
v1
v2
v6
f
G1 G2
v5
v3
v4
ah
c
d
e
g
v1
v2
v6
f
v5
G1 U G2
b
O
P
E
R
A
C
I
O
N
E
S
E
N
T
R
E
G
R
A
F
O
S
INTERSECCION
SeanV1 ∩ V2 ≠ 0 la intersección de los subgrafos G1 y G2, G1 ∩ G2, es otro subgrafo
G4 = (V4,A4, fG4) de G, tal queV4 =V1 ∩ V2, A4 = A1 ∩ A2 y FG4 asigna a toda arista
de A4 un par de vértices deV4.
EJEMPLO
v1
v2v3
v4v5
a b
c
d
e
v3
v4
a h
c
d
e
g
v1
v2
v6
f
v5
G1 G2
v1
v2v3
v4v5
a
c
d
e
G1 ∩ G2
O
P
E
R
A
C
I
O
N
E
S
E
N
T
R
E
G
R
A
F
O
S
SUMA ANILLO
La suma anillo de los subgrafos G1 y G2, G1 o G2, es otro subgrafo G5 = (V5, A5, FG5) de
G, tal que V5 = V1 U V2, A5 = (A1 U A2) – (A1 ΩU A2) (1) y FG5 asigna a toda arista A5
un par de vértices de V5.
(1) Sean M y N dos conjuntos . La diferencia simétrica de M y N, escrita (M U N) – (M ∩ N), es el
conjunto de todos los elementos que pertenecen a M U N, pero que no pertenecen a M ∩ N.
v1
v2v3
v4v5
a b
c
d
e
v3
v4
a h
c
d
e
g
v2
v6
f
v5
v4
b
g
v2
v6
f
h
v5
v1
v3
G1 G2
v1
O
P
E
R
A
C
I
O
N
E
S
E
N
T
R
E
G
R
A
F
O
S
Las tres operaciones mencionadas son conmutativas, es decir:
G1 U G2 = G2 U G1, G1 ∩ G2 = G2 ∩ G1 y G1 G2 = G2 G1
Si G1 y G2 son arista-disjuntos entonces G1 ∩ G2 es igual al grafo vacio y G1 G2 =
G1 U G2. Si G1 y G2 son vértice-disjuntos, entonces G1 ∩ G2 no esta definido
arista-disjuntos vértice-disjuntos
Para todo grafo G se tiene que:
G U G = G ∩ G = G
G G es igual a grafo vacio
Si G1 es un grafo de G, entonces G G1 = G – A(G1 )
Fusión de vértices
Un par de vértices a y b de un grafo G se dice que ha sido Fusionados, si los vértices son
remplazados por un nuevo vértice, tal que toda arista incidente en a o en b, o en ambos es
Incidente en el nuevo vértice.
v1
v2
b
v1
v2
hG1 G2
v1
v2
b
v3
v4
bG1 G2
O
P
E
R
A
C
I
O
N
E
S
E
N
T
R
E
G
R
A
F
O
S
EJEMPLO FUSION DE VERTICES
La figura muestra la fusión de los vértices a y b. la arista 2 se convierte en un aro y la arista
4 en una arista paralela a la arista 5. la fusión de los vértices no altera el numero de
aristas, pero si reduce el numero de vértices en una unidad.
a
b
c
d
e
f
g
1 2
3
45
6
7
8
9
(a,b)
c
d
e
f
g
1
2
3
4
5
6
7
8
9
Grafo G sin fusión Grafo G con fusión
O
P
E
R
A
C
I
O
N
E
S
E
N
T
R
E
G
R
A
F
O
S
ADICION DE UNA ARISTA
Sea G = ( V, A, f ) un grafo y u y v dos vértices de G. El grafo G+a, donde f(a) = uv denota
el grafo cuyo conjunto de vértices es V(G) y cuyo conjunto de aristas es A(G) U {a} esta
operación se llama adición de una arista a.
Claramente G es subgrafo de G+a
b
d
c
e
v2
v1v3
v4
b
d
c
e
v2
v1v3
v4
a
G G+a
Si en el grafo G los vértices u y v son adyacentes, entonces la arista a en G+a es paralela a la arista
cuyos extremos son u y v en G.
O
P
E
R
A
C
I
O
N
E
S
E
N
T
R
E
G
R
A
F
O
S
CONEXIÓN EN GRAFOS
Una RUTA en un grafo G es una sucesión finita no nula.
R = v0a1v1a2v2 … ak-1vk-1akvk
Cuyos términos son alternadamente vértices y aristas, tal que toda arista
de R tiene Como sus extremos el vértice precedente y el siguiente de la
sucesión.
En estas condiciones diremos que R es una ruta de v0 a vk , lo que
denotamos por R - ( v0,vk ).
v0 se llama vértice inicial y vk se llama vértice terminal de R.
Los vértices v1 hasta vk -1 se llaman vértices intermedios . El numero
entero k se llama la longitud de R y la denotamos por l( R ) = k
EJEMPLO
v1
v2
v3
v4
v5
v6
v7
v8
v9
R1=v3a6v5a8v6a9v7a10v5a6v3a3v2a1v1
R1-(v3,v1) y l (R1) = 7
R2=v1a1v2a4v5a6v3a5v4a7v5a8v6
R2-(v1,v6) y l (R2) = 6
R3=v8a11v7a10v5a6v3a3v2a1v1
R3-(v8,v1) y l (R3) = 5
a1
a2
a3a4
a5
a6
a7
a8a9
a10
a11
a12
C
O
N
E
X
I
Ó
N
E
N
G
R
A
F
O
S
Una ruta R – ( V0 -Vk) de un grafo G en el cual todas sus aristas son diferentes, se llama
una CADENA C – ( V0 -Vk) de grafo G. Por ejemplo, en el grafo de la figura anterior, la
ruta R2 es una cadena.
Si además todos los vértices de una cadena son diferentes, esta se llama CADENA
SIMPLE (CS) . Por ejemplo, en el grafo de la figura anterior, la ruta R3 es una cadena
simple.
Una ruta R – ( V0 -Vk) se llama RUTA CERRADA (RC) si y solo si V0 =Vk, es decir, si su
vértice inicial y su vértice terminal coinciden
Si la ruta cerrada es una cadena se llama CICLO (CI).
Si la ruta cerrada es una cadena simple se llama CICLO SIMPLE (CIS).
Las representaciones graficas de los conceptos ruta, cadena, cadena simple, ruta cerrada, ciclo y
ciclo simple son subgrafos del grafo dado.
En un grafo simple, una cadena, una cadena simple un ciclo o un ciclo simple quedan
unívocamente determinados mediante la sucesión de vértices.
C
O
N
E
X
I
Ó
N
E
N
G
R
A
F
O
S
EJEMPLO
v1
v2
v3
v4
v5
v6
v7
RC=v1a1v2a3v3a7v5a6v2a3v3a4v4a2v1 es una ruta cerrada de G
a2
a1a3
a4
a5
a6
a7
a8
a9
a10
CI=v2a6v5a7v3a4v4a8v6a11v5a10v7a5v2 es un ciclo de G
CIS=v2a6v5a11v6a8v4a4v3a3v2 es un ciclo simple de G
G
a11
C
O
N
E
X
I
Ó
N
E
N
G
R
A
F
O
S
GRAFOS CONEXOS Y NO CONEXOS
Un grafo G se llama CONEXO si dados dos vértices cualesquiera V1 yVj de G, existe una
cadena C – (V1 ,Vj ). En caso contrario, el grafo G se llama NO-CONEXO.
EJEMPLOS
G1 es un grafo conexo, mientras que G2, y G3 son grafos no-conexos.
Un grafo G no-conexo esta formado por dos o mas grafos conexos. Cada uno de estos grafos
conexos se llama una COMPONENTE CONEXA del grafo G.
Si existe una cadena C – (V1 ,Vj ) o V1 =Vj en un grafo G, diremos queV1 esta conectado con
Vj. La relación “estar conectado”, definida sobre el grafoV(G) es una relación de equivalencia
(¿por que?) . En esta relación de equivalencia cada clase de equivalencia corresponde a una
componente conexa del grafo G.
G1 G2
G3
DISTANCIA EN UN GRAFO
En un grafo conexo G, la distancia d (V1 ,Vj ) entre dos de sus vérticesV1 yVj es la
longitud de la cadena simple mas corta entre ellos, es decir, d (V1 ,Vj ) = min (CS) donde
CS - ( V1 , Vj )
EJEMPLO
d ( V1 , V5 ) = ?
Las diferentes cadenas simples CS - ( V1 , Vj ) y sus longitudes correspondientes son:
v1
v2v3
v4
v5
v6
v7
v8
a1
a2 a3
a4a5
a6
a7
a8
a9
a10
CS1: v1a1v2a2v3a3v5 (C1) = 3
CS2: v1a10v8a8v4a4v3a3v5 (C2 ) = 4
CS3: v1a10v8a8v4a7v7a6v6a5v5 (C3 ) = 5
CS4: v1a1v2a2v3a4v4a7v7a6v6a5v5 (C4 ) = 6
Por lo tanto:
d ( V1 , V5 ) = (CS) = 3
G
La distancia entre dos vértices de un grafo conexo G, puede ser considerada como una
función que asigna a cada par de vértices del grafo G un numero entero no negativo. Esta
función así definida satisface las condiciones:
1. d ( V1 , Vj ) ≥ 0 y d ( V1 , Vj ) = 0 si y solo si V1 = Vj
2. d ( V1 , Vj ) = d ( V1 , Vj )
3. d ( V1 , Vj ) = d ( V1 , Vk ) + ( Vk , Vj ) para algún vértice de Vk
La función que satisface estas tres propiedades se llama METRICA. Luego la distancia
entre los vértices de un grafo es una métrica.
Sea G un grafo conexo y v un vértice de G, la excentricidad de v, E(v), es la distancia que
hay de v al vértice mas lejano a v en el grafo G, es decir:
E(v) = máx. d ( V, V1) donde V1 Є V(G)
En un grafo conexo G un vértice con mínima excentricidad se llama el centro de G.
En el grafo de la figura anterior E(V3) = E(V4) = 2, el lector puede comparar que V3 y V4
son centros del grafo G. En un grafo conexo G la excentricidad de un centro se llama
RADIO de G
El diámetro D de un grafo conexo G, es la máxima distancia entre dos pares de vértices de
G, esto es : D(v) = máx. d ( V, W) donde V, W Є V(G)
D
I
S
T
A
N
C
I
A
E
N
U
N
G
R
A
F
O
EJEMPLO
En el grafo G1 se tiene: En el grafo G2 se tiene:
La excentricidad de cada vértice es 3 E(V1) = E(V2) = E(V3) = E(V4) = 2, E(V5) = 1
El radio de G1 es 3 El radio de G2 es 1
Todos sus vértices son centros El único centro es V5
El diámetro de G1 es 3 El diámetro de G2 es 2
v1 v2
v3
v4
v5
v6
G1
v1
v2
v3
v4 v5
G2
D
I
S
T
A
N
C
I
A
E
N
U
N
G
R
A
F
O