MATEMÁTICAS DISCRETAS

UNIDAD IV - GRAFOS –

DEFINICION: Un grafo no dirigido G es de la forma : (V,L) donde V es un conjunto de

vértices (nodos), L es un conjunto de aristas (lados) y cada lL está asociada a un par no
ordenado de vértices.
Ejemplo: Sea G=(V,L) donde V={Tehuacán, Puebla, Tlaxcala}
L={(Tehuacán,Puebla),(Puebla,Tlaxcala),(Tlaxcala, Tehuacán)}
Gráficamente: Tehuacán Tlaxcala

(GRAFO NO DIRIGIDO)

Puebla

DEFINICION: Un grafo dirigido G es de la forma : (V,L) donde V es un conjunto de

vértices (nodos), L es un conjunto de aristas (lados) y cada lL está asociada a un par
ordenado de vértices.
Ejemplo: Sea G=(V,L) donde V={Tehuacán, Puebla, Tlaxcala}
L={(Tehuacán,Puebla),(Puebla,Tlaxcala),(Tlaxcala, Tehuacán)}

Gráficamente: Tehuacán Tlaxcala

Puebla

DEFINICIÓN: Sean x,y vértices (no necesariamente distintos) de un grafo no dirigido

G=(V,L). Un Camino x-y en G es una sucesión alterna finita: x=x0,l1,x1,l2,x2,,......,ln,xn=y de
vértices y aristas de G que comienzan en el vértice x y terminan en el vértice y, y que
contiene n aristas de la forma li=(xi,xi+1). La longitud de un camino eds n, donde n es el
número de aristas que hay en el camino. Cualquier camino x-y donde x=y (n>1) es un
camino cerrado y, en caso contrario es un camino abierto.
Ejemplo:
Sea G el siguiente grafo no dirigido:

a l2 d l4 e a) a,l3,c,l7,e,l4,d es un camino de longitud 3.

además es un camino abierto.
l1 l5 b) a,l3,c,l6,b,l1,a,l2,d es un camino de
l3
longitud 4. Además es un camino abierto
l7 c) a,l3,c,l6,b,l1,a es un camino de longitud 3.
b f Además es un camino cerrado
l6 c

LIC. IRENE GARCIA ORTEGA 1

 MATEMÁTICAS DISCRETAS

DEFINICIÓN: Consideremos un camino x-y en ungrafo no dirigido G=(V,L).

a) Si no se repite ninguna arista en el camino x-y, entonces el camino es un recorrido
x-y. Un recorrido cerrado es un circuito.
b) Cuando ningún vértice del camino x-y se presenta más de una vez, el camino es un
camino simple.El término ciclo se usa para describir un camino simple cerrado x-x.

Del ejemplo anterior a) es un camino simple y es un recorrido a-d.

Del ejemplo anterior b) es un recorrido y no es un camino simple a-d.
Del ejemplo anterior c) es un circuito y es un ciclo a-d.

Tarea: Sea G el grafo:

b e f

g
c d

Determinar:
1. Un camino de b-f que no sea un recorrido.
2. Un recorrido de a-d que no sea un camino simple.
3. Un camino simple de a-g Un camino cerrado a-a que no sea un circuito.
4. Un camino de a-a que no sea un ciclo.
5. un ciclo de a-a.
6. ¿Cuántos caminos simples existen de a-f ?

DEFINICION: Un grafo G=(V,L) es un multigrafo, si existe a,b  V ab, co 2 o más

aristas de la forma (a,b).

Ejemplo: a b
a b

Lados paralelos
Lados paralelos
c d
c d

(Grafo no-dirigido) (Grafo dirigido)

DEFINICIÓN: Un grafo que no tiene lazos ni lados paralelos recibe el nombre de grafo
simple.

LIC. IRENE GARCIA ORTEGA 2

 MATEMÁTICAS DISCRETAS

DEFINICIÓN: Se dice que un lado l=(v,w) de un grafo dirigido o no dirigido es incidente

en v y w. Se dice que los vértices v y w son incidentes en l, y también que son vértices
adyacentes.

DEFINICIÓN: Sea G=(V,L) un grafo o multigrafo no dirigido, para cualquier vértice de V

en G, el grado o valencia de v, que se denota como grad(v) es el número de aristas que son
incidentes en v. En este caso un lazo en un vértice v se considera como 2 aristas incidentes
en v.

