TUP Plan 2024 - Matemática Lic.

Giudice Vilma

Unidad VI – Tipos Abstractos de Datos: Grafos y Árboles

Módulo 7 – Grafos
Introducción
El término grafo fue introducido en 1887 por Sylvester, en el contexto de análisis algebraico de estructuras
moleculares. No obstante, el origen de la teoría de grafos puede remontarse unos 150 años cuando Euler
en 1736, publicó un trabajo en el cual resolvía el que ha venido a llamarse problema de los puentes de
Konigsberg. La ciudad de Konigsberg (Kaliningrado, durante la época soviética) estaba dividida por el río
Pregel en cuatro zonas: las dos orillas, la isla llamada Kneiphof y la parte comprendida entre las dos
bifurcaciones del río. En esa época existían siete puentes comunicando las distintas zonas, como puede
verse en la siguiente figura:

Figura 1. Los 7 puentes de Konigsberg

Parece ser que uno de los pasatiempos de los ciudadanos de Konigsberg consistía en dar un paseo que
cruzara cada puente exactamente una vez. Se pensaba que tal paseo no era posible habida cuenta de los
múltiples intentos fallidos, pero nadie había podido demostrar tal imposibilidad. Fue Euler quien
demostró este hecho. Euler reemplazó el mapa de la ciudad por un diagrama más simple, donde se
incluye la información relevante del problema. No llegó a dibujar el diagrama de puntos y líneas que hoy
se conoce como grafo, pero enunció que la condición necesaria dada por él también era suficiente. Su
demostración se debe a Hierholzer en 1871.
Para dicha demostración, Euler recurre a una abstracción del mapa y se enfoca exclusivamente en las
regiones terrestres y las conexiones entre ellas. Tomó 4 regiones y 7 caminos diferentes uniendo didas
regiones. Cada puente quedó representado mediante una línea que unía a dos puntos, y cada región
diferente estaba representada por un punto.
Desde entonces, los resultados y aplicaciones de la teoría de grafos han ido aumentando y los grafos se
utilizan en contextos muy diferentes, construir redes de comunicaciones, implementación de circuitos
en el plano, distinción de compuestos químicos con igual fórmula molecular, redes de transporte,
asignación de horarios, diseño de estructuras de datos, etc.
En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto
de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten
representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de
grafos. Típicamente, un grafo se representa gráficamente como un conjunto de puntos unidos por líneas
(aristas o arcos).

1
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que
interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse
mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las
cuales, a su vez, pueden ser cables o conexiones inalámbricas).
Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las
diversas áreas de las ciencias exactas y las ciencias sociales.
Por lo general, un grafo se representa en forma de diagrama como un conjunto de puntos o círculos para
los vértices, unidos por líneas o curvas para los bordes. Los grafos son uno de los objetos de estudio de
las matemáticas discretas.
Los bordes, arcos o aristas pueden ser dirigidos o no dirigidos. Por ejemplo, si los vértices representan
personas en una fiesta y hay una arista entre dos personas si se dan la mano, entonces este grafo no está
dirigido porque cualquier persona A puede darle la mano a una persona B sólo si B también le da la mano
a A. Por el contrario, si una ventaja de una persona A a una persona B significa que A le debe dinero a B,
entonces este grafo es dirigido, porque la deuda no es necesariamente recíproca.

Los Grafos y su Representación

Un grafo 𝐺 es un par ordenado 𝐺 = (𝑉,𝐸) , donde:

• 𝑉 es un conjunto de vértices o nodos, y

• 𝐸 es un conjunto de aristas o arcos, que relacionan estos nodos o vértices.
Normalmente 𝑉 suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para
grafos infinitos. Por lo que nuestro estudio será sobre grafos finitos.

Elementos de un Grafo
Nodos: un vértice o nodo es la unidad fundamental de la que están formados los grafos.
Aristas: Son las líneas que unen los vértices de un grafo. Existen distintos tipos de aristas:
• Aristas adyacentes: Dos aristas son adyacentes si convergen en el mismo vértice.
• Aristas cíclicas: Aristas que parten de un vértice para entrar en el mismo.
• Aristas paralelas: Dos aristas son paralelas si los vértices iniciales y finales son el mismo vértice
Una arista puede cruzarse con otra y al punto en que esto ocurre se lo llama cruce.
Camino: Se denomina camino a un conjunto de vértices interconectados por aristas. Dos vértices están
conectados si hay un camino entre ellos. En el siguiente grafo se ve en rojo uno de los caminos para ir del
nodo 1 al nodo 5:

2
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Los dos vértices que conforman una arista se llaman puntos finales ("endpoints", en inglés), y esa arista
se dice que es incidente a los vértices. Un vértice w es adyacente a otro vértice v si el grafo contiene una
arista (v,w) que los une. La vecindad de un vértice v es un grafo inducido del grafo, formado por todos los
vértices adyacentes a v.

Características de los Grafos

Se llama orden del grafo 𝐺 al número de vértices,|𝑉|, que el grafo posee.

El orden de G es 5, ya que posee 5 nodos o vértices

Un nodo es adyacente o contiguo a otro nodo si y sólo sí tienen entre ellos un arco o arista que los liga.
Un vértice w es adyacente a otro vértice v si el grafo contiene una arista (v,w) que los une. Se dice que dos
aristas son adyacentes o contiguas si tienen un extremo en común.

