Teoría de Grafos

Definición 1. Un grafo G es una triada de objetos G D .V; A; f / formada por un conjunto no

vacío V cuyos elementos se denominan vértices, un conjunto A cuyos elementos son llamados
aristas y una aplicación f que a cada elemento x de A le asocia un par no-ordenado de vértices
fu; vg, esto es,
f .x/ D fu; vg:

Cuando los extremos de una arista coinciden, es decir, si f .x/ D fv; vg D fvg, diremos que
la arista es un lazo.
Si x 2 A y f .x/ D fu; vg, entonces decimos que u y v son los extremos de la arista x, o que la
arista x incide o tiene incidencias en u y en v; también se dice que u y v son vértices adyacentes
o que están conectados por la arista x.

Graficar el grafo G D .V; A; f /, donde V D fv1 ; v2 ; v3 ; v4 ; v5 g, A D fa; b; c; d; e; hg y f es

tal que f .a/ D fv1 ; v2 g, f .b/ D fv1 ; v3 g, f .c/ D fv1 ; v4 g, f .d / D fv4 ; v5 g, f .e/ D fv3 ; v4 g
y f .h/ D fv5 g.

Solución. La expresión f .a/ D fv1 ; v2 g significa que los vértices v1 y v2 están conectados
por la arista a; f .b/ D fv1 ; v3 g significa que v1 y v3 están conectados por la arista b, y así
sucesivamente. La función f .h/ D fv5 g indica que la arista h es un lazo sobre el vértice v5 . (Ver
figura)

v2
v3
a
b
e h
v1
c
d v5
v4

Ejercicio. Dados los conjuntos V D fv1 ; v2 ; v3 ; v4 ; v5 g, A D fa1 ; a2 ; a3 ; a4 ; a5 g, una aplica-

ción que produce el grafo G D .V; A; g/ viene dada por

Arista a1 a2 a3 a4 a5
[Link] / fv1 ; v3 g fv1 ; v4 g fv2 ; v5 g fv3 ; v2 g fv4 ; v5 g

1
Graficar el grafo G

Ejercicio. Dado el grafo G:

v1
1 v5 7
5
v6
v2
6
8
2
v4

3 v3 4

Determine la función de incidencia del grafo.

Definición 2. Sea v un vértice de un grafo G. El grado de v denotado por gr.v/ es el número de

aristas de G que inciden en v, en donde cada lazo que incide en v es contado dos veces.

El número de incidencia de una arista a en v es:

 0 si v no es un extremo de la arista a.

 1 si v es un extremo de la arista a y a no es un lazo.

 2 si v es un extremo de un lazo a.

Teorema 1. Sea G D .V; A; f / un grafo, donde V D fv1 ; v2 ; : : : ; vn g. Entonces

gr.v1 / C gr.v2 / C


C [Link] / D 2  .número de aristas de G/

Definición 3. Consideremos un grafo G:

.a/ Para u; v 2 V , la multiplicidad del par fu; vg es el número de aristas que tienen un extremo
en u y el otro extremo en v; se denota por m.u; v/.

.b/ Un vértice aislado en G es un vértice que tiene grado igual a cero.

.c/ Un vértice colgante en G es un vértice que tiene grado igual a 1.

Definición 4. Se dice que un grafo G es finito cuando los conjuntos V y A son finitos. Si G es
un grafo finito con n vértices y m aristas (m > 0), entonces:

2
 .a/ La matriz de incidencias de G es la matriz m  n, denotada por I.G/, cuya componente
ij es el número de veces que la arista ai incide en el vértice vj .

.b/ La matriz de adyacencia de G es la matriz cuadrada de orden n  n, denotada por Ad.G/,

cuya componente ij es la multiplicidad [Link] ; vj /.

Consideremos el grafo G:

a2
a1
v1 v2

a4
a6 a5 a3

v4 v3

Para construir la matriz de adyacencia, primero escribimos todos los vértices del grafo tanto
en la parte superior como en el lateral de la matriz. Luego, nos preguntamos: ¿cuántas aristas
conectan el vértice vi con el vértice vj ? La respuesta a esa pregunta es el valor que colocaremos
en la entrada correspondiente de la matriz.
Comencemos por el vértice v1 . ¿Cuántas aristas conectan a v1 con v1 ? Ninguna. Entonces la
primera entrada de la primera fila de la matriz es 0.
¿Cuántas aristas conectan a v1 con v2 ? En el grafo vemos que ambos vértices están conectados
por una arista, así que la segunda entrada de la primera fila es 1.
¿Cuántas aristas conectan a v1 con v3 ? 1.
¿Cuántas aristas conectan a v1 con v4 ? En el grafo vemos que 2 aristas conectan estos vértices,
por lo que introducimos ese valor en la matriz.
La primera fila de la matriz de adyacencia queda de la siguiente manera:

