teorias de grafos

Teoría de Grafos
Matemáticas Discretas: Daniel A. Quinto Pazce
Semestre 2014 -2

Matematicas Discretas Daniel A. Quinto Pazce

1

Concepto 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 = {e1,…,em}
 =función incidencia
Grafos Dirigidos:Grafos no Dirigidos:

G:
a

b

c

Matematicas Discretas Daniel A. Quinto Pazce

2

Grafo:

Matematicas Discretas Daniel A. Quinto Pazce

3

Grafos

Matematicas Discretas Daniel A. Quinto Pazce

4

Función de incidencia


= función de incidencia



:A



V*V

a - ( a )
Arista

= ai

función

 (a1)  (v 1.v2 )
(a2 )  (a 2 )  (v 2.v3 )
(a3 ) (a 3 )  (v 3.v4 )


(an )  (a n )  (v n .vn 1)
(a1)

Matematicas Discretas Daniel A. Quinto Pazce

5



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
Matematicas Discretas Daniel A.Quinto Pazce

6

entrada
=2

salen

b

a

loop

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

G:
(Nodo ) fuente
1

2

3

(Nodo) sumidero o pozo

las aristas son relaciones “muchos a muchos” entre nodos...

Matematicas Discretas Daniel A. Quinto Pazce

7

Ejemplo:

X1
B

A
X4
X2

X6

X3X9

X5

X8
X10

C

D

NODOS
y
ARCOS O ARISTAS

X7

NODOS
V = { A , B ,C , D }

ARISTAS
A = { (A,B) , (A,C) , (A,D) , (B,A) , (B,D) , (C,A) , (C,D) , (D,A) , (D,B) , (D,C)}
:

ó Arcos = A={x1,x2,x3,x4,x5,x6,x7,x8,x9,x10}

Matematicas Discretas Daniel A. Quinto Pazce

8

Grafos no Dirigidos: Cuando

todas las

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

G:
1

2

3

4

Matematicas Discretas Daniel A. Quinto Pazce

9

G’:
a

c

G:

b

d

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

G:

Matematicas Discretas Daniel A. Quinto Pazce

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


Matematicas Discretas Daniel A. Quinto Pazce

11

Ejemplo:

Conjunto de Vértices Sucesores




(B) = {C, D}

5

Pr opiedades

Conjunto de Vértices Predecesores

 d(X
i 1

i

) 1

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

Matematicas Discretas Daniel A. Quinto Pazce

12

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

d  ( Xi ) |   ( Xi ) |
Grado Exterior : Número de aristas que salen

d  ( Xi ) |   ( Xi ) |
Grado de un Vértice: Número de arcos que inciden en él.

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 |
Matematicas Discretas Daniel A. Quinto Pazce

13Ejemplo:

d  ( Xi )
d  ( X 1 )=3

d  ( Xi )

d (Xi)
d ( X1)

d  ( X 2 )=2
d  ( X 3 )=2

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

d(X 2 )

=6

d(X3)

=3

d  ( X 4)=1

d  (X 4)

d(X 4 )

=4

=3

Teorema de Euler

=5

d * ( X i )  loop

propiedades  d(x i )  18, suma par
i 1

Max ( | d  Xi | )  | V | 1, Max ( | d  Xi |)  | V |  1Matematicas Discretas Daniel A. Quinto Pazce

14

Teorema:

4

 d ( Xi)  2( A)

verificando

i 1

Salen
2,3,4
1,4
1,4
2

18  2(9)
18  18 _ cumple
Ejercicio:

entran
2,3
2,2,4
1
1,2,3

Dada la tabla encontrar el grafo

d  ( Xi )
d  ( X1)

d  (X 2)

=2
=2

d  ( Xi )
d  ( X1)
d  (X 2)

d (Xi)
=2
=2

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

d (...