Análisis de Algoritmos

Solución Práctico 5
Ingeniería en Informática

Se proponen soluciones de ejemplo para algunos de los ejercicios del práctico. Las
soluciones presentadas no son las únicas posibles. Pueden existir otras soluciones
igualmente correctas.

Ejercicio 1
Considerando que la función T(n) para el algoritmo de DFS está dada por T(n) = | V | + 2 | A | cuando
el grafo es no dirigido, calcule la expresión concreta para T(n) en los siguientes casos y luego
indique cuál es el orden del algoritmo en cada uno.
a) G es un grafo completo.
Solución:
Dado que G es un grafo completo, se cumple que | V | = n y | A | = n (n – 1) / 2. Tenemos entonces
2 2
que T(n) = n + 2.n (n – 1) / 2 = n + n (n – 1) = n + (n – n) ⇒ . T(n) = n .
Concluimos que el algoritmo es de O(n2) en este caso.
b) G es un árbol.
Solución:
Dado que G es un árbol, se cumple que | V | = n y | A | = n – 1. Tenemos entonces que
T(n) = n + 2.(n – 1) = n + 2n – 2 ⇒ . T(n) = 3n – 2 .
Concluimos que el algoritmo es de O(n) en este caso.
c) G es como un grafo completo pero además tiene un lazo en cada nodo.
Solución:
Dado que G es un grafo completo pero además tiene un lazo en cada nodo, se cumple que
| V | = n y | A | = n (n – 1) / 2 + n. Tenemos entonces que T(n) = n + 2.(n (n – 1) / 2 + n) =
2 2
n + 2.(n (n – 1) + 2n) / 2 = n + (n (n – 1) + 2n) = n + (n – n + 2n) ⇒ . T(n) = n + 2n .
2
Concluimos que el algoritmo es de O(n ) en este caso.
d) G es como un árbol pero además tiene un lazo en cada nodo.
Solución:
Dado que G es como un árbol pero además tiene un lazo en cada nodo, se cumple que
| V | = n y | A | = n – 1 + n. Tenemos entonces que T(n) = n + 2.(n – 1 + n) = n + 2.(2n – 1) =
n + 4n – 2 ⇒ . T(n) = 5n – 2 .
Concluimos que el algoritmo es de O(n) en este caso.

Ejercicio 2
Suponga que a la versión tradicional de DFS se le agrega un procesamiento adicional que se
ejecuta al momento de visitar cada vértice. Calcule la expresión concreta para T(n) (y halle el orden
del algoritmo) en cada uno de los cinco casos del ejercicio anterior, suponiendo los siguientes
procesamientos adicionales:

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
1
2 Análisis de Algoritmos – Solución Práctico 5

a) operación básica de O(1)

Solución:
El tiempo de ejecución de la recorrida está dado por | V | + 2 | A |. Debemos sumarle el tiempo
que consume el procesamiento adicional P(n) en cada uno de los n vértices. Por tanto, el
tiempo de ejecución total estará dado por T(n) = | V | + 2 | A | + n.P(n).
En este caso el procesamiento adicional está dado por P(n) = 1. Al ejecutarse n veces (una vez
en cada vértice), el tiempo de ejecución total queda T(n) = | V | + 2 | A | + n.

• G es un grafo completo ⇒ | V | + 2 | A | = n (ejercicio 1) ⇒ . T(n) = n + n .

2 2

2
El algoritmo sigue siendo de O(n ).

• G es un árbol ⇒ | V | + 2 | A | = 3n – 2 (ejercicio 1) ⇒ T(n) = 3n – 2 + n ⇒ . T(n) = 4n – 2 .

El algoritmo sigue siendo de O(n).

• G es como un grafo completo pero además tiene un lazo en cada nodo ⇒ | V | + 2 | A | =

2 2 2
n + 2n (ejercicio 1) ⇒ T(n) = n + 2n + n ⇒ . T(n) = n + 3n .
El algoritmo sigue siendo de O(n2).