El vértice 2 y el vértice 3 son adyacentes al vértice 1, pero el vértice 2 no es adyacente al vértice 3

Se llama grado de un vértice o nodo 𝑣 ∈ 𝑉 a la cantidad de arcos o aristas que lo tienen como extremo.
Para identificar el grado de un vértice determinado por ejemplo el vértice v, usaremos d(v). (Tengamos en
cuenta que la letra d viene del inglés “degree”, grado en castellano). El grado de vértice depende del nodo
y cada uno puede tener grados diferentes.

3
TUP Plan 2024 - Matemática Lic. Giudice Vilma

El grado del vértice 1 de G es 4, y el grado del vértice 2 es 2. O sea d(1)=4, d(5)=2 y d(3)=3

Un bucle es una arista que relaciona un nodo consigo mismo; es decir, una arista donde el nodo inicial y
el nodo final coinciden.

Dos o más aristas son paralelas o múltiples si relacionan el mismo par de vértices.

El vértice 1 y 3 están ligados con 3 paralelas

La vecindad de un vértice v es un grafo inducido del grafo, formado por todos sus vértices adyacentes.

Vecindad del vértice 1

4
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Antes que nada, debemos tener en cuenta el motivo de la construcción del grafo, o sea debe existir una
relación o aplicación que nos indica qué nodos se conectan y cómo los nodos se conectan entre sí.
Veamos una nueva definición de grafo:

Un grafo finito es una terna G = (V,A,φ) donde V = V(G) es un conjunto finito (cuyos elementos
se denominan vértices o nodos) no vacío, A = A(G) es un conjunto finito cuyos elementos se
llaman aristas, y φ : A→P(V) es una aplicación que asocia a cada arista un par de vértices. Es
decir φ(a) = {x,y} con a ∈ A y x,y ∈ V

En estas condiciones, se dice que la arista a une x con y, o que los extremos de a son x e y, o que a es
incidente con x e y, o incluso que x e y son adyacentes a a. Se dice que la arista a es un lazo si φ(a) = {x,x}
para un cierto x ∈ V. Se dice que un vértice es aislado si no existen aristas incidentes con él.
Aristas Múltiples: Llamamos aristas múltiples a aquellas aristas repetidas, es decir existen a 1, a2, ..., ak
que pertenecen a A tal que φ(a1) = φ(a2) = ... = φ(ak).

Grafos Especiales
Grafos no Dirigidos y Grafos Dirigidos
Un grafo no dirigido es un tipo de grafo en el cual las aristas representan relaciones simétricas y no
tienen un sentido definido, a diferencia del grafo dirigido, en el cual las aristas tienen un sentido y por
tanto no son necesariamente simétricas.

Un grafo dirigido o dígrafo es una terna G = (V,A,φ) donde V son el conjunto de vértices y A el conjunto de
aristas del grafo y φ : A → V × V es una aplicación que asocia a cada arista un par de vértices ordenados.
Es decir, φ(a) = (x,y) con a ∈ A y x,y ∈ V. O sea, una arista que empieza en x y acaba en y. En este sentido,
las aristas de un grafo dirigido representan una dirección. Por tanto, se ha de distinguir entre dos aristas
(a,b) incidentes a los mismos dos vértices, x,y pero tal que φ(a) = (x,y) y φ(b) = (b,a)
Formalmente, se definen por un par de conjuntos 𝐺 = (𝑉,𝐸), donde:
• V ≠ ⌀ es el conjunto no vacío de vértices o nodos.
• E  {(a,b)  V x V } es el conjunto de aristas, tal que (a,b) ≠ (b,a) si es dirigido y {a,b}={a,b}
si es no dirigido.
En el caso de los grafos no dirigidos, una arista (a,b) también se puede denotar como {a,b}.
En algunas situaciones reales en las que se usan grafos, las aristas además tienen un sentido o dirección;
es decir, salen de un vértice y llegan a otro (algo así como el sentido de circulación). Esto dará un grafo
dirigido o dígrafo.

n = | V | nos indica la cantidad de nodos que un grafo tiene.

m= | E | nos indica la cantidad de aristas que un grafo tiene.

La cantidad de aristas m que un grafo no dirigido con n nodos, sin aristas adyacentes, será un número
Natural comprendido entre los siguientes valores:

5
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Esto nos da la cantidad de parejas posibles a formarse con la cantidad de nodos dados. Al grafo que tiene
todos sus nodos ligados entre sí, o sea que la cantidad de vértices sea el máximo posible, se lo llama
grafo completo.

La cantidad de aristas m que un grafo dirigido con n nodos, sin aristas adyacentes, será un número natural
comprendido entre los siguientes valores:

Grafo Simple
Un grafo simple es aquel grafo no dirigido que acepta una sola arista uniendo dos vértices cualesquiera.
Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la
definición estándar de un grafo. Tengamos en cuenta que un grafo simple no puede tener lazos o bucles,
o sea un nodo se puede conectar con cualquier otro nodo, pero no consigo mismo. El grado de todos sus
vértices tiene que ser uno.

Diremos que un grafo es simple si no tiene lazos y dos vértices están unidos a lo sumo por una única
arista. Si es n-1 el grado de todos sus vértices decimos que el grafo está completo.