TEOREMA: Si G=(V,L) es un grafo o multigrafo no dirigido entonces  grad(v)=2 L .

vV

DEFINICIÓN: Sea G=(V,L) un grafo no- dirigido decimos que G es conexo si existe un
camino simple entre cualesquiera dos vértices distintos de G.
Un grafo que no es conexo es Disconexo.
a b a d

c d b c e d

Grafo conexo Grafo disconexo

DEFINICIÓN: Se dice que G es un grafo Bipartido si G=(V,L) es un grafo tal que V=v1v2
y v1  v2 = y además todo lado lL es incidente a un vértice de v1 y a uno de v2.

Ejemplo: c

a
d Donde:
b v1={a,b}
v2={c,d,e}
e

DEFINICION: Se dice que Km,n es un grafo Bipartido completo de m+n vértices si es

Bipartido (sin lados paralelos) tal que: v1=m y v2=n, y todo vértice de v1 es adyacente
a todo vértice de v2.

EJEMPLO: Hallar el grafo bipartido completo K2,3.

En este caso m=2, n=3.
c
v1={a,b}
a v2={c,d,e}
d v1=2
b v2=3
e

LIC. IRENE GARCIA ORTEGA 3

 MATEMÁTICAS DISCRETAS

DEFINICION: Si G=(V,L) es un grafo (dirigido o no), entonces G1=(v1,L1) es un subgrafo

de G si   v1  v y L1L, donde cada arista de L es incidente con algún par de vértices
de v1.

Ejemplo: 1 2
1 2

G1 es un subgrafo de G

3 4 3

G G1

DEFINICIÓN: Sea V un conjunto de n vértices, el grafo completo sobre V, que se denota

con Kn es un grafo no dirigido sin lazos, tal que para todos a,b  V a  b existe una arista
(a,b).

Ejemplos:

K1 K2
K3 K4

DEFINICIÓN: sea g un grafo o multigrafo no dirigido, sin vértices aislados, entonces G

tiene un circuito Euleriano si existe un circuito en G que recorre cada arista del grafo
exactamente una vez.
Si existe un recorrido abierto de a a b en G que recorre cada arista de G
exactamente una vez este recorrido se llamará RECORRIDO EULERIANO.

TEOREMA: UN grafo G tiene un Circuito de Euler si y sólo si es conexo y todos sus

vértices tienen valencia par.

TEOREMA: Un grafo tiene un camino de v a w (v  w) que contiene todos los lados y

vértices , si y sólo si es conexo y v y w son los únicos vértices de G con valencia impar.

EJEMPLO: Establecer circuitos de Euler para cada uno de los siguientes circuitos:

d f
b

c e
a g

i j
h

LIC. IRENE GARCIA ORTEGA 4

 MATEMÁTICAS DISCRETAS

d f
b

a c e
g

i j
h

DEFINICIÓN: SI G =(V,L) un grafo o multigrafo con V3, decimos que G tiene un

Ciclo Hamiltoniano si existe un ciclo en G que contenga cada vértice de G.
Un camino hamiltoniano es un camino simple (y no un ciclo) de G que contiene todos los
vértices.

EJEMPLO: Determinar si el siguiente grafo tiene un ciclo hamiltoniano o un camino

hamiltoniano.
a

b
c

d e

REPRESENTACIÓN DE GRAFOS.
Existen algunas maneras formales de representar los grafos por medio de una computadora.
1) LISTAS DE ADYACENCIA. En este tipo de representación se utiliza un arreglo de
apuntadores para representar a los vértices adyacentes de un grafo.
Ejemplo: Sea G=(V,L) el sgte. Grafo:
1 2

3 4

La lista de adyacencia sería:

2 3 4
1
2 1 4

3 1 4
4 1 2 3
LIC. IRENE GARCIA ORTEGA 5
 MATEMÁTICAS DISCRETAS

2) MATRIZ DE ADYACENCIA.

En esta representación asumimos que los vértices son numerados de 1 a V (en forma
arbitraria ). La representación Matriz de adyacencia de un grafo G=(V,L) es una matriz de
dimensión VxV en donde:

1 si (i,j)  L
MA(i,j)=
0 en caso contrario.

Ejemplo: Sea G=(V,L), el grafo siguiente:

1 2

3 4

La Matriz de Adyacencia que representa a este grafo es:

1 2 3 4

1 0 1 1 1 Para obtener el grado de los vértices

se suma la fila a la columna a menos
MA = 2 1 0 0 1 que sea un vértice (x,x) en cuyo
3 1 0 0 1 caso se debe agregar dos.
4 1 1 1 0

NOTAS: Una matriz de Adyacencia

 Permite representar lazos.
 No permite representar lados paralelo ( No permite representar multigrafos).
 Permite obtener la valencia de los vértices, sumando la fila o columna
correspondiente.
 No es un método muy eficaz de representar un grafo ya que la matriz es simétrica
con respecto a la diagonal, por lo tanto la información, exceptuando la contenida en
la diagonal, aparece 2 veces.
 Nos permite determinar si existen caminos de longitud n del vértice x al vértice y
cuántos caminos existen, lo cual esta representado en la matriz MAn, es decir obtener
la potencia n de la matriz de adyacencia. Y el valor de MAn (i,j) indicara cuantos
caminos de longitid n existen del vértice i al vértice j.
 La matriz de Adyacencia requiere O(V2) de memoria indepemndientemente del
número de lados.

Por lo tanto si el número de vértices es exageradamente mayor al número de lados entonces

esta representación no es la indicada.

LIC. IRENE GARCIA ORTEGA 6

 MATEMÁTICAS DISCRETAS

MATRIZ DE INCIDENCIA.

Otra representación útil de un grafo es conocida como MATRIZ DE INCIDENCIA. En una

matriz de Incidencia se le asignan a las filas las marcas correspondientes a los vértices, y a
las columnas las marcas correspondientes a las aristas, en donde la matriz se define de la
siguiente manera:

Una matriz de incidencia para un multigrafo no-dirigido G = (V,L) , es una matriz de

dimensión VXL, donde :

1 Si el lado j es incidente al vértice i.

MI (i,j) =
0 Si el lado j no es incidente al vértice i.

Ejemplo: Determinar la matriz de incidencia para el grafo siguiente :

a b

d c

paralelos

L1 L2 L3 L4 L5 L6 L7
l1 l2 l6
l3 l4 l5 l7 lazo
a 1 1 1 0 1 1 0
MA = b 1 1 0 1 0 0 0
c 0 0 1 1 0 0 0
d 0 0 0 0 1 1 1

NOTAS:
 Una matriz de incidencia permite representar lazos y lados paralelos simultáneamente.
 Si i es un vértice y no hay lazos en i , entonces la suma de la fila i es la valencia o grado del vértice i.
 Si i es un vértice y hay lazos en él , entonces la valencia o grado del vértice i es la suna de la fila i,
menos 1 más 2 * la cantidad de lazos en i.

Una matriz de Incidencia para un multigrafo dirigido G=(V,L), es u8na matriz de dimensión
VXL, donde :

1 Si Lj sale de i
MI (i,j) = -1 Si Lj llega a i
0 en otro caso.

LIC. IRENE GARCIA ORTEGA 7

 MATEMÁTICAS DISCRETAS

Ejemplo: Halla la matriz de incidencia para le siguiente grafo:

a b

d c

L1 L2 L3 L4 L5 L6
l1 l2 l3 l4 l5 l6
a 1 -1 -1 0 1 1
paralelos
MA = b -1 1 0 1 0 0
c 0 0 1 -1 0 0
d 0 0 0 0 -1 -1

DEFINICIÓN: Un grafo (o multigrafo) G es plano si podemos dibujar G en el plano de

nodo que sus aristas se intercepten sólo en los vértices de G. Este dibujo de G se conoce
como una INMERSIÓN DE G EN EL PLANO.

Ejemplos:

K1 Plano: K2 Plano: K3 Plano : K4 Plano:

K2,2 plano:

Si se representa en un plano un grafo plano y conexo, queda dividido en regiones

continuas llamadas caras. Una cara se caracteriza por el circuito que forma su frontera.

LIC. IRENE GARCIA ORTEGA 8

 MATEMÁTICAS DISCRETAS

GRAFOS PONDERADOS