• G es como un árbol pero además tiene un lazo en cada nodo ⇒ | V | + 2 | A | = 5n – 2

(ejercicio 1) ⇒ T(n) = 5n – 2 + n ⇒ . T(n) = 6n – 2 .
El algoritmo sigue siendo de O(n).

• G es un grafo aplanable, sin lazos y con la mayor cantidad de aristas posible ⇒ | V | + 2 | A | =

7n – 12 (ejercicio 1) ⇒ T(n) = 7n – 12 + n ⇒ . T(n) = 8n – 12 .
El algoritmo sigue siendo de O(n).

b) for (int i=0; i < n; i++)

operación básica de O(1)
Solución:
El tiempo de ejecución de la recorrida está dado por | V | + 2 | A |. Debemos sumarle el tiempo
que consume el procesamiento adicional P(n) en cada uno de los n vértices. Por tanto, el
tiempo de ejecución total estará dado por T(n) = | V | + 2 | A | + n.P(n).
En este caso el procesamiento adicional está dado por P(n) = n. Al ejecutarse n veces (una vez
2
en cada vértice), el tiempo de ejecución total queda T(n) = | V | + 2 | A | + n .

• G es un grafo completo ⇒ | V | + 2 | A | = n (ejercicio 1) ⇒ T(n) = n + n ⇒ . T(n) = 2n .

2 2 2 2

2
El algoritmo sigue siendo de O(n ).

• G es un árbol ⇒ | V | + 2 | A | = 3n – 2 (ejercicio 1) ⇒ T(n) = 3n – 2 + n ⇒ . T(n) = n + 3n – 2 .

2 2

2
El algoritmo ahora pasa de O(n) a ser de O(n ).

• G es como un grafo completo pero además tiene un lazo en cada nodo ⇒ | V | + 2 | A | =

2 2 2 2
n + 2n (ejercicio 1) ⇒ T(n) = n + 2n + n ⇒ . T(n) = 2n + 2n .
2
El algoritmo sigue siendo de O(n ).

• G es como un árbol pero además tiene un lazo en cada nodo ⇒ | V | + 2 | A | = 5n – 2

(ejercicio 1) ⇒ T(n) = 5n – 2 + n2 ⇒ . T(n) = n2 + 5n – 2 .
2
El algoritmo ahora pasa de O(n) a ser de O(n ).

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
2
Análisis de Algoritmos – Solución Práctico 5 3

• G es un grafo aplanable, sin lazos y con la mayor cantidad de aristas posible ⇒ | V | + 2 | A | =

2 2
7n – 12 (ejercicio 1) ⇒ T(n) = 7n – 12 + n ⇒ . T(n) = n + 7n – 12 .
2
El algoritmo ahora pasa de O(n) a ser de O(n ).
c) for (int i=1; i < n; i = 2*i)
operación básica de O(1)
Solución:
El tiempo de ejecución de la recorrida está dado por | V | + 2 | A |. Debemos sumarle el tiempo
que consume el procesamiento adicional P(n) en cada uno de los n vértices. Por tanto, el
tiempo de ejecución total estará dado por T(n) = | V | + 2 | A | + n.P(n).
En este caso el procesamiento adicional está dado por P(n) = log (n). Al ejecutarse n veces (una
vez en cada vértice), el tiempo de ejecución total queda T(n) = | V | + 2 | A | + n.log (n).

• G es un grafo completo ⇒ | V | + 2 | A | = n (ejercicio 1) ⇒ . T(n) = n + n.log (n).

2 2

2
El algoritmo sigue siendo de O(n ).

• G es un árbol ⇒ | V | + 2 | A | = 3n – 2 (ejercicio 1) ⇒ . T(n) = 3n – 2 + n.log (n) .

El algoritmo ahora pasa de O(n) a ser de O(n.log (n)).