El grado de cualquier vértice v, d(v), de un grafo simple con n nodos, será un número natural comprendido
entre los siguientes valores:

Multi Grafo o Pseudografo.

Un multi grafo o pseudografo es un grafo que tiene aristas múltiples; es decir, aristas que relacionan los
mismos nodos. De esta forma, dos nodos pueden estar conectados por más de una arista. Los multi
grafos podrían usarse, para modelar las posibles conexiones de vuelo ofrecidas por una aerolínea. Para
este caso tendríamos un grafo dirigido, donde cada nodo es una localidad y donde pares de aristas

6
TUP Plan 2024 - Matemática Lic. Giudice Vilma

paralelas conectan estas localidades, según un vuelo es hacia o desde una localidad a la otra. Cuando
un multi grafo es dirigido se lo llama multidigrafo.

Grafos Notables
Por ejemplo, algunos grafos particulares tienen características especiales y reciben un nombre en
concreto. A continuación, se detallan algunos de ellos cuya representación gráfica se muestra en cada
una de las figuras dadas:

Grafo Completo: Kn.

K6
Vértices: V = {x1, x2, ..., xn},
Aristas: A = {aij}, 1 ≤ i < j ≤ n tal que φ(aij) = {xi, xj}.

Grafo Lineal: Ln

L6
Vértices: V = {x1, x2, ..., xn},
Aristas: A = {ai},1 ≤ i ≤ n−1 tal que φ(ai) = {xi, xi+1}.

7
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Grafo Ciclo: Cn

C6
Vértices: V = {x1, x2, ..., xn},
Aristas: A = {ai},1 ≤ i ≤ n tal que φ(ai) = {xi, xi+1} si i < n y φ(an) = {xn, x1}.

Grafo Rueda: Rn

R6
Vértices: {x1, x2, ..., xn},
Aristas: A = {ai,bj},1 ≤ i,j ≤ n tal que ai es como en el grafo ciclo y φ(bj) = {xo,xj}. v.)

Grafo Bipartito Completo: Kn,m

K3,4
Vértices: {x1, x2,...,xn,y1,y2 ...ym},
Aristas: A = {aij},1 ≤ i ≤ n, 1 ≤ j ≤ m tal que φ(aij) = {xi, yj}

En general, un grafo G se dice bipartito si existe una partición de V, es decir V1 ∩ V2 = ∅ y V1 ∪ V2 = V,

V =V1⊕V2, tal que todas las aristas de G unen un vértice de V1 con un vértice de V2.

8
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Grafos Conexos y No Conexos

Veamos los siguientes grafos y analicemos en cada caso cómo se conectan los vértices:

Grafo 1 Grafo 2 Grafo 3

En el grafo 1 podemos observar que podemos recorrer todos los nodos ya que existe algún camino que
permite conectarlos.
En el grafo 2, en cambio existe un nodo que no está conectado con ningún otro nodo del grafo y podríamos
distinguir dos subgrafos que tampoco se conectan entre sí, si quisiéramos ir desde nodo 1 al nodo 5, o al
nodo 6 no podríamos llegar.
En el grafo 3 vemos tres subgrafos que no están conectados entre sí.

Por consiguiente, podemos definir a un Grafo Conexo por la existencia de aristas entre sus vértices. O
sea, un grafo no dirigido G es conexo si para todo vértice u, v, vértices de G, donde u sea distinto de v,
existe un camino entre u y v. Por lo que en nuestros ejemplos sólo el grafo 1 es un grafo conexo, los otros
dos son grafos no conexos. Cabe aclarar que el caso teórico de un grafo con un único vértice aislado se
lo considera conexo.
Tomemos los siguientes dos grafos no conexos:

9
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Podemos observar que en cada uno de ellos tenemos tres zonas en las cuales hay grafos que si son
conexos. Con lo cual se podrá plantear una relación de accesibilidad dentro del conjunto de vértices

Sea G(V,E) un grafo no dirigido, y los vértices x, y  V. Se define la relación de accesibilidad R* en V, tal que
x R* y (el vértice x tiene una relación de accesibilidad con y) si y sólo sí x = y o existe un camino ente x e
y. Se dice que y está conectado con x o que y es alcanzable desde x (al ser un grafo no dirigido, si esto
último se da, x es también alcanzable desde y)

Matriz de Adyacencia
La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones
binarias. Tener en cuenta que un mismo grafo, con n nodos, puede tener n! matrices diferentes
dependiendo del orden que se establezca en la presentación de los nodos.
Construcción de la Matriz a partir de un Grafo
Se crea una matriz nula, cuyas columnas y filas representan los nodos del grafo ordenados de la misma
forma en las filas y en las columnas. Vemos dos inicios de matriz de adyacencia en las que se han
ordenado en forma diferente los nodos:

Por cada arista que une a dos nodos, se suma 1 al valor que hay actualmente en la ubicación
correspondiente de la matriz. Si tal arista es un bucle y el grafo es no dirigido, entonces se suma 1 o 2
(dependiendo de la convención usada).
Finalmente, se obtiene una matriz que representa el número de aristas (relaciones) entre cada par de
nodos (elementos).
Sea por ejemplo el siguiente grafo no dirigido con 6 nodos, su matriz de adyacencia considerando que los
bucles se le sumará 2 (si sumamos la filas o las columnas nos dará el grado del vértice ya que los bucles
suman 2) es:

10
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Existe una matriz de adyacencia única para cada grafo (sin considerar las permutaciones de filas o
columnas), y viceversa. Nótese que la matriz obtenida es una matriz simétrica. En un grafo no dirigido,
la transpuesta de matriz de adyacencia es igual a la matriz de adyacencia.

Veamos un ejemplo de la matriz de adyacencia de grafo dirigido:

En los grafos dirigidos la matriz de adyacencia se construye teniendo en cuenta que los nodos que se
encuentran en las filas son los nodos de partida de las aristas y en las columnas los nodos de llagada de
las aristas. Se colocará el número de aristas que salen de un nodo y llegan a otro o cero si no hay arista
que ligue en ese sentido. Esta matriz puede no ser simétrica.
En este ejemplo vemos que al tener una sola arista dirigida de un nodo a otro obtenemos una matriz
booleana (de unos y ceros), podríamos tener caminos de ida y de regreso de un nodo a otro pero si sólo
es uno en cada sentido, aun con bucles, tendremos una matriz con unos y ceros.
Veamos otro ejemplo de matriz de adyacencia para un multi grafo dirigido, en este caso en la matriz hemos
indicado cuáles son las columnas al tratarse de vértices llamados con una letra (recordemos que
podemos ubicar los nodos en diferente orden, pero sí tiene que ser el mismo orden de las filas que de las
columnas):

Un grafo ponderado, pesado o con costos es un grafo donde cada arista tiene asociado un valor o
etiqueta, para representar un dato específico como por ejemplo, el costo, peso, longitud, tiempo, etc. Si
deseamos construir la matriz de adyacencia de un grafo ponderado, deberemos tener en cuenta que en
lugar de sumar uno (1) por cada arista se suma el peso de la arista respectiva. Veamos esto con un
ejemplo:

11
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Propiedades de la Matriz de Adyacencia

Para un grafo no dirigido la matriz de adyacencia es simétrica. Esta matriz nos permite ver cuántos
caminos hay entre cada uno de los nodos del grafo.
Consideremos ahora que la matriz de adyacencia la hemos creado considerando que los bucles sumarán
1 a la matriz nula.

Qué podemos ver en la matriz de Adyacencia

La matriz A nos muestra con el elemento A(5,1)=3 que el nodo 1 tiene 3 caminos posible con el nodo 5,
que el nodo 1 tiene un camino consigo mismo, un bucle, pues A(1,1)=1. Como A(5,4)=2 el nodo 5 tiene
dos caminos para llegar al nodo . Todos estos caminos son de longitud 1.
Si necesitamos saber cuántos caminos de longitud uno hay entre el nodo 1 y el 4, pasando por el nodo 5,
bastará con hacer el producto de los caminos que hay de 1 a 5 y de 5 a 4, A(1,5).A(5,4)= 3.2=6, la matriz
nos dice que hay 6 caminos de longitud 1 entre 1 y 4 pasando por 5.
La matriz de adyacencia nos brinda información sobre la conectividad del grafo.
Sea ahora la matriz 𝐴2 = 𝐴. 𝐴 analizaremos que pasa con sus elementos:

12
TUP Plan 2024 - Matemática Lic. Giudice Vilma

El elemento de la matriz 𝐴2 que se encuentra en la fila 4 columna 1 o sea [𝐴2 ]41 = 𝐴2 (4,1) se obtuvo
demultiplicar la fila 4 con la columna 1:

Se puede observar que A(4,5) es la cantidad de caminos de longitud 1 que hay entre los nodos 4 y 5 y que
A(5,1) es la cantidad de caminos que hay entre los nodos 5 y 1.

Teorema: Sea el grafo no dirigido G(V,E) cuya matriz de adyacencia es A respecto de alguna ordenación
de V, entonces el elemento[𝐴𝑘 ]𝑖𝑗 es la cantidad de caminos de longitud k entre el vértice i (vi ) y el vértice
j (vi ). La matriz 𝐴𝑘 es la potencia k de la matriz de adyacencia.
Este último teorema nos indica que la matriz de adyacencia permite con sus diferentes potencias
encontrar la cantidad de caminos de acuerdo con una longitud deseada que hay entre dos nodos
cualesquiera del grafo.
Si se quisiera saber la cantidad de caminos que van desde la arista 1 a 4, de longitud 2 debemos usar la
una potencia de la matriz de adyacencia, o sea 𝐴𝑘 con k es igual a 2, A2 y buscar el elemento de la fila 1
columna 4 o fila 4 columna 1 ya que en los grafos no dirigidos la matriz de adyacencia es simétrica y sus
potencias también los son, A2(1,4)=A2(4,1)=6.
13
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Debido a que en el elemento [𝐴2 ]25 =A2(2,5) = 3 indica que hay tres caminos de longitud 2 desde el nodo 2
al nodo 5.
Si deseamos los caminos de longitud 3 que ligan dos nodos entre sí deberemos encontrar primero la
matriz de adyacencia elevada al cubo o sea A3 = A2.A = (A. A). A. O sea que:
A2(2,5) = cantidad de caminos de longitud 2 entre el nodo 2 y el nodo 5, ente v2 y v5
A3(2,5) = cantidad de caminos de longitud 3 entre el nodo 2 y el nodo 5, v2 y v5
A5(2,5) = cantidad de caminos de longitud 5 entre el nodo 2 y el nodo 5, v2 y v5
Corolario del teorema: Sea el grafo no dirigido G(V,E) con |V|=n cuya matriz de adyacencia es A respecto
de alguna ordenación de V y la matriz C se obtiene como la suma de las distintas potencias de A desde 1
hasta n-1 entonces existe un camino entre el vértice i (vi ) y el vértice j (vi ) sí y sólo si el elemento C(i,j) no
es nulo.
Veamos esto con un grafo no dirigido G(V,E) con |V|=4 y cuya matriz de adyacencia es:

La matriz C es entonces la siguiente matriz:

Nos indica que el vértice 4, (v4 ), no tiene nexo con ningún otro nodo. El grafo no es conexo.
Veamos un nuevo ejemplo:

Cuya matriz C es la siguiente matriz:

En este último grafo la matriz C no tiene ningún componente nulo y por el último corolario nos dice que
existe entre todos sus nodos algún camino posible entre ellos. En este caso podemos decir que el grafo
es un grafo conexo. Por consiguiente:

14
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Un grafo conexo es aquel grafo que tiene caminos entre cualquier par de vértices del grafo.

Matriz de Incidencia
Matriz de Incidencia de Grafos no Dirigido: Las matrices de incidencias son matrices rectangulares,
sólo serán cuadradas si el grafo tiene la misma cantidad de aristas que vértices. La matriz de incidencia
es una matriz binaria o booleana (sus elementos sólo pueden ser unos o ceros) que se utiliza como una
forma de representar relaciones binarias.

• Las columnas de la matriz representan las aristas del grafo.

• Las filas representan a los distintos nodos o vértices.
• Por cada nodo unido por una arista, ponemos un uno (1) en el lugar correspondiente, y llenamos
el resto de las ubicaciones con ceros (0).
En particular, la matriz de incidencia es muy utilizada en la programación, debido a su naturaleza binaria
y matricial calza perfecto en la programación. Sin embargo, a una persona sin conocimientos de
computación se le hará mucho más sencillo comprender una relación descrita mediante grafos, que
mediante matrices de incidencia.
En esta matriz se deja asentado de cada nodo cuáles son las aristas que llegan a él, marcando con 1 si
llega o 0 si no está une ese nodo. Por lo tanto en esta matriz se usarán las filas para mostrar los nodos y
las columnas para mostrar las aristas, cada columna tendrá dos unos, uno para cada vértice que liga la
arista en cuestión.
Para confeccionar una matriz de incidencia lo primero a hacer es darle nombre a cada arista. Armamos
la matriz considerando en las filas los vértices y en las columnas las aristas. Recordemos que en la matriz
de adyacencia usábamos tanto en las filas como en las columnas los nodos o vértices. Veamos un
ejemplo:

Cada celda o elemento de la matriz de incidencia corresponde a la posible incidencia entre un nodo y un
vértice. Colocaremos un 1 si la arista incide en el vértice que estamos tomando o un cero cuando ésta no
incida. Cada columna tendrá sólo dos unos mientras que las filas pueden tener más de dos unos:

15
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Matriz de Incidencia de Grafos Dirigido: En esta matriz, al igual que en los grafos no dirigidos, tomamos
en las filas cada nodo y en las columnas cuáles son las aristas que tiene el grafo, marcaremos con 1 si la
arista tiene origen en ese nodo, con -1 si la arista tiene como destino ese nodo (la flecha llega a ese nodo)
o 0 si esa arista no se relaciona con el nodo. Por lo tanto en esta matriz se usarán las filas para mostrar
los nodos y las columnas para mostrar las aristas, cada columna tendrá unos, menos unos o ceros.

En el caso de que tengamos un multidigrafo vemos que se trabaja de la misma forma, pero tendremos tal
vez filas repetidas o columnas en las que algunos elementos están intercambiados (cuando relacionan
los mismos nodos pero en sentidos distintos). Sólo utilizamos 1, -1 y 0 ya que tenemos tantas columnas
como arcos, aristas, tengamos. Pero si el grafo tiene un bucle en esa arista colocaremos 2 o -2 como se
lo defina desde un inicio:

La matriz de incidencia nos permite ver el grado de cada vértice pero divididos en grados de entrada
(cuenta de los -1) y grados de salida (cuenta de los 1). Por ejemplo, el nodo c tiene tres aristas de entrada

16
TUP Plan 2024 - Matemática Lic. Giudice Vilma

y tres de salida, por lo que el grado del nodo c es 6. El -2 del bucle recordemos que cuenta uno de entrada
y uno de salida.

Estructuras de Datos en la Representación de Grafos

Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada
depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más
sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una
combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la
memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades
de memoria.
Estructura de lista

• Lista de Incidencia: Las aristas son representadas con un vector de pares (ordenados, si el grafo es
dirigido), donde cada par representa una de las aristas.
• Lista de Adyacencia: Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto
causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa),
pero las búsquedas son más rápidas, pese al costo de almacenamiento extra.
En esta estructura de datos la idea es asociar a cada vértice i del grafo una lista que contenga todos
aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos
adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se
representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista
de adyacencia correspondiente a cada uno de los vértices del grafo. Cada elemento de la lista consta de
un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un
segundo campo para mostrar el valor de la etiqueta.
Estructuras matriciales

