Ingeniería de Sistemas y Computación UNDAC

TEORIA DE GRAFOS

1. DEFINICIONES BÁSICAS

Un grafo G es un par (V,E) donde V es un conjunto (llamado conjunto de vértices) y E un

subconjunto de VxV (conjunto de aristas).
Gráficamente representaremos los vértices por puntos y las aristas por líneas que los
unen.
Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente 2
vértices.
Llamaremos orden de un grafo a su número de vértices, |V|.

Si |V| es finito se dice que el grafo es finito. En este curso estudiaremos los grafos
finitos. También supondremos, a no ser que se diga lo contrario, que entre dos vértices
hay, como mucho, una arista y que toda arista une dos vértices distintos. Ademas en la
presente secion se tratara el caso de grafos NO DIRIGIDOS.

Aristas

Si la arista carece de dirección se denota indistintamente {a,b} o {b,a}, siendo a y b

los vértices que une.

Si {a,b} es una arista, a los vértices a y b se les llama sus extremos.

Vértices

Dos vértices v, w se dice que son adyacentes’ si {v,w}∈A (o sea, si existe una arista
entre ellos)

Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice

que un vértice es ‘par’ o ‘impar’ según lo sea su grado.

Caminos

Sean x, y ∈ V, se dice que hay un camino en G de x a y si existe una sucesión finita no

vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso
- x e y se llaman los extremos del camino
- El número de aristas del camino se llama la longitud del camino.
- Si los vértices no se repiten el camino se dice propio o simple.
- Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre
ellos.
- Cuando los dos extremos de un camino son iguales, el camino se llama circuito o
camino cerrado.
- Llamaremos ciclo a un circuito simple

Teoría de la computación – Sesión 1-2 1

Ingeniería de Sistemas y Computación UNDAC

- Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos.

Todo vértice es accesible respecto a si mismo

Ejemplos de Grafos

1.- Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k
lo llamaremos k-regular.
Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular
y el tercero no es regular

2.- Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos
disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo
conjunto

Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es

3.- Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo
completo con n vértices se denota Kn.
A continuación pueden verse los dibujos de K3, K4, K5 y K6

Todo grafo completo es regular porque cada vértice tiene grado |V|-1 al estar
conectado con todos los otros vértices.

Un grafo regular no tiene por qué ser completo.

Teoría de la computación – Sesión 1-2 2

Ingeniería de Sistemas y Computación UNDAC

4.- Un grafo bipartido regular se denota Km,n donde m, n es el grado de cada

conjunto disjunto de vértices.

A continuación ponemos los dibujos de K1,2, K3,3, y K2,5

Proposición.- La suma de los grados de los vértices es igual al doble del número de
aristas

Demostración
Al realizar la suma de los grados de todos los vértices, como cada arista tiene 2
extremos se cuenta exactamente 2 veces. Por tanto la suma de los grados de los
vértices es igual al doble del número de aristas

2. MATRIZ DE ADYACENCIA DE UN GRAFO

Sea G un grafo de orden n. Llamaremos matriz de DG\DFHQFLD de G a la matriz nxn que

llamaremos A = (aij) donde aij = 1 si {i,j}∈A, es decir si el Vi esta conectado
directamente con Vj y aij = 0 en otro caso.

La matriz de adyacencia siempre es simétrica porque aij = aji

Ejemplo:

v1 v2 v3 v4 v5
v1 0 1 1 0 0 v1 v2
v2 1 0 1 1 0
v3 1 1 0 1 1
v4 0 1 1 0 0 v3 v4
v5 0 0 1 0 0 v5

Definición.- Un grafo G se dice conexo si cada par de vértices está unido al menos
por un camino.

3. GRAFOS EULERIANOS Y HAMILTONIANOS

Grafos eulerianos

Llamaremos camino euleriano a un camino que contiene a todas las aristas del grafo,
apareciendo cada una exactamente una vez.

Un ciclo euleriano es un camino euleriano que comienza y acaba en el mismo vértice.

Teoría de la computación – Sesión 1-2 3

Ingeniería de Sistemas y Computación UNDAC

Definición.- Un grafo que admite un ciclo euleriano diremos que es un grafo

euleriano.

Ejemplo:
1 2
1) El primero no tiene ciclos ni caminos euleriano,
8 5 3 El segundo tiene ciclo euleriano

6 4

Teorema.- Un grafo conexo G=(V,A) es euleriano ⇔ todo vértice tiene grado par.

Proposición.- Un grafo conexo tiene un camino abierto euleriano ⇔ tiene exactamente

dos vértices de grado impar.