• G es como un grafo completo pero además tiene un lazo en cada nodo ⇒ | V | + 2 | A | =

2 2
n + 2n (ejercicio 1) ⇒ . T(n) = n + 2n + n.log (n) .
2
El algoritmo sigue siendo de O(n ).

• G es como un árbol pero además tiene un lazo en cada nodo ⇒ | V | + 2 | A | = 5n – 2

(ejercicio 1) ⇒ . T(n) = 5n – 2 + n.log (n) .
El algoritmo ahora pasa de O(n) a ser de O(n.log (n)).

• G es un grafo aplanable, sin lazos y con la mayor cantidad de aristas posible ⇒ | V | + 2 | A | =

7n – 12 (ejercicio 1) ⇒. T(n) = 7n – 12 + n.log (n) .
El algoritmo ahora pasa de O(n) a ser de O(n.log (n)).

Ejercicio 3
En el curso se vio que los algoritmos de DFS y BFS son en realidad el mismo algoritmo, a menos
de la secuencia auxiliar utilizada para almacenar los vértices durante la recorrida.
En este ejercicio se propone un diseño que permite implementar ambas recorridas para la
estructura de matriz de adyacencia utilizando el mismo código fuente y cambiando únicamente la
secuencia auxiliar utilizada durante la recorrida.
La secuencia auxiliar utilizada es un Stack para el caso de DFS y una Queue para el caso de BFS.
La inserción y la eliminación en el stack se realizan siempre por el mismo extremo, mientras que en
la queue la inserción se realiza por un extremo y la eliminación se realiza por el otro.

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
3
4 Análisis de Algoritmos – Solución Práctico 5

GRAFO << abstract >>

- matriz: int [][] Secuencia
1 1
- n: int # lista: LinkedList <Integer>
- secAux: Secuencia
+ Secuencia ( )
+ Grafo (n: int) + insert (n: Integer): void
+ setSecuencia (s: Secuencia): void + front ( ): Integer
+ addArista (v: int, w: int): void + remFront ( ): void
+ recorrida (inicial: int): void + empty ( ): boolean

El método recorrida de la clase Grafo

implementa, de forma puramente iterativa
la recorrida cuyo comportamiento (DFS o
BFS) dependerá de la secuencia auxiliar
(Stack o Queue) que esté instanciada al STACK QUEUE
momento de la ejecución
+ insert (n: Integer): void + insert (n: Integer): void

a) Implemente en Java el diseño propuesto. Puede agregar operaciones auxiliares privadas a la

clase Grafo si le resulta de utilidad.
Solución:
public abstract class Secuencia
{
protected LinkedList <Integer> lista;
public Secuencia ()
{
lista = new LinkedList <Integer> ();
}
public abstract void insert (Integer n);
public Integer front ()
{
return lista.getFirst();
}
public void remFront ()
{
lista.removeFirst();
}
public Boolean empty ()
{
return (lista.size() == 0);
}
}
public class Stack extends Secuencia
{
public void insert (Integer n)
{
lista.addFirst (n);
}
}
Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
4
Análisis de Algoritmos – Solución Práctico 5 5

public class Queue extends Secuencia

{
public void insert (Integer n)
{
lista.addLast (n);
}
}
public class Grafo
{
private int [][] matriz;
private int n;
private Secuencia secAux;
public Grafo (int n)
{
this.n = n;
this.secAux = null;
for (int i = 0; i < n; i++)
for (int j = 0; i < n; i++)
matriz [i][j] = 0;
}
public void setSecuencia (Secuencia s)
{
this.secAux = s;
}
public void addArista (int v, int w)
{
matriz [v][w] = 1;
matriz [w][v] = 1;
}
public void recorrida (int inicial)
{
boolean [] visitado = new boolean [n];
for (int i = 0; i < n; i++)
visitado[i] = false;
secAux.insert (inicial);
while (!secAux.empty())
{
int actual = secAux.front();
secAux.remFront();
if (!visitado [actual])
{
visitado [actual] = true;
System.out.print (actual);
for (int j = 0; j < n; j++)
{
if ((matriz [actual][j] == 1) && (!visitado [j]))
secAux.insert (j);
}
}
}
}
}

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
5
6 Análisis de Algoritmos – Solución Práctico 5