v1 v2 v3 v4
2 3
v1 0 1 1 2
v2
6 7
Ad.G/ D
6 7
6 7
v3 4 5
v4

3
 Repitiendo el procedimiento para el resto de las filas obtenemos la matriz de adyacencia del
grafo dado.
v1 v2 v3 v4
2 3
v1 0 1 1 2
v2
6 1 1 1 0 7
Ad.G/ D
6 7
1 1 0 0
6 7
v3 4 5
v4 2 0 0 0
Para construir la matriz de incidencia copiamos en la parte superior de la matriz todas las
aristas del grafo, mientras que en el lateral copiamos todos los vértices.
a1 a2 a3 a4 a5 a6
2 3
v1
v2
6 7
I.G/ D
6 7
6 7
v3 4 5
v4

Entonces nos preguntamos: ¿cuántas veces la arista ai entra en el vértice vj ? Por ejemplo:
¿Cuántas veces la arista a1 entra en el vértice v1 ? 1.
¿Cuántas veces la arista a2 entra en el vértice v1 ? 0.
¿Cuántas veces la arista a3 entra en el vértice v1 ? 0.
¿Cuántas veces la arista a4 entra en el vértice v1 ? 1.
¿Cuántas veces la arista a5 entra en el vértice v1 ? 1.
¿Cuántas veces la arista a6 entra en el vértice v1 ? 1.
Así, la primera fila de la matriz de incidencia queda como
a1 a2 a3 a4 a5 a6
2 3
v1 1 0 0 1 1 1
v2
6 7
I.G/ D
6 7
6 7
v3 4 5
v4

Ahora repetimos el procedimiento con el resto de las filas. Sólo observe que la arista a2 es
un lazo sobre el vértice v2 , de manera que a2 entra 2 veces en v2 . En general, el número de
incidencia de un lazo siempre es 2. Por lo tanto, la matriz de incidencia está dada por:
a1 a2 a3 a4 a5 a6
2 3
v1 1 0 0 1 1 1
v2
6 1 2 1 0 0 0 7
I.G/ D
6 7
0 0 1 1 0 0
6 7
v3 4 5
v4 0 0 0 0 1 1

Si sumamos las entradas de cada fila de la matriz de incidencia, entonces obtenemos el grado
de cada vértice. Así vemos que:

gr.v1 / D 1 C 0 C 0 C 1 C 1 C 1 D 4

4
 gr.v2 / D 1 C 2 C 1 C 0 C 0 C 0 D 4
gr.v3 / D 0 C 0 C 1 C 1 C 0 C 0 D 2
gr.v4 / D 0 C 0 C 0 C 0 C 1 C 1 D 2

Definición 5.

.a/ Un grafo G se denomina grafo simple si y sólo si no tiene lazos y entre cada par de vértices
distintos no hay más de una arista.

.b/ Un grafo que no es simple se denomina multigrafo.

.c/ Un grafo simple que tiene exactamente una arista entre cada par de vértices distintos se
llama grafo completo. Se denota por Kn , donde n es el número de vértices.

.d / Un grafo simple en el que todos los vértices tienen el mismo grado se conoce como grafo
regular. Si el grado de cada vértice es r, decimos que el grafo es regular de grado r.

v4 a1
v1 v4
v2
v1
a2
a5
a3
v1 v3
v3 a4 v2 v3 v2

Grafo Simple Grafos Completos

n.n 1/
Teorema 2. El grafo completo Kn tiene aristas.
2
Definición 6. Un camino de un grafo G D .V; A; f / es una sucesión finita y alternada de vértices
y aristas de la forma .v0 ; a1 ; v1 ; a2 ; v2 ; : : : ; vn 1 ; an ; vn / que comienza y termina con un vértice
y que satisface las condiciones siguientes:

1. Cada arista tiene por extremos el vértice que lo antecede y el vértice que lo sigue.

2. Las aristas son todas distintas.

El número n es la longitud del camino (número de aristas), v0 es el vértice inicial y vn es el

vértice final.

5
 v1 vn
v3 vn-2

v0 vn-1
v2

Definición 7.

.a/ Un camino simple es un camino que tiene todos sus vértices distintos.

.b/ Un camino euleriano es un camino que posee todas las aristas del grafo.

.c/ Un camino hamiltoniano es un camino que pasa una sola vez por todos los vértices del
grafo.

