Teoría de Grafos

Teoría de Grafos

FISI-D Q P

1

Definición de Grafo:
Un grafo G=(V,A,  ) es una estructura 3-tuple
formado por un conjunto de vertices y aristas
donde:
V = {Conjunto de vértices o nodos} V ={v1,…,vn}
A = {Conjunto de aristas o arcos} A = {a1,…,am}
 =función incidencia
Grafos Dirigidos:

Grafos no Dirigidos:

G:
a

b

c

FISI-D Q P

2

Grafo: Definición de arcosFISI-D Q P

3

Grafos
red de ordenadores

ARCOS
O
ARISTAS

multigrafos:

Relaciones
INFORMACION
NODOS
O
VERTICES

FISI-D Q P

4

Función de incidencia


= función de incidencia



:A

 V*V

 (a) = ai

a -
Arista

funcion

 (a1)  (v 1.v2 )
(a2 )  (a 2 )  (v 2.v3 )
(a3 )  (a 3 )  (v 3.v4 )
(a1)

(an )

 (a n )  (v n .vn 1)
FISI-D Q P5



Grafos Dirigidos: Cuando todas las
aristas tienen una orientación

LAZO o bucle: arista que une a un vértice consigo
mismo

G:

a

b

c

  = conjunto de nodos de arcos que salen
  = conjunto de nodos de aristas que entran
FISI-D Q P

6

entrada
=2

salen

b

a

loop

Entran
En cualquier grafo dirigido sin bucles
puede existir o no los nodosllamados:
FUENTE Y SUMIDERO o pozo

G:
(Nodo ) fuente
1

2

3

(Nodo) sumidero o pozo

FISI-D Q P

7

Ejemplo:

X1
B

A
X4

X2

X6

X3

X9

X5

X8

X10
C

NODOS
ARCOS O ARISTAS

D

X7

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}:

FISI-D Q P

8

Grafos no Dirigidos: Cuando

todas las

.
.
aristas no tienen una orientación
.
.
.

.

G:
1

2

3

4

FISI-D Q P

9

G’:
a

c

b

d

En cualquier grafo no
dirigido sin bucles donde
(#nodos = n), se cumple:
#arcos =

G:

n(n - 1)
2

G:

FISI-D Q P

10

EN GRAFOS DIRIGIDOS
CONJUNTO de Vértices Sucesores

 ( Xi)  VjV /(Vi,Vj)  A


Conjunto de Vértices Predecesores

 ( Xi)  Vj V /(Vj,Vi)  A


FISI-D Q P

11

Ejemplo:

Conjunto de Vértices Sucesores




(B) = {C, D}

Conjunto de Vértices Predecesores

 (B) = {C, D, E , F}

FISI-D Q P

12

Grado o Valencia de un Vértice:
Grado Interior :Número de aristas que entran

d  ( Xi) |   ( Xi) |
Grado Exterior : Númerode aristas 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 |
FISI-D Q P

13

Ejemplo:

d  (Xi)
d  ( X1 )

d  (Xi)

d (Xi)
d ( X1 )

=5

d(X 2 )
d(X3)

=6

d  ( X 3 ) =2

d  ( X 1 ) =2
d ( X 2 ) =4
d * ( X 3 ) =1

d  ( X 4)

d  (X4 )

d(X 4 )

d ( Xi)  18

=4

=3

d  ( X 2 ) =2
=1

propiedades

=3

=3

d * ( X i )  loop

 d(Xi )  18

Max d  ( X i )  V  1 Min d  ( X i )  V  1
FISI-D Q P

14

Teorema:

4

 d ( Xi)  2( A)

verificando

i 1

18  2(9)
18  18 _ cumple

Salen
2,3
1,3
2

Ejercicio:

entran
21,2,3
1,2,3

Dada la tabla encontrar el grafo



d (Xi)
d  ( X1 )

d  (X2 )

=2
=2

d  (Xi)
d  ( X1 )
d  (X2 )

d (Xi)
=2

d ( X1 )

=4

=2

d(X 2 )

=4

d  ( X 3 ) =1 d * ( X 3 ) =1 d ( X 3 ) =2

FISI-D Q P

15

Grafos Etiquetados o Ponderado:

Un grafo G es etiquetado si cada vértice y aristas están asociados con cierta
información. Las aristas sonasignadas: pesos, costos, tiempos, longitudes.
Los nodos son asignados: lugares o ciudades.

X = {ciudades}
W = {costos}

FISI-D Q P

16

Camino:
Es toda sucesión de arcos tales el vértice extremo de cada arco es
a su vez origen del siguiente, excepto el último
Ejemplo:

Camino (X1, X4) =(X1,U1,X2,U3,X3,U5,X2,U4,X4)
= U1.U3,U5,U4

FISI-D Q P

17

Camino Simple:
Es el...