Ejercicio 4
Dado el grafo de la figura:

12 3
0 1 2
16 14 6 1
4

13 10
3 4 5
5 15
7 9 8

2 11
6 7 8

a) Encuentre un árbol de cubrimiento aplicando el algoritmo de DFS comenzando en el vértice 0

y eligiendo los vecinos siempre en orden creciente de numeración.
Solución: 12 3
0 1 2

13 10
3 4 5

2 11
6 7 8

b) Ídem a la parte (a) pero ahora aplicando el algoritmo de BFS.

Solución:
12 3
0 1 2

14 6
4

3 4 5
5
7 8

6 7 8

e) Encuentre los caminos más cortos desde el vértice 0 hacia todos los demás vértices aplicando
el algoritmo de Dijkstra.
Solución:
0 1 2 3 4 5 6 7 8
distancia ∞ 12 ∞ 15 4 ∞ 17 ∞ 24 18 16 ∞ 11 ∞ 9 ∞ 20
desde ∞ 0 ∞ 1 0 ∞ 3 ∞ 7 1 2 ∞ 3 ∞ 3 ∞ 7

Caminos más cortos: 0, 1 (costo 12) – 0, 1, 2 (costo 15) – 0, 3 (costo 4) – 0, 3, 4 (costo 17) –
0, 1, 2, 5 (costo 16) – 0, 3, 6 (costo 11) – 0, 3, 7 (costo 9) – 0, 3, 7, 8 (costo 20)

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
6
Análisis de Algoritmos – Solución Práctico 5 7

Ejercicio 5
En este ejercicio calcularemos el orden de la implementación del algoritmo de Prim para matriz de
adyacencia visto en el curso.
a) Estime la expresión para T(n) de cada uno de los algoritmos auxiliares inicializar y
procesarVerticeInicial.
Solución:
En el algoritmo inicializar el bloque for asigna n celdas en los tres arreglos auxiliares, por
lo que se estima T(n) = 3n.
En el algoritmo procesarVerticeInicial el bloque for recorre la fila correspondiente al
vértice inicial, por lo que se estima T(n) = n.
b) Estime la expresión para T(n) del algoritmo auxiliar verticeMenorDistancia.
Solución:
El algoritmo verticeMenorDistancia recorre el arreglo a partir de la 2º celda buscando la
menor distancia almacenada, por lo que se estima T(n) = n – 1.
c) Estime la expresión para T(n) del bloque for que procesa los restantes vértices, tomando en
cuenta la parte (b) y el bloque for interior.
Solución:
for exterior se ejecuta (n – 1) veces.
{
T(n) = (n – 1).(2n – 1)
verticeMenorDistancia: T(n) = n – 1 (2n – 1) veces
for interior se ejecuta n veces
}
(por regla de la secuencia) (por regla de la anidación)

2
T(n) = (n – 1).(2n – 1) ⇒ T(n) = 2n – 3n + 1 (tiempo de ejecución del bloque for exterior)
d) En base a las partes anteriores, estime la expresión para T(n) de todo el algoritmo y calcule
finalmente su orden.
Solución:
algoritmo inicializar → T1(n) = 3n
algoritmo procesarVerticeInicial → T2(n) = n
for exterior se ejecuta (n – 1) veces.
{ verticeMenorDistancia: T(n) = n - 1 T3(n) = 2n2 – 3n + 1
for interior se ejecuta n veces
}
Por regla de la secuencia, tenemos que el tiempo de ejecución total del algoritmo de Prim está
dado por T(n) = T1(n) + T2(n) + T3(n) = 3n + n + (2n2 – 3n + 1) ⇒ T(n) = 2n2 + n + 1.
2
Concluimos que el algoritmo de Prim es de O(n ) en el peor caso.
e) ¿Hay diferencias entre el peor y el mejor caso del algoritmo de Prim? ¿Influye la cantidad de
aristas de G en el tiempo de ejecución? ¿Cambiaría la eficiencia si se trabaja con listas de
adyacencia? Explique brevemente sus respuestas.
Solución:
No hay diferencias entre el peor y el mejor caso del algoritmo Prim. Es un algoritmo de caso
único, cada una de sus iteraciones se ejecuta siempre una cantidad fija de veces. Por lo tanto,
la cantidad de aristas del grafo no influye para nada en el tiempo de ejecución.

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
7
8 Análisis de Algoritmos – Solución Práctico 5