Demostración
Añadimos un nuevo vértice junto con dos aristas que lo unan a los dos vértices que
tenían grado impar. Ahora estos vértices, al haberles añadido una arista a cada uno,
tienen grado par y el nuevo vértice tiene grado 2, por tanto, todos los vértices son
de grado par. Por el teorema anterior, tendremos un ciclo euleriano. Si en dicho ciclo
quitamos ahora el vértice y las dos aristas que habíamos añadido, obtendremos un
camino abierto que contiene exactamente una vez a cada arista de nuestro grafo
original.

Caminos hamiltonianos
Un camino hamiltoniano es un camino que recorre todos los vértices de un grafo sin
pasar dos veces por el mismo vértice. Si el camino es cerrado se dice un ciclo
hamiltoniano
Un grafo G se dice hamiltoniano si tiene un ciclo hamiltoniano.

Nota.- A diferencia de los grafos eulerianos, no hay una caracterización de cuando un

grafo tiene un ciclo o un camino hamiltoniano

Teorema.- Si un grafo es conexo con |V|≥3 y para cada par de vértices la suma de
sus grados es mayor o igual que el número de vértices entonces es hamiltoniano.

Teoría de la computación – Sesión 1-2 4

Ingeniería de Sistemas y Computación UNDAC

GRAFOS DIRIGIDOS

♦ Existen dos teorías de grafos paralelas, la de grafos dirigidos y la

de grafos no dirigidos.

♦ Un grafo dirigido o digrafo G se define como un par (V, A)

donde V es un conjunto de elementos, y A es una relación
binaria definida sobre V. Los elementos de V se denominan
nodos o vértices, y los elementos de A arcos. Dado un arco (x,y)
de A, se dice que x es el origen e y el destino del arco.

Ejemplo:
V= { v1, v2, v3, v4}
A= {(v1,v2), (v2,v1), (v3,v2), (v3,v3) }

Cada par (x, y) de A es un par ordenado (por ser A una relación)

y es esto lo que determina que el grafo sea dirigido (cada arco
tiene un sentido).

Teoría de la computación – Sesión 1-2 5

Ingeniería de Sistemas y Computación UNDAC

♦ Si el par (x,y) no fuera considerado ordenado el grafo sería un

grafo no dirigido. En este último caso el par (x,y) es igual al
par (y,x). Si G es un grafo no dirigido los elementos de A se
denominan aristas.

2.1. Representación gráfica de grafos

♦ Para representar gráficamente un digrafo generalmente se

utilizan círculos para los vértices y flechas para los arcos.

G1 = (V, A) grafo dirigido

V= { v1, v2, v3, v4, v5}
A= { (v1,v2), (v2,v1), (v2,v3), (v2,v5), (v3,v3), (v3,v5) }

♦ En un grafo no dirigido los vértices también se representan con

círculos, pero la aristas se representan con segmentos.

G2 = (V, A) grafo no dirigido

V= { v1, v2, v3, v4 }
A= { (v1,v2), (v2,v3), (v2,v4), (v3,v4)}

En G2 no podemos tener como elemento de A la arista (v2,v1)

dado que es igual a la arista (v1,v2). Si la agregamos, A tendría
elementos repetidos y esto no está permitido porque A es un
conjunto.

Teoría de la computación – Sesión 1-2 6

Ingeniería de Sistemas y Computación UNDAC

♦ Los vértices y arcos (o aristas) de un grafo pueden ser elementos

con información adicional unida a ellos. Tales grafos se llaman
grafos etiquetados o ponderados. Por ejemplo:

2.2. Definiciones básicas en grafos dirigidos

♦ Se exponen a continuación una serie de conceptos definidos

sobre digrafos. Para ejemplificar los mismos usaremos el
siguiente grafo:

♦ Bucle: Un bucle es un arco de la forma (x, x), es decir es un

arco que tiene por origen y destino al mismo vértice. Ej: En el
grafo dado existe un bucle: (v7,v7).

♦ Sucesor o adyacente: Se dice que el nodo y es sucesor o

adyacente del nodo x si existe un arco que tenga por origen a x
y por destino a y, es decir si el arco (x, y) ∈ A. Al conjunto de
nodos sucesores o adyacentes de x lo denotaremos con S(x). Ej:
S(v4) ={ v3, v5 }, S(v2) = { v2, v3, v4, v5} y S(v3) = S(v6) = ∅

Teoría de la computación – Sesión 1-2 7

Ingeniería de Sistemas y Computación UNDAC

♦ Predecesor: Se dice que el nodo y es predecesor del nodo x si

existe un arco que tenga por origen a y y por destino a x, es
decir si el arco (y, x)∈ A. Al conjunto de nodos predecesores de x
lo denotaremos con P(x). Ej: P(v4) = { v1, v2 }, P(v7) ={ v7 }

Nótese que en el caso de v7 , el mismo v7 forma parte de su

conjunto de predecesores y de su conjunto de sucesores. Esto se
debe a que existe un bucle en v7.

♦ Grado:

• Grado de entrada del nodo x:

g-(x) =| P(x) |