• Matriz de Incidencia: El grafo está representado por una matriz de A (aristas) por V (vértices), donde
[arista, vértice] contiene la información de la arista (1 - conectado, 0 - no conectado)
• Matriz de Adyacencia: El grafo está representado por una matriz cuadrada de orden N, donde, siendo
n el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento es 1,
en caso de que haya más de una arista se debe colocar el número correspondiente a la cantidad de
aristas que existen entre ambos nodos, de lo contrario se coloca 0.

Isomorfismo de Grafos
Un isomorfismo de grafos es una biyección de los vértices de un grafo sobre otro, de modo que se
preserva la adyacencia de los vértices. Más formalmente, el isomorfismo entre dos grafos G y H es una
función f entre los conjuntos de sus vértices f: V(G) → V(H) que preserva la relación de adyacencia. Es
decir, cualquier par de vértices u y v de G son adyacentes si y sólo si lo son sus imágenes, f(u) y f(v), en H.
A continuación, presentaremos un ejemplo de dos grafos son isomorfos, que a pesar de su diferente
aspecto, los dos grafos muestran que existe una función entre ellos, el isomorfismo entre G y H es el
siguiente:
𝑓(𝑎) = 1 𝑓(𝑑) = 3 𝑓(𝑐𝑖) = 4
𝑓(𝑏) = 6 𝑓(𝑔) = 5 𝑓(𝑗) = 7
𝑓(𝑐) = 8 𝑓(ℎ) = 2

17
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Grafo G Grafo H

Dos grafos con matrices de adyacencia respectivas A y B serán isomorfos si y sólo si existe una
matriz permutación P tal que B = P A P t
La determinación de si dos grafos con el mismo número de vértices n y aristas m son isomorfos o no, se
conoce como el problema del isomorfismo de grafos.

Subgrafo
Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G.
Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H (dependiendo
de las necesidades de la situación).
El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al
subconjunto de vértices de G.
Definición: Sea G=(V, A). G’=(V’,A’) se dice subgrafo de G si:

1. V’  V
2. A'  A
3. (V’,A’) es un grafo
Tener en cuenta que si G’=(V’,A’) es subgrafo de G, para todo v G (vértice de V) se cumple que el grado
de v en G’ es menor o igual al grado de v en G, o sea d(G’, v) ≤ d(G, v)

Ciclos y Caminos Hamiltonianos

Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde
se regresa al punto inicial.
Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (excepto el
vértice del que parte y al cual llega). Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo
sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa
el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas).
Se habla también de camino hamiltoniano si no se impone regresar al punto de partida, como en un
museo con una única puerta de entrada. Por ejemplo, si un caballo puede recorrer todas las casillas de
un tablero de ajedrez sin pasar dos veces por la misma, es un camino hamiltoniano.
Otro ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro. Hoy en día, no se conocen métodos
generales para hallar un ciclo hamiltoniano, siendo la búsqueda por fuerza bruta de todos los posibles
18
TUP Plan 2024 - Matemática Lic. Giudice Vilma

caminos u otros métodos excesivamente costosos. Existen, sin embargo, métodos para descartar la
existencia de ciclos o caminos hamiltonianos en grafos pequeños.

Grafos Ponderados o Etiquetados

En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación
o coste según el contexto, y se obtiene así un grafo valuado. Formalmente, es un grafo con una función v:
A → R+ . Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por
carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever
atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la
valuación será la distancia entre ellas. Y, de momento, no se conocen métodos generales para hallar un
ciclo de valuación mínima, pero sí para los caminos desde a hasta b, sin más condición.

Grafos Eulerianos
Un grafo es euleriano si es conexo y el grado de todos sus vértices es par. En ese caso podemos encontrar
un ciclo que recorra todas las aristas pasando por cada una de ellas una sola vez. Veamos un grafo
euleriano:

19
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Si el grafo es conexo y sólo hay dos vértices de grado impar, el grafo es semi euleriano y habrá un camino
euleriano que recorra todas las aristas comenzando por uno de los vértices de grado impar y terminando
en el otro.
Teorema de Euler. Un grafo conexo y no dirigido es euleriano si y solo si cada vértice tiene grado par.
Teorema. Un grafo conexo y no dirigido es semi euleriano si y solo si solo tiene dos vértices de grado impar.

Consideraciones de Grafo Dirigidos

Todo grafo dirigido simétrico se puede representar como un grafo no dirigido. Por lo tanto, los grafos no
dirigidos se pueden ver como un caso particular de grafos dirigidos.

Más Definiciones
Nodo Aislado: vértice que no se conecta con ningún otro vértice, ni llega ni sale una arista de él.
Nodo Impar: es aquel vértice que une un número impar de aristas o curvas, tiene grado impar.
Nodo Par: es aquel vértice que une un número par de aristas o curvas, tiene grado par.