Si se trabaja con listas de adyacencia, la operación darCosto de una arista deja de ser de
O(1), mientras que el resto del algoritmo se mantiene igual. Por lo tanto, la eficiencia del
algoritmo resulta sensiblemente menor si se trabaja con listas de adyacencia.

Ejercicio 6
En este ejercicio calcularemos el orden de la implementación optimizada del algoritmo de Kruskal
para matriz de adyacencia visto en el curso. Lo haremos para el caso particular en que G es un
grafo completo de n vértices.
d) Repita las partes anteriores ahora para el caso particular en que G es un árbol de n vértices.
Solución:
En el caso particular en que G es un árbol de n vértices, ya es en sí mismo un ACCM. Por lo
tanto, el bloque while (aristasAgregadas < n - 1) se ejecuta n-1 veces, ya que hay
exactamente n-1 aristas, todas las cuales serán agregadas al ACCM. Tenemos entonces que:
La invocación a Merge Sort ordena las (n-1) aristas del arreglo en tiempo T1(n) = (n - 1).log (n - 1).
El bloque while se ejecuta n-1 veces, siendo de O(1) todas las instrucciones que se ejecutan
dentro de él. Estimamos su tiempo de ejecución en T2(n) = n – 1.

Invocación a mergeSort → T1(n) = (n - 1).log (n - 1)

while (aristasAgregadas < n - 1)
{ T2(n) = n - 1
Instrucciones de O(1) despreciables
}
Por regla de la secuencia, tenemos que el tiempo de ejecución total está dado por:
T(n) = T1(n) + T2(n) = (n - 1).log (n - 1) + (n - 1) ⇒ T(n) = (n - 1).(log (n - 1) + 1)
Concluimos que el algoritmo de Kruskal es de O (n.log (n)) cuando se aplica sobre un árbol.
e) ¿Hay diferencias entre el peor y el mejor caso del algoritmo de Kruskal? ¿Influye la cantidad
de aristas de G en el tiempo de ejecución? ¿Cambiaría la eficiencia si se trabaja con listas de
adyacencia? Explique brevemente sus respuestas y compárelas con las del algoritmo de Prim
Solución:
Sí hay diferencias entre el peor y el mejor caso del algoritmo de Kruskal. El mejor caso se
produce cuando la cantidad de aristas descartadas por generar ciclos es nula. El peor caso se
produce cuando la cantidad de aristas descartadas por generar ciclos es máxima.
Cuando el grafo tiene una alta cantidad de aristas, el tiempo de ejecución tiende a ser de orden
2
O (n .log (n)) en el peor caso. Cuando el grafo tiene una baja cantidad de aristas, el tiempo de
ejecución tiende a ser de orden O (n.log (n)) en el peor caso.

Si se trabaja con listas de adyacencia, las operaciones addArista y borrarArista dejan de

ser de O(1), mientras que el resto del algoritmo se mantiene igual. Por lo tanto, la eficiencia del
algoritmo resulta sensiblemente menor si se trabaja con listas de adyacencia.

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
8
Análisis de Algoritmos – Solución Práctico 5 9