Un grafo ponderado o con peso es un grafo en el cual hay datos asociados a sus lados. El
valor w(i,j) asociado con el lado (i,j) se llama ponderación o peso de (i,j). Por ejemplo si se
interpretan las ciudades como vértices y los caminos entre ellas como lados, al asignarle
longitud a los caminos resulta un grafo ponderado. Con frecuencia los pesos se utilizan para
representar costos. Po ejemplo, si los vértices reprsentan ciudads y los lados, caminos por
construir, el peso de un lado podría representar el costo de construir el camino que une a dos
ciudades.

El peso o ponderación de un grafo es la suma de los pesos de sus lados. Frecuentemente el

peso de un camino se conoce como longitud del camino. Con frecuencia se desea encontrar
en grafos ponderados, el camino más corto entre doas vértices dados. El algoritmo de
Dijkstra resuelve eficazmente este problema.

ALGORITMO DE DIJKSTRA

Porposito: Obtener la ruta más cortas para ir de un vértice especifico s a un vértice

específico t.

DESCRIPCIÓN:

1. (INICIALIZACIÓN DE ETIQUETAS).
Sea d(s)=0 y P={s}
Donde P es un conjunto de nodos o vértices permanentes
Sea d(x)=∞ ∀ x ≠ s, donde x es un vértice.
Sea a(x)=x; esta etiqueta indicará el predecesor del nodo x Para todo x vértice
Sea p=s; ea T= el conjunto de vértices en el grafo excluyendo a s.
2. (ACTUALIZACION DE ETIQUETAS)
∀ x vértice al que se puede llegar directamente de p y que tenga etiqueta de
temporal, actualizar las etiquetas de acuerdo a:
d(x)= min { d(x), d(p) + d(p,x)}
Si d(x) se modificó hacer a(x)=p;

Sea x* tal que d(x*)==∞, PARAR: ” No existe camino del vértice s al t ”

En otro caso marcar la etiqueta x* como permanente y eliminarlo de T.
3. (CRITERIO DE PARO).
Si p==t, PARAR, “d(x) es la longitud del camino más corto para ir de s a t”, y
el camino es : t, a(t), a(a(t)), …. , s en sentido opuesto.
En otro caso ir al paso 2.

LIC. IRENE GARCIA ORTEGA 9

 MATEMÁTICAS DISCRETAS

Ejemplo: Sea G el grafo siguiente, aplique el algoritmo de Dijkstra para hallar la ruta más
corta del D.F. a Tehuacán.

3 6 9
2 IROLO 9
EL REY JALAPA
2 1.5 2 4

3 7.5
2 TEOTIHUACAN 5
1 7 12
D.F SN. LORENZO VERACRUZ
0.5
2.5 3
3.5
3
4 10
3 METEPEC CORDOBA
3
10
3.5 6

5 8 11
CUAUTLA 3 PUEBLA TEHUACAN
4

Si (vértice inicial) s = 1 y (vértice final) t = 11

Aplicando el algoritmo tenemos:

d(x) Vértices 1 2 3 4 5 6 7 8 9 10 11 12 x*
1)Inicialización
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
de etiquetas
2 2 2.5 3 ∞ ∞ ∞ ∞ ∞ ∞ ∞ x*=2
2) ACTUALIZACIÓN

2 2.5 3 5 ∞ ∞ ∞ ∞ ∞ ∞ x*=3
DE ETIQUETAS

2.5 3 3.5 ∞ ∞ ∞ ∞ ∞ ∞ x*=4

3 3.5 5.5 ∞ ∞ ∞ ∞ ∞ x*=5
3.5 5.5 6 ∞ ∞ ∞ ∞ x*=6
5.5 6 12.5 ∞ ∞ ∞ x*=7
6 12.5 ∞ ∞ ∞ x*=8
12.5 ∞ 10 ∞ x*=11

a(x)
Vértices 1 2 3 4 5 6 7 8 9 10 11 12
1)Inicialización
1 2 3 4 5 6 7 8 9 10 11 12
de etiquetas
1 1 1 1 1
ACTUALI

2 4 5 6 8
ETIQUET
ZACIÓN
DE

AS
2)

LIC. IRENE GARCIA ORTEGA 10

 MATEMÁTICAS DISCRETAS

El camino es t,a(t), a(a(t)),..s

Sustituyendon tenemos:
11,8,5,1 en sentido opuesto es : 1,5,8,11

LIC. IRENE GARCIA ORTEGA 11