Camino: Un camino (en inglés, walk, y en ocasiones traducido también como recorrido) es una sucesión
de vértices y aristas dentro de un grafo, que empieza y termina en vértices, tal que cada vértice es
incidente con las aristas que le siguen y le preceden en la secuencia. Dos vértices están conectados o
son accesibles si existe un camino que forma una trayectoria para llegar de uno al otro; en caso contrario,
los vértices están desconectados o bien son inaccesibles.
Dos vértices pueden estar conectados por varios caminos. La longitud de un camino es su número de
aristas. Así, en un grafo no dirigido, los vértices adyacentes están conectados por un camino de longitud
1, los segundos vecinos por un camino de longitud 2, y así sucesivamente. Un grafo no dirigido es conexo
si todos sus vértices están conectados a través de un camino. Un grafo conexo cuyos vértices y aristas
permiten definir un camino es un grafo camino.
Dado un grafo 𝐺 = (𝑉,𝐸), un camino es una sucesión de vértices 𝑣1𝑣2…𝑣𝑛+1 y aristas 𝑙1𝑙2…𝑙𝑛 tales que
𝑙𝑖={𝑣𝑖,𝑣𝑖+1} (en caso de que el grafo sea no dirigido) para todo 𝑖 ∈ {1,…,𝑛}. La longitud del camino es 𝑛.
Tipos de Trayectorias Relacionadas: Existen varios conceptos derivados del de camino:
Un recorrido (en inglés, trail, a veces traducido como rastro) es un camino sin aristas repetidas.
20
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Un camino cerrado es un camino cuyo vértice inicial y final coinciden.

Un camino abierto es un camino cuyo vértice inicial y final no coinciden.
Un camino simple (en inglés, path, a veces traducido como camino) es un camino sin vértices repetidos,
salvo quizás el primero y el último (por lo tanto, es un tipo especial de recorrido, pues tampoco tiene
aristas repetidas).
Un ciclo (en inglés, cycle) es un camino simple que además es un camino cerrado. Es un camino simple
cerrado no trivial (no es lazo).
Un circuito (en inglés, circuit) es un recorrido que además es un camino cerrado. Un circuito no es un
ciclo, en el circuito se pueden repetir vértices mientras que en el ciclo no (aunque ambos parten y llegan
al mismo sitio).
Un ciclo euleriano es un ciclo que pasa por todas las aristas del grafo una única vez.
Un ciclo hamiltoniano es un ciclo que pasa por todos los vértices del grafo una única vez (en caso de que
el vértice inicial y final no coinciden, se suele hablar también de camino hamiltoniano).
Un camino hamiltoniano en un grafo es un camino simple que pasa por todos los vértices.
Un camino trivial es un camino que consta de un solo vértice y no tiene aristas. Es decir, comienza y
termina en el mismo vértice sin recorrer ninguna arista.
Un grafo trivial es un grafo con 0 aristas, y 0 o 1 vértices. Los grafos triviales son grafos completos, si no
posee vértices se le llama grafo nulo, mientras que al que posee un vértice, se le conoce como grafo
singleton.

Complementemos algunos conceptos:

Recorrido: La operación de recorrer una estructura de datos consiste en visitar (procesar) todos y cada
uno de los nodos a partir de uno dado. Así, para recorrer un árbol se parte del nodo raíz y según el orden
se visitan todos los nodos. De igual forma, recorrer un grafo consiste en visitar todos los vértices
alcanzables a partir de uno dado. Hay dos formas de recorrer un grafo: recorrido en profundidad y
recorrido en anchura.
Si el conjunto de nodos marcados se trata como una cola, entonces el recorrido es en anchura; si se trata
como una pila, el recorrido es en profundidad. Veamos con el siguiente ejemplo de grafo que existen
varios recorridos para hacer tanto en anchura como en profundidad, a modo de ejemplo plantearemos
de cada grafo dos recorridos en anchura y dos recorridos en profundidad:

Recorrido en Anchura
Visitando primero el nodo
izquierdo sería:
a→b→d→e→c
Visitando primero el derecho
sería:
a→d→b→e→c

21
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Recorrido en Profundidad
Visitando primero el nodo
izquierdo seria:
a→d→e→b→c
Visitando primero el nodo
derecho seria:
a→b→c→e→d

Ciclo Euleriano – Ciclo de Euler: Es aquel grafo en que todos sus vértices son pares y, además, se lo
puede recorrer de un solo trazo. La característica de este ciclo es que se elige para iniciar el trazo
cualquier vértice y en ese mismo vértice se termina.
Recorrido Euleriano – Recorrido de Euler: es un recorrido que pasa por todas las aristas del grafo, una
única vez. Es aquel en el cual, el grafo tiene sólo 2 vértices impares y, además, si se puede recorrer de un
solo trazo. La característica de este recorrido es que se elige para iniciar el trazo cualquier punto impar y
se terminará en el otro punto o vértice impar
Concepto de Distancia: cuando tenemos un grafo conexo es importante saber la longitud del camino
más corto entre cada 1 de sus vértices, esto se lo conoce como distancia entre dos vértices. Sí dos
vértices son adyacentes su distancia será de 1, es la menor de las longitudes de los caminos posibles
entre esos nodos. O sea, dados dos vértices u y v cualesquiera de un grafo G definimos la distancia de
entre los vértices u y v mediante la longitud del camino más corto que los une, en caso de que dichos
vértices no estén conectados su longitud es infinita.