Ejercicio 7
Dados los siguientes grafos dirigidos:

0 1 2 0 1 2

3 4 5 3 4 5

6 7 8 6 7 8

a) Encuentre las componentes fuertemente conexas del primer grafo aplicando el algoritmo visto
en el curso.
Solución:

1º paso: Recorrer G según DFS, numerando los vértices en orden inverso al cual van siendo
visitados:
Recorrida: 1º) 0 2º) 1 3º) 2 4º) 5 5º) 7 6º) 8 7º) 3 8º) 6 9º) 4
Numeración: 9 8 7 6 5 4 3 2 1

2º paso: Obtener G’, invirtiendo las aristas de G: 3º paso: Recorrer G’, según DFS, empezando
por el vértice con numeración más alta y
0 1 2 tachando los números durante la recorrida.

Se obtienen las siguientes componentes

Fuertemente conexas de G:
3 4 5
1) vértices: 0, 3, 1, 4, 6
2) vértices: 2
6 7 8 3) vértices: 5, 8, 7

b) Encuentre una ordenación topológica para el segundo grafo aplicando el algoritmo visto en el
curso.
Solución:
0 1 2 3 4 5 6 7 8
gradosEnt 0 1 0 1 0 0 3 2 1 0 4 3 2 1 0 0 2 1 0 1 0

Queue auxiliar: 0, 3, 6, 1, 4, 2, 7, 8, 5
Ordenación topológica: 0, 3, 6, 1, 4, 2, 7, 8, 5

Ejercicio 8
Considerando que la función T(n) para los algoritmos DFS y BFS están dadas por T(n) = | V | + | A |
cuando el grafo es dirigido, calcule la expresión concreta para T(n) del algoritmo de ordenación
topológica en los siguientes casos y luego indique cuál es el orden del algoritmo en cada uno.
Hágalo suponiendo que los grados de entrada de los vértices han sido pre-calculados.

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
9
10 Análisis de Algoritmos – Solución Práctico 5

a) G es un grafo semi-completo y sin ciclos (esto es, existe una arista de ida pero no una de
regreso entre todo par de vértices)..
Solución:

Calcular grados de entrada → no influye, se asumen pre-calculados

Encolar vértices con grado de entrada 0 → T1(n) = n
while (!queue.empty())
{ T2(n) = | V | + | A | (variante de BFS)
(variante de BFS)
}
Por regla de la secuencia, tenemos que el tiempo de ejecución total está dado por:
T(n) = T1(n) + T2(n) = n + | V | + | A | = n + n + | A | ⇒ T(n) = 2n + | A |
Dado que G es un grafo semi-completo, se cumple que | A | = n (n – 1) / 2. Tenemos entonces
2 2
que T(n) = 2n + n (n – 1) / 2 = (4n + (n – n)) / 2 ⇒ . T(n) = (n + 3n) / 2 .
2
Concluimos que el algoritmo es de O(n ) en este caso.
b) G es un árbol.
Solución:
De acuerdo con la parte (a), el tiempo de ejecución total está dado por: T(n) = 2n + | A |
Dado que G es un árbol, se cumple que | A | = n – 1. Tenemos entonces que
T(n) = 2n + (n – 1) ⇒ . T(n) = 3n – 1 . Concluimos que el algoritmo es de O(n) en este caso.
c) G es un grafo aplanable sin lazos y con la mayor cantidad de aristas posible.
Solución:
De acuerdo con la parte (a), el tiempo de ejecución total está dado por: T(n) = 2n + | A |
Dado que G es grafo aplanable sin lazos y con la mayor cantidad de aristas posible, de acuerdo
con el ejercicio 1 se cumple que | A | = 3n – 6.
Tenemos entonces que T(n) = 2n + (3n – 6) ⇒ . T(n) = 5n – 6 .
Concluimos que el algoritmo es de O(n) en este caso.
d) Repita las partes anteriores para el algoritmo de determinación de componentes fuertemente
conexas, suponiendo que el grafo G’ con las aristas invertidas ha sido pre-construido.
Solución:

Recorrida de G en DFS numerando vértices → T1(n) = | V | + | A |

Inversión de artistas de G (grafo G’) → no influye, se asume pre-construido
Recorrida de G’ en DFS tachando números → T2(n) = | V | + | A |
Por regla de la secuencia, tenemos que el tiempo de ejecución total está dado por:
T(n) = T1(n) + T2(n) = | V | + | A | + | V | + | A | = n + | A | + n + | A | ⇒ T(n) = 2n + 2 | A |

• En el caso en que G es un grafo semi-completo, se cumple que | A | = n (n – 1) / 2.

2 2
Tenemos entonces que T(n) = 2n + 2.(n (n – 1) / 2) = 2n + (n – n) ⇒ . T(n) = n + n .
2
Concluimos que el algoritmo es de O(n ) en este caso.

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
10
Análisis de Algoritmos – Solución Práctico 5 11

• En el caso en que G es un grafo árbol, se cumple que | A | = n – 1.

Tenemos entonces que T(n) = 2n + 2(n – 1) = 2n + 2n – 2 ⇒ . T(n) = 4n – 2 .
Concluimos que el algoritmo es de O(n) en este caso.

• En el caso en que G es grafo aplanable sin lazos y con la mayor cantidad de aristas
posible, de acuerdo con el ejercicio 1 se cumple que | A | = 3n – 6.
Tenemos entonces que T(n) = 2n + 2(3n – 6) = 2n + 6n – 12 ⇒ . T(n) = 8n – 12 .
Concluimos que el algoritmo es de O(n) en este caso.

Ejercicio 9
Dado el siguiente grafo:
0 1 2 3

4 5 6 7

a) Encuentre todos sus ciclos hamiltonianos.

Solución:
Hay 8 ciclos hamiltonianos en total, los cuales mostramos a continuación:

0 1 2 3 0 1 2 3

4 5 6 7 4 5 6 7

0 1 2 3 0 1 2 3

4 5 6 7 4 5 6 7

0 1 2 3 0 1 2 3

4 5 6 7 4 5 6 7

0 1 2 3 0 1 2 3

4 5 6 7 4 5 6 7

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
11
12 Análisis de Algoritmos – Solución Práctico 5

b) Encuentre todas sus cliques de 4 vértices.

Solución:
Hay, en total, 3 cliques de 4 vértices, las cuales mostramos a continuación:

0 1 1 2 2 3

4 5 5 6 6 7

Ejercicio 10
Se quiere implementar un algoritmo con el menor orden posible que, dados un grafo y una
secuencia de vértices, verifique si la misma constituye o no un ciclo hamiltoniano en el grafo.
b) Repita la parte anterior, pero ahora usando listas de adyacencia.
Solución:

La implementación del algoritmo es exactamente la misma que para la versión con matriz de
adyacencia, con la diferencia de que la operación invocada existeArista, que chequea la
existencia de una arista entre dos vértices dados, internamente opera ahora sobre listas de
adyacencia.
En matriz de adyacencia, la operación existeArista es de O(1), mientras que en listas de
adyacencia debe recorrer la lista de adyacencia correspondiente a uno de los extremos. Por lo
tanto, su tiempo de ejecución ahora depende del largo de la lista (lo que no ocurre en la matriz).
Para esta parte, realizaremos el análisis detallado únicamente para el caso en que el grafo es
completo.
El tamaño de la entrada sigue siendo n = cantidad de vértices. El mejor y el peor caso se
mantienen igual que en la versión para matriz de adyacencia. La operación básica sigue siendo
la invocación a existeArista, cuyo tiempo de ejecución es T(n) = n – 1 para G completo.
Suponiendo una iteración que se ejecuta n veces (recorre la secuencia de n vértices), dentro de
la cual se invoca a existeArista, por regla de la anidación tenemos que el tiempo de
2
ejecución total del algoritmo está dado por T(n) = n(n – 1) = n – n.
2
Concluimos entonces que el algoritmo es de O(n ) para el caso en que el grafo es completo.
c) ¿Es relevante para este algoritmo la representación utilizada para el grafo? Explique.
Solución:

Sí, es relevante, dado que en matriz de adyacencia la operación existeArista es de O(1),

mientras que en listas de adyacencia depende del largo de la lista de adyacencia. Por lo tanto,
el algoritmo resulta más eficiente en matriz de adyacencia que en listas de adyacencia.

Ejercicio 11
Dados los siguientes grafos, determine cuáles de ellos son isomorfos y cuáles no lo son. En caso
afirmativo, encuentre una función biyectiva que transforme uno en el otro preservando las
adyacencias. En caso negativo, demuestre por qué no pueden ser isomorfos.

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
12
Análisis de Algoritmos – Solución Práctico 5 13

b c i
0 1 2
a d ii iii
3 4 5
iv v vi
f e

Solución:

Solamente el primer y el tercer grafo son isomorfos. La correspondencia entre vértices es la

siguiente: a → 0, b → 1, c → 3, d → 5, e → 4, f → 2.
La correspondencia entre aristas es la siguiente:
{a, b} → {0, 1} {a, e} → {0, 4} {b, d} → {1, 5} {c, d} → {3, 5} {d, e} → {5, 4}
{a, c} → {0, 3} {a, f } → {0, 2} {b, f } → {1, 2} {c, e} → {3, 4} {d, f } → {5, 2}
El segundo grafo no puede ser isomorfo a los otros dos porque, si bien los tres grafos tienen la
misma cantidad de vértices (6) y de aristas (10), el segundo grafo posee un vértice de grado 2
(el i), mientras que en los otros dos grafos no hay ningún vértice de grado 2.

Ejercicio 12
Para hacer este ejercicio, busque información en fuente/s confiable/s, citando en cada caso la/s
referencia/s consultada/s. No se pretenden demostraciones formales para este ejercicio. Un ciclo
euleriano en un grafo no dirigido es un ciclo simple que pasa una sola vez por todas y cada una de
las aristas del grafo.
a) Dibuje el grafo completo de 5 vértices y encuentre un ciclo euleriano en dicho grafo.
Solución:

1 Un posible ciclo euleriano es:

0, 2, 3, 1, 4, 0, 1, 2, 4, 3, 0

0 2

3 4

b) Investigue en qué consiste el problema de los Puentes de Königsberg y formúlelo en términos

de la teoría de grafos.
Solución:

Partiendo de un punto cualquiera

de la ciudad de Königsberg ¿es
posible retornar a él pasando por
cada puente una sola vez?
Es decir, ¿existe un ciclo
euleriano en el grafo
correspondiente?

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
13
14 Análisis de Algoritmos – Solución Práctico 5

c) El problema de saber si un grafo contiene o no un ciclo euleriano, ¿es tratable o intratable?

Fundamente su respuesta. ¿Qué orden tiene el mejor algoritmo conocido que lo resuelve?
Solución:
El problema de saber si un grafo contiene o no un ciclo euleriano es un problema tratable. La
condición necesaria y suficiente para la existencia de un ciclo euleriano en un grafo conexo es
que todos sus vértices posean grado par. Esta condición puede chequearse mediante un
algoritmo de orden polinómico.
d) Ídem a la parte (c), pero ahora para el problema de encontrar un ciclo euleriano en el grafo.
Solución:
El problema de encontrar un ciclo euleriano en un grafo conexo es también un problema
tratable. El algoritmo de Fleury permite encontrar un ciclo euleriano en un grafo conexo y tiene
orden polinómico. La precondición para poder encontrarlo es que todos los vértices del grafo
sean de grado par.

Este material es de uso exclusivo para los cursos impartidos por Universidad de la Empresa
14