.d / Un ciclo es un camino que tiene al menos una arista y en el que el vértice final coincide
con el vértice inicial (es decir, v0 D vn ).

.e/ Un ciclo es simple si todos los vértices son distintos, excepto el inicial y el final.

.f / Un ciclo euleriano es un ciclo que tiene todas las aristas del grafo.

.g/ Un ciclo hamiltoniano es un ciclo que pasa una sola vez por todos los vértices del grafo,
excepto el vértice inicial y el vértice final.

.h/ Dos caminos son independientes o ajenos si no tienen ningún vértice en común, excepto
el inicial y el final.

Considere el siguiente grafo.

v1
a1
a8 a2

a6 a3
a7 v5 v2 v3

a5 a4

v4

6
 1. Camino de longitud 5:

C D .v3 ; a3 ; v2 ; a1 ; v1 ; a2 ; v2 ; a6 ; v5 ; a5 ; v4 /

Este camino tiene longitud 5 porque está formado por 5 aristas. Además, no es simple
porque el vértice v2 se repite.
2. Camino simple de longitud 4:

C D .v3 ; a3 ; v2 ; a1 ; v1 ; a8 ; v5 ; a5 ; v4 /

Este camino tiene 4 aristas y ningún vértice se repite.

3. Ciclo simple de longitud 4:

C D .v1 ; a1 ; v2 ; a4 ; v4 ; a5 ; v5 ; a8 ; v1 /

Es un ciclo porque el camino inicia y termina en v1 ; además, es simple porque ningún

vértice se repite, excepto el inicial y el final.
4. Un camino hamiltoniano es

C D .v3 ; a3 ; v2 ; a1 ; v1 ; a3 ; v5 ; a5 ; v4 /

5. El camino de mayor longitud del grafo tiene longitud 7; uno de ellos puede ser:

C D .v3 ; a3 ; v2 ; a2 ; v1 ; a8 ; v5 ; a7 ; v5 ; a6 ; v2 ; a4 ; v4 ; a5 ; v5 /:

Observa que este camino no es euleriano porque falta la arista a1 .

6. Dos caminos independientes son:

C1 D .v2 ; a1 ; v1 ; a8 ; v5 / y C2 D .v2 ; a4 ; v4 ; a5 ; v5 /

Definición 8. Sea G D .V; A; f / un grafo.

.a/ Si u y v son dos vértices de un grafo G, diremos que u y v están conectados si y sólo si
existe un camino que tiene sus extremos en u y en v.

.b/ Diremos que el grafo G es conexo si y sólo si para todo par de vértices u del grafo G
se cumple que u y v están conectados. En caso contrario, diremos que G es un grafo
disconexo.

.c/ Las “partes” que constituyen el grafo son llamadas componentes del grafo.

En pocas palabras, el grafo G es conexo cuando está constituido por una sola componente.

7
 v1 v2 v1 v3

v3 v5

v5 v4 v2 v4

Grafo conexo Grafo disconexo

Definición 9. Sea G D .V; A; f / un grafo.

.a/ G es euleriano si tiene un ciclo euleriano.

.b/ G es un árbol si es conexo y no tiene ciclos.

v1 v1 v2 v1 v1 v2

v3 v3

v2 v2
v4 v4

A1 A2 G1 G2

Ejemplos de árboles Estos no son árboles

En la imagen, G1 no es un árbol porque tiene un lazo en v2 , mientras que G2 tampoco lo es

porque tiene un ciclo formado por los vértices v1 , v2 y v3 .

Definición 10. Sean G D .V1 ; A1 ; f / y S D .V2 ; A2 ; g/ dos grafos. Diremos que S es un

subgrafo de G (es decir, un grafo derivado de otro grafo) si y sólo si se cumplen las siguientes
tres condiciones:

.a/ V2 es un subconjunto de V1 , es decir, V2  V1 .

8
 .b/ A2 es un subconjunto de A1 , esto es, A2  A1 .

.c/ g.a/ D f .a/ para toda a en A2 .

Teorema 3. Sea G D .V; A; f / un grafo conexo. Entonces:

1. G es euleriano si y sólo si todos sus vértices tienen grado par.

2. G tiene un camino euleriano si y sólo si G tiene exactamente dos vértices de grado impar
(el camino une los vértices de grado impar).

Definición 11. Sea G D .V; A; f / un grafo. Un árbol generador de G es un subgrafo de G que

es conexo y tiene todos los vértices del grafo G.

Teorema 4. Las siguientes proposiciones son equivalentes (es decir, si una es verdadera entonces
todas son verdaderas y si una es falsa, entonces todas son falsas):

.a/ G es un árbol.

