Teoria De Grafos (Matematicas Discretas)

29/10/2013

Definición de Grafos

Unidad 6.Teoría de Grafos

Un grafo G es un par (V,E) donde:
V ={v1,…,vn} es un conjunto de vértices
E = {e1,…,em} es un conjunto de aristas,
Los vértices se representan como puntos y las aristas como líneas
entre vértices
Ejemplo:
G = (V,E)
V = {a,b,c,d }
E = {{a,b}, {b,c}, {a,c}, {a,d}, {d,b} }

2

Tipos de grafos
Es importante recordar queun mismo grafo puede tener diferentes
representaciones gráficas
Ejemplo:

Tipos de Grafos
Si se permite que haya más de una arista se
habla de multigrafos:

Dos representaciones del mismo grafo
G = ({a,b,c,d,e,f},{{a,b},{a,e},{a,f}{e,f},{b,c},{c,d},{e,d},{d,f}})

Definición
• Nodos / Vértices: constituyen los objetos de la situación a
representar.
Ejemplo: V = {A,B,C,D,E}
• Ejes /Aristas /Arcos: conforman las relaciones entre un par de
objetos representados por los nodos.
Ejemplo: X = {(A,B),(A,C),(B,C),(B,E),(C,D),(D,E)}

Teoría de Gafos
Atributos Cualitativos

Es lo que se conoce como variables nominales
• En Nodos: sirve para identificar o describir al objeto que se
quiere representar
• En Ejes: describe el tipo de relación que hay entre dos
objetos.

Tantolos nodos como ejes, pueden tener atributos
cuantitativos y/o cualitativos (variables de cualquier tipo).

1

29/10/2013

Ejemplos

Atributos Cuantitativos
Corresponden a variables ordinales
• En Nodos: miden algún aspecto común entre los distintos
objetos

12

10

7

7

12

10

6
6

5

5

Tipos de Grafos

Aplicaciones

Un grafo dirigido o dígrafo, secaracteriza porque cada
arista a tiene una dirección asignada, esta asociada a un
par ordenado de vértices de G.

Redes conceptuales

En este caso las aristas se llaman arcos y se
representan como pares para indicar el orden:
V = { a,b,c,d,e}
A ={(e,a), (a,b), (b,a), (d,a), (c,d), (d,c),(b,c),(c,b) }

A = (a,b) y se expresa a → b

Aplicaciones
Redes de transporte

Aplicaciones
Plano deautopistas

2

29/10/2013

Aplicaciones: calles de una ciudad
1

2

100

3

100

Circuitos eléctricos

4

100

100

100

5

100

Aplicaciones

100

100

52

6

7

100

100

8

30

9

100

100
100

10
100
70

11

100

12

120
100

14

100

13
100

15

100

100

100

100

Aplicaciones
Red Social

16

100

17120

100

18

Aplicaciones
Polímeros

Aplicaciones
Red de computadoras

Topologías
B

Anillo
B

I

Árbol

A
D

Estrella

F
C

E

E

B

F

G

D

A

G
E

H

C

H

C

I

F

G

D
H

I

3

29/10/2013

Tipos de Grafos

Clasificación

Cuando las aristas tienen un valor numérico asociado se llama de
grafos valorados, pesados:Grafos

Multigrafos
E je 1 B -A

No orientados o
Bidireccionales

E je 2 A -B

A

B

EA
j e B

A

B

E je 3 A -B

E je 4 A -B

E je 1 B -A
E je 1 A -B

EA
j e B

Orientados o
Direccionados

A

B
EB
j e A

A

B

E je 2 A -B

E je 3 A -B

Al valor numérico asociado se le llama costo de la arista

E je 3 B -A

Grado de un Nodo

Definiciones enGrafos

• El grado de un nodo es la cantidad de ejes
incidentes al vértice v.

• Un camino en un grafo es una sucesión de ejes
e1 e2.......ek tal que un extremo de ei coincide con uno
de ei-1 y el otro con uno de ei+1.

• Notación: d(v) = grado de v.

• Un camino simple es un camino que no pasa dos
veces por el mismo nodo.

• Teorema: La suma de los grados de los nodos de
un grafo es2 veces el número de ejes, o sea:
i=1,n d (vi) = 2 m

Componentes Conexas
Un grafo se dice conexo si existe un camino entre todo par de
nodos.

• Un circuito es un camino que empieza y termina en
el mismo nodo. (camino circular)

Grafos Completos
•Un grafo se dice completo si todos los nodos son adyacentes entre si.
K3
B

K4
A

C

K5

B

C

B

A

A

D

C

E...