Teoria de grafos
Grafo: Un grafo G=(V,A, λ ) es una estructura 3-tuple donde : V = {Conjunto de vértices o nodos} A = {Conjunto de aristas o arcos} λ =función incidencia Grafos Dirigidos: G:
a
b
Grafos no Dirigidos:
c
Función de incidencia
λ
= funcion de incidencia
λ
:A X1 X2 X3 X4 Xn
→
V*V
. .
(V1,V2) (V2,V3) (V3,V4) (V4,V5) (Vn,Vn+1)
Grafos Dirigidos: G:b
λ
a
c
Γ + = conjunto de que salen
Γ − = conjunto de aristas que entran
sale Como que entra loop G:
Nodo fuente
1 2
a Entra
b En cualquier grafo dirigido sin bucles se cumple: #arcos = n(n-1)
3
Nodo sumidero o pozo
Ejemplo:
A
X1 B X4 X2 X6 X3 X8 X10 C X7 X9 X5
D
V = { A , B ,C , D }
… nodos
A = { (A,B) , (A,C) , (A,D) , (B,A) , (B,D) , (C,A) ,(C,D) , (D,A) , (D,B) , (D,C)} …aristas ó Arcos = A={x1,x2,x3,x4,x5,x6,x7,x8,x9,x10}
λ
:
A
VxV
x1 (A,B) x2 (A,C)
. . . . . .
x10 (D,C)
λ λ
(x1)=(A,B) (x2)=(A,C)
. . . . . .
λ
(x10)=(D,C)
Grafos no Dirigidos:
G:
1 2
3
4
G’:
a b
En cualquier grafo no dirigido sin bucles donde (#nodos = n), se cumple: #arcos =
n(n - 1) 2
c
d
G:
G:VERTICES: Conjunto de Vértices Sucesores
Γ (Xi) ={Vj ∈V /(Vi,Vj)∈A}
+
Conjunto de Vértices Predecesores
Γ (Xi) ={Vj ∈V /(Vj,Vi)∈A}
−
Ejemplo:
Conjunto de Vértices Sucesores Tau(B) = {C, D} Conjunto de Vértices Predecesores Tau(B) = {C, D, E , F}
Grado o Valencia de un Vértice: Grado Interior :Número de aristas que entran
d − ( Xi) =| Γ − ( Xi) |
Grado Exterior : Número dearistas que salen
d + ( Xi) =| Γ + ( Xi) |
Grado de un Vértice:
d ( Xi ) = d + ( Xi ) + d − ( Xi )
Teorema de Euler: En todo grafo la suma de los grados de los vértices es igual a dos veces el número de aristas
∑d(Xi) = 2| A|
Ejemplo:
d + ( Xi )
d + ( X1)
=3
d − ( Xi )
d − ( X 1 ) =2 d − ( X 2 ) =4 d *− ( X 3 ) =1
d − (X 4)
=3
d ( Xi )
d ( X1)
d(X 2)
d(X3)
=5
∑d ( Xi) = 18
d * ( X i ) = loop
d + ( X 2 ) =2 d + ( X 3 ) =2
=6 =3 =4
d + ( X 4)
=1
d(X 4)
Max|d+(xi)= |V|-1. Max|d-(Xi)=|V|+1 Suma(dXi) =pares
Teorema:
∑ d ( Xi ) = 2(U )
i =1
4
18 = 2 (9 ) 18 = 18 _ cumple
Ejercicio: Dada la tabla encontrar el grafo Salen 2,3 1,3 2 entran 2 1,2,3 1,2,3
d + ( Xi )
d + (X 2)
d + ( X1)
=2 =2 =1
d − ( Xi )
d − ( X1) d −(X 2)
=2 =2 =1
d ( Xi )
d ( X1)
d(X 2 )
=4 =4
d +(X 3)
d *− ( X 3 )
d ( X 3 ) =2
Grafos Etiquetados o Ponderado: Un grafo G es etiquetado si cada vértice y aristas están asociados con cierta información. Las aristas son asignadas: pesos, costos, tiempos, longitudes. Los nodos son asignados: lugares o ciudades.
X = {ciudades} W = {costos}
Camino: Es la sucesión finita dearcos. Es una sucesión finita de vértices y aristas alternos, donde cada arista tiene por extremo los vértices adyacentes. Ejemplo:
Camino (X1, X4) =(X1,U1,X2,U3,X3,U5,X2,U4,X4)
Camino Simple: Es el conjunto de aristas que no incluyen dos veces la misma arista (que no se repite las aristas). Camino Elemental: Es el conjunto de aristas, que no incluyen el mismo vértices dos veces CE=(X1,U1,X2,U3,X3,U6,X4) Circuito: Es el camino cerrado donde el vértice inicial y final coinciden Circuito Simple: Es un camino simple cerrado Circuito Elemental: Es un camino elemental cerrado
LONGITUD DE UN CAMINO Es el numero de aristas que contiene un camino
Longitud (X1,X4) = 6
Vértices Adyacentes: Dos vértices son adyacentes si uno es el sucesor del otro
Aristas adyacentes Dos aristasson adyacentes si tienen el mismo vértice o un extremo en común
Grafo Completo Cuando cada vértice es adyacente a todos los demás vértices, En un grafo sin bucle, y sin aristas paralelas.
G:
N (aristas)= n(n-1); n: número de nodos.
G:
N(aristas)= (n(n-1))/2
Grafo Conexo: Cuando en cada par de vértices distintos, existe un camino que los une.
G:
Grafo fuertemente conexo:...
Regístrate para leer el documento completo.