.b/ G no tiene ciclos y posee n 1 aristas.

.c/ G es conexo y tiene n 1 aristas.

.d / Cualquier par de vértices de G pueden ser unidos por un único camino simple.

En un grafo G D .V; A; f / podemos representar las aristas con un valor numérico, el cual
llamaremos longitud de la arista. En este caso, la longitud de G es la suma de las longitudes de
todas sus aristas.

Definición 12. Sea G un grafo conexo. Un árbol generador económico de G es un árbol de G

con longitud mínima.

Construcción de un árbol generador

económico
Si el grafo G tiene n vértices, entonces la construcción de un árbol generador económico se
hace en n 1 pasos, el cual será el número de aristas que tendrá el árbol generador económico.

1. Se elige una arista a1 de G que no sea un lazo y que tenga la menor longitud de todas las
aristas de G. Sea G1 el grafo formado por la arista a1 y sus dos vértices.

2. Se construye un grafo G2 , agregando al grafo G1 una arista a2 de G (junto con sus vértices)
que tenga longitud mínima y de manera tal que el grafo G2 no tenga un ciclo. Es obvio que
la arista a2 debe ser distinta que la arista a1 . El grafo G2 no es necesariamente conexo.

3. Se construye G3 , agregando a G2 una arista a3 de G (distinta de a1 y a2 ) que tenga longitud

mínima y tal que G3 no tenga ningún ciclo. Este grafo no es necesariamente conexo y se
pueden cruzar las líneas.

9
 4. Se procede de manera similar al paso 3 hasta obtener un grafo Gn 1 . Este grafo es un árbol
generador económico de G.

Dado el grafo ponderado

6 5
v1 v2 v3

2 4 6 2

3
v6 v5 v4
5 7

Construir un árbol generador económico de longitud mínima.

Solución. Recordemos que un grafo ponderado es aquel en el que cada arista tiene un valor
numérico, como se muestra en la figura anterior. Para construir un árbol generador económico a
partir del grafo dado, seguiremos los pasos del algoritmo.
En primer lugar observa que el grafo tiene 6 vértices, por lo que el árbol generador económico
lo construiremos en 6 1 D 5 pasos.
1. En el grafo, la arista que tiene menor longitud es el lazo del vértice v3 , pero no podemos
tomar un lazo. En consecuencia, elegimos la arista que conecta los vértices v1 y v6 , cuya longitud

10
es 2.

v1

v6

2. Ahora, escogemos otra arista (distinta de la que ya tomamos) que tenga longitud menor al
resto de las aristas del grafo del enunciado y que no forme un ciclo. Por eso, tomamos la arista
que une los vértices v3 y v4 , de longitud 2.

v1 v3

2 2

v6 v4

11
 3. De las aristas que van quedando en el grafo, elegimos la que conecta los vértices v2 y v4 ,
porque tiene longitud 3 (la menor).

v1 v2 v3

2 2

v6 v4

4. Como la arista entre v3 y v5 tiene longitud 4, siendo la de menor valor, entonces la escoge-
mos como parte de nuestro árbol. Observa que se permite que algunas líneas se crucen siempre
y cuando no formen un ciclo.

v1 v2 v3

2 2

4
3
v5
v6 v4

12
 5. Finalmente, elegimos la arista entre v1 y v5 de longitud 4 por ser la de menor longitud entre
las aristas que quedan. (Recuerda que no podemos escoger ninguna arista repetida.)

v1 v2 v3

2 2

4
3
v5
v6 v4

Este es un árbol generador económico del grafo que nos dieron en el enunciado del ejercicio. Su
longitud es la suma de todas las longitudes de sus aristas, esto es,
2 C 4 C 4 C 2 C 3 D 15:
Observa que un árbol generador no tiene que ser único, es decir, puedes construir otro árbol
generador que sea diferente al que hemos obtenido aquí a partir del mismo grafo ponderado; sin
embargo, todo árbol generador económico que consigas para el grafo de este ejercicio debe tener
la misma longitud, o sea, 15. 

Dado el siguiente grafo ponderado

v1 2 3
v2 v3
4 5 1

2 4 2 3 v4

5 5
v7 v6 v5
2 3

hallar 3 árboles generadores económicos y diga cuál es su longitud.

13
Dada la matriz de adyacencia

v1 v2 v3 v4 v5
2 3
v1 0 2 1 1 0
v2
6
6 2 0 0 0 1 7
7
Ad.G/ D 1 0 0 1 1
6 7
v3 6 7
6 7
v4 4 1 0 1 0 0 5
v5 0 1 1 0 2

construya el grafo G asociado a esta matriz.

14