1-definiciones grafos
Post on 13-Apr-2016
228 Views
Preview:
DESCRIPTION
TRANSCRIPT
ES
TRU
CTU
RA
S
DIS
CR
ETA
S II
Estructuras Discretas II
Introducción a la Teoría de Grafos
Dra. Norka Bedregal Alpaca1
Grafos
Grafos: Modelos matemáticos de situaciones reales
Ejemplos: Mapa de carreteras, Plano del tren eléctrico Plano callejero Red de PCs, Plano de un circuito eléctrico Arboles genealógicos, etc.
Aplicaciones:Compiladores y traductores, Redes, Planificación, etc.Origen: 1736 (Los Puentes de Könisberg. Euler)
Dra. Norka Bedregal Alpaca
Def
inic
ione
s: G
rafo
s
2
Grafos
Desafortunadamente no existe una terminología estandarizada en la teoría de los grafos,
Por lo tanto es oportuno aclarar que las presentes definiciones pueden variar ligeramente entre diferentes publicaciones de estructuras de datos y de teoría de grafos,
En general se puede decir que un grafo, es la representación (para nuestro caso) gráfica de los datos de una situación particular,
Ejemplo:
Los Angeles
Chicago
Boston
Nueva York
Miami
Filadelfia
Vuelos de lagunas aerolíneas
Dra. Norka Bedregal Alpaca
3
Def
inic
ione
s: G
rafo
s
Definición: Grafo
Definición: Grafo
Los grafos de manera general pueden ser considerados diagramas o dibujos, de manera formal como un par de conjuntos.
Un grafo G = (V, E) se define como el par formado por:
Un conjunto V cuyos elementos reciben el nombre de vértices. El conjunto V de vértices del grafo, se denota por V(G).
Un conjunto E de pares no ordenados de elementos distintos llamados aristas. El conjunto E de aristas del grafo, se denota por E(G).
La notación general es:V={v1, v2,..., vn}E={(vi,vj); ( vn,,vm), ...} Dra. Norka Bedregal Alpaca
4
Def
inic
ione
s: G
rafo
s
Definición: Grafo
Dra. Norka Bedregal Alpaca
5
Def
inic
ione
s: G
rafo
s
Definición: Grafo
Vértices Adyacentes:Dos vértices vi, vj son adyacentes si son los extremos de una arista, es decir, si el par de vértices (vi, vj) es un elemento de E.
V={v1, v2, v3}
E={(v1,v2), (v2,v3), (v1,v3)}
Dra. Norka Bedregal Alpaca
6
GR
AFO
S - D
IGR
AFO
S
Otros Tipos de Grafos
Multigrafo: es un grafo con varias aristas entre dos vértices.
V={v1, v2, v3}E={(v1,v2), (v2,v3), (v2,v3), (v1,v3), (v1,v3)}
Pseudografo: tiene aristas cuyos extremos coinciden (origen y fin en el mismo vértice), tales aristas se denominan lazos.
V={v1, v2, v3}E={(v1,v1), (v1,v2), (v2,v2), (v1,v3)}
Dra. Norka Bedregal Alpaca
7
Def
inic
ione
s: G
rafo
s
Tipos de Grafos
Digrafo (grafo dirigido): A cada arista se le asigna un orden en sus extremos, en el dibujo se indica con una flecha. Los pares que forman los elementos de E son pares ordenados.
V={v1, v2, v3}E={(v1,v2), (v2,v3), (v3,v1)}
Dra. Norka Bedregal Alpaca
8
Def
inic
ione
s: G
rafo
s
Tipos de Grafos
Dra. Norka Bedregal Alpaca
9
En general si no se especifica que un grafo G es dirigido o no, supondremos que es no dirigido.
La figura proporciona un ejemplo de un grafo dirigido sobre V= {a, b, c, d, e} con E= {(a, a), (a, b), (a, d), (b, c)}. D
efin
icio
nes:
Gra
fos
Otra Definición: Grafo
Grafo:
Un grafo es una terna G = (V, E, T), en donde V y E son conjuntos finitos,
T es una aplicación que hace corresponder a cada elemento de A un par de elementos de V.
Los elementos de V y de E se llaman, respectivamente, "vértices" y "aristas" de G,
T asocia entonces a cada arista con sus dos vértices.
Dra. Norka Bedregal Alpaca
10
Def
inic
ione
s: G
rafo
s
Grado de un vértice
Es el número de aristas que parten de él. El grado de un vértice se conserva por isomorfismo.
Dado un vértice u de V(G), su grado es gr(u).
El vértice y es de grado 3El vértice x es de grado 3El vértice z es de grado 3El vértice w es de grado 3
Dra. Norka Bedregal Alpaca
11
Def
inic
ione
s: G
rafo
s
Subgrafo
Dra. Norka Bedregal Alpaca
12
Def
inic
ione
s: G
rafo
s
¿Qué tipo de subestructura nos sirve para analizar un grafo?
¿Es posible trazar dos grafos que parezcan distintos pero que tengan la misma estructura subyacente?
Definición
Si G = (V, E) es un grafo (dirigido o no), entonces G1 = (V1, E1) es un subgrafo de G si
V1 V y E1 E,
donde cada arista de E1 es incidente con los vértices de V1.
Subgrafo
Un subgrafo se obtiene eliminando alguna(s) arista(s) y/o vértice(s). Si se suprime un vértice, se suprimen todas las aristas que tienen por origen o fin dicho vértice.
G’ es un subgrafo de G, al suprimir el vértice x y las aristas que llegan a él.
Dra. Norka Bedregal Alpaca
13
Def
inic
ione
s: G
rafo
s
Subgrafo Recubridor
Dra. Norka Bedregal Alpaca
14
Def
inic
ione
s: G
rafo
s
Definición
Dado un grafo (dirigido o no) G = (V, E), sea G1=(V1, E1) un subgrafo de G. Si V1 = V, entonces G1 es un subgrafo recubridor de G.
Los subgrafos G3 y G4 son subgrafos recubridores del grafo G en la parte a) de la figura anterior. Los grafos dirigidos G’’ y G’’’ son dos grafos recubridores de G en la parte b).
Subgrafo Inducido
Dra. Norka Bedregal Alpaca
15
Def
inic
ione
s: G
rafo
s
Definición
Sea G = (V, E) un grafo (dirigido o no). Si U V, el subgrafo de G inducido por U es el subgrafo cuyo conjunto de vértices es U y que contiene todas las aristas (de G) de la forma:
1) (x, y), para x, y U, si G es dirigido o;
2) {x, y} para x, y U, si G no es dirigido
Se denota a este subgrafo como U.
Un subgrafo G’ de un grafo G = (V, E) es un subgrafo inducido si existe U V tal que G’ = U.
Subgrafo Inducido
Dra. Norka Bedregal Alpaca
16
Def
inic
ione
s: G
rafo
s
Para los subgrafos de la figura, se ve que G2 es un subgrafo inducido de G pero el subgrafo G1 no es un subgrafo inducido ya que no aparece la arista {a, d}.
Subgrafo Inducido
Dra. Norka Bedregal Alpaca
17
Def
inic
ione
s: G
rafo
s
EJEMPLO
Sea G el grafo de la figura. • Los subgrafos G1 y G2 de la figura son inducidos. • G1=U1 para U1 ={b, c, d, e}. • G2=U2 para U2={a, b, e, f}. • G3 no es un subgrafo inducido; los vértices c, e están en G3, pero la arista {c, e} de (G) no está presente.
Grafo Regular
Un grafo es regular si todos los vértices tienen el mismo grado, si dicho grado es k, el grafo se denominará k-regular.
Dra. Norka Bedregal Alpaca
Los grafos G, G’ son grafos 3-regular y 2-regular.
La regularidad de grafos se conserva por isomorfismo.
18
Def
inic
ione
s: G
rafo
s
Grafo Completo
Un grafo es completo si cada par de vértices son los extremos de una arista.
Dos grafos completos con el mismo número de vértices son isomorfos.
Se designará el grafo completo con n vértices por Kn.
Se puede representar Kn, para n mayor o igual a tres, mediante los vértices de un polígono regular Pn de n lados siendo las aristas de Kn los lados y todas las diagonales de Pn.
Dra. Norka Bedregal Alpaca
19
Def
inic
ione
s: G
rafo
s
Grafo Complementario
Dra. Norka Bedregal Alpaca
20
Def
inic
ione
s: G
rafo
s
Definición
Sea G un grafo no dirigido sin lazos con n vértices. El complementario de G, ( ) es el subgrafo de Kn formado por los n vértices de G y todas las aristas que no están en G.
(Si G = Kn, es un grafo con n vértices y ninguna arista. A este grafo se le llama grafo nulo).
G
En a) aparece un grafo no dirigido de cuatro vértices.
Su complementario se muestra en la parte b).En el complementario el vértice a está aislado.
Grafo Bipartito
Dra. Norka Bedregal Alpaca
Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto
21
Def
inic
ione
s: G
rafo
s
Ejemplos de Grafos
Dra. Norka Bedregal Alpaca
• Todo grafo completo es regular porque cada vértice tiene grado |V|-1 al estar conectado con todos los otros vértices.
• Un grafo regular no tiene por qué ser completo • Un grafo bipartido regular se denota Km,n donde m, n es el grado de
cada conjunto disjunto de vértices. • En la figura se tienen los grafos K1,2, K3,3, y K2,5
22
Def
inic
ione
s: G
rafo
s
Matrices de Representación de un Grafo
Matriz de Adyacencia
Dra. Norka Bedregal Alpaca
Un grafo simple G = (V, E) con n nodos
Puede ser representado por su matriz de adyacencia A.
1 si { , } es un arco de .
0 en otro caso. i j
ijv v G
a
23
Def
inic
ione
s: G
rafo
s
Matrices de Representación de un Grafo
Dra. Norka Bedregal Alpaca
Matriz de adyacencia para K5.
d
a
b
c
e a
c
e
f
K5
a 0 1 0 0 1 1b 1 0 1 0 0 1c 0 1 0 1 0 1d 0 0 1 1 0 1 e 1 0 0 1 0 1 f 1 1 1 1 1 1
a b c d e f
24
Def
inic
ione
s: G
rafo
s
Matrices de Representación de un Grafo
Matriz de Incidencia
Dra. Norka Bedregal Alpaca
Sea G=(V, E) un grafo no dirigido. Suponga que v1,v2,…vn son los nodos y e1,e2,…,em son los arcos de G.
La matriz de incidencia con respecto a este ordenamiento de V y E es la matriz de orden nxm
1 cuando el arco es incidente a .
0 en otro caso. j i
ije v
m
25
Def
inic
ione
s: G
rafo
s
Matrices de Representación de un Grafo
Dra. Norka Bedregal Alpaca
Matriz de incidencia para K5.
d
a
b
c
e a
c
e
f
e2
e1
e3
e4
e5
e8
e7
e6 e10
e9
a 1 0 0 0 1 1 0 0 0 0
b 1 1 0 0 0 0 1 0 0 0
c 0 1 1 0 0 0 0 1 0 0
d 0 0 1 1 0 0 0 0 1 0
e 0 0 0 1 1 0 0 0 0 1
f 0 0 0 0 0 1 1 1 1 1
e1 e2 e3 e4 e5 e6 e7 e8 e9 e10
26
Def
inic
ione
s: G
rafo
s
Caminos en un Grafo
Camino
Un camino en un grafo G es una sucesión finita de vértices y aristas alternos, donde cada arista tiene por extremos los vértices adyacentes.
{ v0 , (v0,v1), v1, (v1,v2) ,..., vn-1, (vn-1,vn) , vn }
A v0 y vn se les denomina extremos del camino.
Dra. Norka Bedregal Alpaca
27
Si x, y son vértices (no necesariamente distintos) de un grafo no dirigido G = (V, E). Un camino x-y en G es una sucesión alternada finita (sin lazos)
x= x0, e1, x1, e2, x2, e3,...,en-1, xn-1, en, xn=y
de vértices y aristas de G, que comienza en el vértice x y termina en el vértice y y que contiene las n aristas ei={xi-1, xi} donde 1in.
Def
inic
ione
s: G
rafo
s
Caminos en un Grafo
Dra. Norka Bedregal Alpaca
28
Longitud del camino
La longitud de un camino es n, el número de aristas que hay en el camino (Si n = 0, no existen aristas, x = y, y el camino se denomina trivial).
Camino cerrado
Cualquier camino x-y donde x = y (y n > 1) es un camino cerrado o ciclo. En caso contrario, el camino es abierto.
Def
inic
ione
s: G
rafo
s
Caminos en un Grafo
Dra. Norka Bedregal Alpaca
29
Definición
Consideremos un camino x-y en un grafo no dirigido G = (V, E).
a) Si no se repite alguna arista en el camino x-y, entonces el camino es un recorrido o camino elemental x-y.
b) Cuando ningún vértice del camino x-y se presenta más de una vez, el camino es un camino simple x-y. El término ciclo se usa para describir el camino simple cerrado.
Def
inic
ione
s: G
rafo
s
Caminos en un Grafo
Dra. Norka Bedregal Alpaca
30
w
x y
z
En el grafo de la figura se cumple: Es K4 completo
{ x, y, w, z, y } es un camino { x, y, w } es un camino simple { x, y, w, z, x } es un ciclo
Def
inic
ione
s: G
rafo
s
Caminos en un Grafo
Dra. Norka Bedregal Alpaca
31
Teorema
Sea G = (V, E) un grafo no dirigido, con a, b V, ab. Si existe un camino elemental de a a b, entonces existe un camino simple de a a b.
Demostración.
Como hay al menos un camino elemental de a a b, se selecciona el que tenga la longitud más corta, digamos {a,x1},{x1,x2},...,{xn,b}.
Si este camino no es un camino simple, se tiene la situación
{a,x1},{x1,x2},...,{xk-1,xk},{xk,xk+1},{xk+1,xk+2},...,{xm-1,xm},{xm,xm+1},...,{xn,b},
donde k<m y xk=xm, posiblemente con k=0 y a(=x0)=xm, o m=n+1 y xk=b(=xn+1). Pero entonces
{a,x1},{x1,x2},...,{xk-1,xk},{xm,xm+1},...,{xn,b}
es un camino elemental simple más corto de a a b.
Def
inic
ione
s: G
rafo
s
Grafo Conexo
Dra. Norka Bedregal Alpaca
32
Definición
Sea G = (V, E) un grafo no dirigido. Decimos que G es conexo si existe un camino entre dos vértices cualesquiera distintos de G.
Si e grafo G es dirigido y existe por lo menos un camino entre dos vértices cualesquiera entonces se dice que el grafo G es fuertemente conexo.
Sin un grafo no cumple con las condiciones anteriores se dice que es disconexo o no-conexo.
Arista de SeparaciónUna arista de un grafo G se dice de separación si G es conexo pero al suprimir la arista se divide en dos componentes conexos
Def
inic
ione
s: G
rafo
s
Conectividad en Grafos
Dra. Norka Bedregal Alpaca
33
Def
inic
ione
s: G
rafo
s
Definiciones: Sea G=(V, E) un grafo conexo, se llama punto de corte a un vértice v
de G, de modo que el subconjunto Gv de G con vértices V-{v} y cuyas aristas son aquellas de E cuyos vértices están en V-{v} no es conexo.
Se llama istmo a una arista a de G de modo que el grafo (V, E-{a}) no es conexo.
Son puntos de corte: {e, d, c }. La arista: (e,d), es un istmo.
Ejemplo:
Conectividad en Grafos
Dra. Norka Bedregal Alpaca
34
Def
inic
ione
s: G
rafo
s
Observaciones:
Sea un grafo G=(V, E) que posee k componentes conexas, se verifica la desigualdad: #(E) (#(V) - k)·(#(V) - k+1).
Si G=(V, E) se verifica: #(E) > (#(V) - 1)(#(V) -2). ® G es grafo conexo con una componente.
Caminos en un Grafo
Dra. Norka Bedregal Alpaca
35
Por lo tanto, un grafo no dirigido G = (V, E) es disconexo si y sólo si V puede separarse en al menos dos subconjuntos V1, V2 tales que no haya una arista en E de la forma {x, y} donde xV1 e yV2.
Un grafo es conexo si y sólo si tiene solamente una componente.
Definición Para cualquier grafo G = (V, E), el número de componentes de G se denota con (G).
Def
inic
ione
s: G
rafo
s
Caminos en un Grafo
Dra. Norka Bedregal Alpaca
36
Definición
Para cualquier grafo G = (V, E), el número de componentes de G se denota con (G).
Método para determinar si un grafo es conexoUn método para comprobar si un grafo es conexo es el siguiente:
– Se halla la matriz de adyacencia y se eleva a la (n-1)-ésima potencia
– Se calcula la suma de las potencias de A hasta An-1
– Si todos sus elementos son 0, el grafo es conexo.
Def
inic
ione
s: G
rafo
s
Isomorfismo de Grafos
Dra. Norka Bedregal Alpaca
37
Def
inic
ione
s: G
rafo
s Definición
Sean G1=(V1, E1) y G2=(V2, E2) dos grafos no dirigidos.
Una función f: V1 ® V2 es un isomorfismo de grafos si:
1) f es biyectiva
2) a, b V1, {a, b} E1 si y sólo si {f(a), f(b)} E2.
Cuando existe tal función, G1 y G2 son grafos isomorfos.
Isomorfismo de Grafos
Dra. Norka Bedregal Alpaca
38
Def
inic
ione
s: G
rafo
s
V(G)={w, x, y, z}
E(G)={(x,y), (x,z), (x,w), (y,z), (y,w), (w,z)}
V(H)={t, s, v, u}
E(H)={(s,v), (s,u), (s,t), (v,u), (v,t), (t,u)}
f(w)=t, f(x)=s, f(y)=v, f(z)=u
Ejemplo:
Isomorfismo de Grafos
Dra. Norka Bedregal Alpaca
39
Def
inic
ione
s: G
rafo
s
Para los grafos de las partes a) y b) de la figura, la función f definida por
f(a)=w, f(b)=x, f(c)=y, f(d)=z
da como resultado un isomorfismo.
(De hecho cualquier correspondencia uno a uno entre {a, b, c, d} y {w, x, y, z} será un isomorfismo, ya que ambos grafos son completos).
En consecuencia en lo que se refiere a la estructura estos grafos se consideran iguales, cada uno es isomorfo al grafo K4.
Ejemplo:
Isomorfismo de Grafos
Dra. Norka Bedregal Alpaca
40
Def
inic
ione
s: G
rafo
s
Para los grafos c) y d) de la figura se necesita un poco más de cuidado. La función g definida por: g(m)=r, g(n)=s, g(p)=t, g(q)=u
es uno a uno y sobre.
Sin embargo, aunque {m, q} es una arista del grafo de la parte c), { g(m), g(q)} = {r, u} no es una arista del grafo de la parte d).
En consecuencia, la función g no define un isomorfismo de grafos.
Ejemplo:
Isomorfismo de Grafos
Dra. Norka Bedregal Alpaca
41
Def
inic
ione
s: G
rafo
s
Ejercicio:
Determine si los grafos de la figura son isomorfos
Grafo Etiquetado
Dra. Norka Bedregal Alpaca
42
Def
inic
ione
s: G
rafo
s Grafo o Digrafo etiquetado,
Se dice que un grafo o un digrafo es etiquetado si sus aristas tienen asignado un número.A la etiqueta de una arista a de G se le suele designar longitud de a.
Dado un camino, en un grafo etiquetado, se denomina longitud del camino a la suma de las etiquetas de las aristas, si todas las etiquetas son 1, la longitud del camino, en un grafo etiquetado, coincide con la longitud de un camino en un grafo o digrafo.
Dados dos vértices de un grafo etiquetado, se denomina distancia entre tales vértices, a la suma de los valores de sus aristas, por el camino de longitud mínima.
Dra. Norka Bedregal Alpaca
43
Def
inic
ione
s: G
rafo
sGrafo Etiquetado
Ejemplo de grafo etiquetado
Fin
Dra. Norka Bedregal Alpaca
44
Def
inic
ione
s: G
rafo
s
top related