Alcance y Aplicaciones de Grafos

Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de
circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas, por ejemplo,
Dibujo Computacional, en todas las áreas de Ingeniería.
Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las
calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos
algoritmos como puede ser el algoritmo de Floyd.
Para la administración de proyectos, utilizamos técnicas como PERT o CPM en las que se modelan los
mismos utilizando grafos y optimizando los tiempos para concretar los mismos.
La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para
desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y
verifica la posición, centralidad e importancia de cada actor dentro de la red. Esta medida permite
cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse
gráficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una
sociedad al identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el
poder se transmite y a quiénes.
Los grafos son importantes en el estudio de la biología y hábitat. El vértice representa un hábitat y las
aristas representa los senderos de los animales o las migraciones. Con esta información, los científicos
pueden entender cómo esto puede cambiar o afectar a las especies en su hábitat.

22
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Si volvemos a nuestro punto de partida, cómo comenzaron los grafos con el problema de los puentes,
dándole nombre a las regiones podemos ver que se resume a un problema de grafos:

En este problema de grafos se trata de ver si existe un circuito, o sea un recorrido cerrado, que recorre
cada arista exactamente una vez.
Euler determinó que para que un grafo contenga un circuito euleriano, o sea se pueda tener un camino
cerrado que sólo pase por una arista específica una única vez y se pase por todas las aristas del grafo,
éste debe tener sus vértices centrales de grado par.
Euler en el contexto del problema, vio que los puntos intermedios de un recorrido posible necesariamente
han de estar conectados a un número par de líneas. En efecto, si llegamos a un punto desde alguna línea,
entonces el único modo de salir de ese punto es por una línea diferente. Esto significa que tanto el punto
inicial como el final serían los únicos que podrían estar conectados con un número impar de líneas. Sin
embargo, el requisito adicional del problema dice que el punto inicial debe ser igual al final, por lo que no
podría existir ningún punto conectado con un número impar de líneas.
En particular, como podemos ver en el grafo del problema de los siete puentes de Königsberg tenemos 4
nodos pero todos son impares (a, c y d tienen grado 3 pero b tiene grado 5), los cuatro nodos tienen un
número impar de líneas (tres de ellos tienen tres líneas y el restante tiene cinco). Por lo tanto, se concluye
que es imposible definir un camino con las características buscadas que son los siete puentes de
Königsberg.
El problema original en la actualidad no es el mismo: dos de los siete puentes originales fueron destruidos
por el bombardeo de Königsberg durante la Segunda Guerra Mundial. Otros dos fueron posteriormente
demolidos y reemplazados por carreteras modernas. Los tres puentes restantes aún permanecen en pie,
aunque solo dos de ellos desde la época de Euler, pues uno fue reconstruido en 1935.
Por lo tanto, en la actualidad solo existen cinco puentes en Kaliningrado, distribuidos de tal manera que
ahora sí es posible definir un camino euleriano, es decir, una ruta que comienza en una isla y termina en
otra; pero no todavía un ciclo euleriano, es decir, que la ruta comience y termine en el mismo lugar, lo cual
era necesario para cumplir con las condiciones iniciales del problema.

23
TUP Plan 2024 - Matemática Lic. Giudice Vilma

Ejercicios
1. Seleccionar la afirmación correcta para cada uno de los siguientes grafos:
a) El grafo es un circuito euleriano.
b) El grafo es un ciclo hamiltoniano.
c) El grafo contiene un recorrido euleriano pero no es un
circuito euleriano.
d) El grafo es un camino hamiltoniano pero no es un ciclo
hamiltoniano.
e) Ninguna de las anteriores afirmaciones es correcta

a) El grafo es un circuito euleriano.

b) El grafo es un ciclo hamiltoniano.
c) El grafo contiene un recorrido euleriano pero no es un
circuito euleriano.
d) El grafo es un camino hamiltoniano pero no es un ciclo
hamiltoniano.
e) Ninguna de las anteriores afirmaciones es correcta

2. Dado el siguiente grafo G

a. Construir su matriz de adyacencia.
b. Construir su matriz de incidencia.
c. Indicar el grado de cada uno de sus vértices.
d. Indicar cuáles son los vértices pares y cuáles son impares.

3. Construir un grafo no dirigido de 5 vértices con los siguientes grados 1, 1, 2, 2, 4.

4. Dibujar un grafo completo ponderado de 5 vértices

24
TUP Plan 2024 - Matemática Lic. Giudice Vilma

5. Dada la matriz de adyacencia del grafo ponderado simple G no dirigido:

a. Construir el grafo respectivo.
b. Construir su matriz de incidencia
c. Indicar cuáles son todos los caminos posibles para llegar del nodo A al nodo E
d. Indicar cuál de los caminos planteados es el camino más corto

6. Dado el siguiente grafo G

a. Construir su matriz de adyacencia
b. Definir el grado de cada uno de sus vértices.
c. Indicar cuáles son nodos pares y cuáles son nodos impares
d. Definir tres caminos.
e. Definir tres circuitos.
f. Dibujar tres subgrafos a partir del mismo

7. Cuántas aristas tiene un grafo si sus vértices tienen los siguientes grados: 4, 3, 3, 2, 2. Dibujarlo.
8. Dado el siguiente grafo G dirigido
a. Construir su matriz de adyacencia.
b. Indicar cuál es el orden del grafo G

25