• Grado de salida del nodo x:

g+(x) =| S(x) |

Ej:
g-(v4) = | {v1, v2 } | = 2
g+(v4) = | { v3, v5 } | = 2
g-(v2) = | { v1 } | = 1
g+(v2) = | { v3, v4, v5} | = 3

• En un grafo no dirigido, el grado de un nodo es el número de

aristas que inciden en dicho nodo.

♦ Vértice aislado: Se dice que un vértice x es aislado si g+(x) =

g-(x) = 0. Ej: En el grafo anterior el único vértice aislado es v6:
g+(v6) = g-(v6) = |∅| = 0. El vértice v7 no puede ser considerado
como aislado, dado que al tener un bucle su grado de entrada y
salida es 1.

Teoría de la computación – Sesión 1-2 8

Ingeniería de Sistemas y Computación UNDAC

♦ Camino: Informalmente decimos que existe un camino del

vértice x al vértice y, si podemos llegar de x a y siguiendo los
arcos y en el sentido en que estos están. Ej: Existe un camino de
v1 a v5 siguiendo los arcos (v1,v2), (v2,v4) y (v4,v5). También existe
otro camino entre los mismos vértices siguiendo los arcos (v1,v4)
y (v4,v5).

Formalmente, dado un grafo G = (V,A) decimos que existe un

camino del vértice x al vértice y, si existe una secuencia <v0,
v1,.....,vn-1> tal que:

a) v0=x ∧ vn-1=y

b) (vi-1, vi) ∈ A con i= 1...n-1

♦ La longitud del camino es igual a la cantidad de arcos que lo

forman; en la definición anterior sería n-1. Ej: Existe un camino
de v1 a v5 dado que la secuencia <v1, v2, v4, v5> cumple con la
definición. La longitud de este camino es 3.

Como caso especial la secuencia <v> es un camino de longitud

cero. Esto nos dice que siempre existe un camino de longitud
cero entre un nodo y sí mismo.

♦ Un camino se dice simple o elemental si no pasa dos veces por

un mismo vértice.

♦ Un ciclo es un camino simple de longitud mayor que 1, en donde

coinciden los vértices primero y último. Ej: El camino <v1, v2, v4,
v5, v4, v5, v1> no es un ciclo dado que no es simple. La secuencia
<v1, v2, v4, v5, v1> si es un ciclo y su longitud es 4.

Teoría de la computación – Sesión 1-2 9

Ingeniería de Sistemas y Computación UNDAC

♦ Cadena: Informalmente decimos que existe una cadena del

vértice x al vértice y, si podemos llegar de x a y siguiendo los
arcos pero sin tener en cuenta el sentido de los mismos. Ej: <v1,
v2, v4, v5>, <v2, v1, v4>, <v3, v2, v4, v5>, <v2, v2>.

Formalmente, dado un grafo G = (V,A) decimos que existe una

cadena del vértice x al vértice y, si existe una secuencia v0,
v1,.....,vn-1 tal que:

a) v0=x ∧ vn-1=y

b) (vi-1, vi) ∈ A o (vi, vi-1) ∈ A con i= 1...n-1

♦ La longitud de la cadena es igual a la cantidad de arcos que la

forman; en la definición anterior sería n-1.

♦ Una cadena se dice simple si no pasa dos veces por un mismo

vértice.

♦ Un circuito es una cadena simple de longitud mayor que 1, en

donde coinciden los vértices primero y último. Ej: <v5, v2, v4, v5>,
<v1, v2, v4, v5, v1>, <v3, v4, v2, v3>.

♦ De las definiciones dadas valide que:

• Todo camino es una cadena, pero no toda cadena es un

camino.

• Todo ciclo es un circuito, pero no todo circuito es un ciclo.

• Existe una cadena de x a y si y sólo si existe una cadena de y

a x.

Teoría de la computación – Sesión 1-2 10

Ingeniería de Sistemas y Computación UNDAC

♦ Conectividad

• Un grafo se dice conectado si existe una cadena entre

cualquier par de vértices del grafo.

• Un grafo se dice fuertemente conectado si existe un

camino entre cualquier par de vértices del grafo.

• Nuevamente a partir de esta definiciones podemos sacar

alguna conclusiones:

− Si G es un grafo fuertemente conectado entonces G es

un grafo conectado (el recíproco no se da).
− Si G no es un grafo conectado entonces G no es un
grafo fuertemente conectado.
− Si G tiene vértices aislados entonces G no es
conectado.

Ej:

• G1: el grafo que hemos usado en los ejemplos anteriores no

es un grafo conectado, y por lo tanto tampoco es
fuertemente conectado.

• G2:

Teoría de la computación – Sesión 1-2 11

Ingeniería de Sistemas y Computación UNDAC

• G3:

• G4:

Teoría de la computación – Sesión 1-2 12