07 GRAFOS _FADU_2015_parte_I

TEORÍA DE
GRAFOS
MATEMÁTICA II
CÁTEDRA SANTA MARIA

TEORÍA DE GRAFOS

TEORÍA
INTERDISCIPLINARIA

CIENCIAS
SOCIALES

FÍSICA

QUÍMICA
LINGÜISTICA

AMPLIA GAMA
DE APLICACIONES

INGENIERÍA

INFORMÁTICA
COMUNICACIONES

ARQUITECTURA

GRAFOS

SE UTILIZAN PARA

MODELAR
SITUACIONES

MODELO:
ES UNA

REPRESENTACION SIMPLIFICADA
DEBE TENER
EN CUENTA

CARACTERISTICAS
RELEVANTES

DEBE IGNORAR

DETALLESINNECESARIOS

ALGUNAS APLICACIONES

RED DE PLANIFICACIÓN

Nos preguntamos si es posible conectar estas tres casa con las tres
tomas de modo que ninguna de las conexiones se cruce con otra
conexión

ALGUNAS APLICACIONES
PUENTES DE KONIGSBERG (EULER 1736)
Nos pregunta si es posible dar un paseo y regresar al punto de
partida cruzando cada puente UNA SOLA VEZ

Los 7 puentes

reemplazando la tierra
porvértices y los
puentes por aristas

La pregunta es entonces ¿existe un camino cerrado que
contenga exactamente cada una de las aristas?

DEFINICION FORMAL de GRAFO
Un grafo es una terna G = ( V ; A ;  )

CONJUNTO
DE VERTICES
V≠

CONJUNTO
DE ARISTAS

FUNCION DE
INCIDENCIA
 : A  V(2)

V(2) es el conjunto formado por
subconjuntos de 1 o 2 elementos de V,
que son los extremos de la aristaEJEMPLO

Sea el grafo G =( V, A,  ) siendo los conjuntos:
V = { v 1 , v 2 , v3 , v 4 , v 5 }

A = { a 1 , a 2 , a 3 , a4 , a 5 }

Y la función de incidencia:

 (a1)={v1, v2} ,  (a2) ={v3} ,

 (a3)={v4,v2} ,  (a4)={v1,v3 } ,  (a5)={ v1, v2}
a5

NO EXISTE
un ÚNICO
DIAGRAMA

Que represente
un grafo

a1

a3

v2

v1

v4
a2

a4

v3

v5

DEFINICIONES
VERTICES ADYACENTES
VERTICE AISLADO
ARISTASADYACENTES

GRAFO ASOCIADO A
UN DIGRAFO
SUBGRAFO

ARISTAS PARALELAS

GRAFOS CONEXOS

BUCLES O LAZOS

CONEXIDAD EN DIGRAFOS

ARISTAS INCIDENTES
EN UN VERTICE

CAMINOS ESPECIALES

GRAFO SIMPLE

GRAFOS COMPLETOS

CAMINOS Y CICLOS

GRAFOS BIPARTITOS
COMPLETOS
GRAFOS PLANOS

DIGRAFOS

GRAFO DUAL

GRADO EN UN DIGRAFO

GRAFOS POLIGONALES

GRADO O VALENCIA

vi es adyacente a vj 
 ak  A tal que  (ak) = { vi ,vj}

VERTICES ADYACENTES

Ejemplo:
Que son vértices que están
unidos por alguna arista

a5
a1

a3

v2

v1

v4
a2

a4
v3

v5

v2 es ADYACENTE a v1 y a v4
pero no a v3

Es un vértice que no es adyacente
a ningún otro

VERTICE AISLADO
Ejemplo:
a5

a3

v2

a1
v1

v4
a2

a4
v3

v5

v5 es AISLADO

Son aristas que tienen un único
vértice en común

ARISTAS ADYACENTES
Ejemplo:
a5
a1

a3

v2

v1

v4

a3 ya1 son ADYACENTES

a2
a4
v3

v5

ya que el único vértice en
común entre ambas es v2

ai es paralela a ak   (ai) =  (ak)

ARISTAS PARALELAS

Ejemplo:

Que son aristas
comprendidas entre los
mismos vértices

a5
a1

a3

v2

v1

v4

a5 y a1 SON PARALELAS ya

a2
a4
v3

v5

que ambas están
comprendidas entre los
vértices v1 y v2

Son aristas con ambos extremos
en el mismo vértice

BUCLES O LAZOSEjemplo:

a5
a1

a3

v2

v1

v4
a2

a4
v3

v5

a2 es BUCLE pues ambos extremos
de ella es el vértice v3

ARISTAS INCIDENTES
EN UN VERTICE

Son las aristas que
tienen a dicho vértice por extremo

Ejemplo:
a5
a1

a3

v2

v1

v4
a2

a4
v3

v5

Las aristas a1, a3 y a5
son INCIDENTES en el
vértice v2

G es simple si y sólo si NO tiene
ARISTAS PARALELAS NI BUCLES

GRAFO SIMPLE

a5

Ejemplo:

a1

a3

v2v1

v4

a2
a4

Este grafo NO es SIMPLE

v3

v5

a4
2

3

a6
1

a3

a5

a1

4
a2

5

Este grafo SI es SIMPLE

GRADO o VALENCIA DE UN VERTICE

g(vi) = Es la cantidad de aristas incidentes en un vértice
Nota: los bucles se cuentan doblemente

Los grados de
los vértices son:

Ejemplo:
a5
a1

a3

v2

v1

v4
a2

a4
v3

v5

g(v1)
g(v2)
g(v3)
g(v4)
g(v5)

=
=
=
=
=

3
3
3
1
0

PROPIEDAD
En todo grafose cumple que la suma de los grados de los vértices es
igual al doble de la cantidad de aristas
En símbolos:

 g(vi)= 2  A 
EJERCICIO
¿Cuál es la cantidad total de vértices de un grafo que tiene 2 vértices de
grado 4, uno de grado 3, 5 de grado 2 y el resto colgantes (de grado 1)
sabiendo que en total hay 12 aristas?

EJERCICIO
¿Cuál es la cantidad total de vértices de un grafo que tiene 2...