UPDS
INGENIERÍA
FUNDAMENTOS DE MATEMÁTICAS
PRÁCTICA GRAFOS
Carlos Caballero Rosembluth
______________________________________________________________________
1. Construir el grafo que tiene como vértices las posibles parejas de números entre 1 y 5,
unidos por una arista si las correspondientes parejas no comparten ningún número.
2. Escribir la matriz de adyacencia de los siguientes grafos y decidir si son o no regulares:
(a) El grafo bipartido completo Kn,m.
(b) El grafo cubo Qn, cuyos vértices son los números binarios de n cifras, unidos por una
arista cuando difieren sólo en una cifra.
3. Dado el grafo G = (V,A) con V = {1,...,6} y A = {{1,2},{1,5},{1,6},
{2,3},{2,4},{2,5},{3,4},{3,6},{4,5},{5,6}}, se pide:
(a) Determinar si G es plano y, si se puede, dibujar una representación plana de G con
aristas rectas.
(b) Obtener la matriz de adyacencia de G.
(c) Determinar si el subgrafo G0 de vértices V 0 = {1,2,3,5} es conexo, usando su matriz de
adyacencia.
(d) Determinar cuántos caminos de longitud 3 hay en G0 entre los vértices 2 y 5.
(e) Determinar si G es euleriano o posee algún camino euleriano.
(f) Si añadimos un séptimo vértice, ¿a cuáles de los seis primeros puede estar unido para
que el nuevo grafo sea euleriano? Hacerlo y construir un circuito euleriano usando el
algoritmo de Fleury.
(g) Determinar si el grafo G es hamiltoniano. Si lo es, buscar un circuito de Hamilton.
(h) Obtener un árbol generador del grafo G.
4. Suponiendo que en el grafo del ejercicio 2 las aristas tienen pesos c12 = 1,c15 = 3,c16 = 4,c23
= 2,c24 = 3,c25 = 2,c34 = 3,c36 = 1, c45 = 4,c56 = 5, se pide:
(a) Obtener un árbol generador minimal de G.
(b) Obtener un camino de peso mínimo entre 2 y 6.
Carlos Caballero Rosembluth pág. 1
UPDS
INGENIERÍA
FUNDAMENTOS DE MATEMÁTICAS
PRÁCTICA GRAFOS
Carlos Caballero Rosembluth
______________________________________________________________________
5. Suponiendo que en el grafo del ejercicio 2 las aristas están dirigidas
(1,2),(1,4),(2,3),(2,5),(3,4),(3,5),(4,6),(5,3),(6,2),(6,5), se pide:
(a) Obtener la matriz de adyacencia del grafo orientado.
(b) Usando ´esta, determinar cuántos caminos hay entre 3 y 6, y de qué longitudes. ¿Y
entre 6 y 3?
6. El grafo de la figura representa las distancias entre los distintos edificios de una
universidad y los caminos entre ellos. Se pide:
(a) Decidir si un vigilante puede salir de A, recorrer todos los edificios una sola vez y
volver al punto de partida. ¿Y desde B?
(b) Encontrar un recorrido de longitud mínima que visite todos los edificios y regrese al
punto de partida.
(c) Encontrar un árbol generador de peso mínimo.
A
5 4
5 8
B C
2
2 5
3 3
D 2 E
7. La red de transporte entre las tiendas Hipermaxi en Bolivia se representa por el siguiente
grafo, que incluye los costes de cada envío entre dos tiendas (en miles de Bolivianos):
B 6 F
4 6 D
4 2
6
A 4 7 G
1 4 6
3 6 10
C 5 E
Se pide encontrar la ruta de transporte de coste mínimo entre A y G:
(a) Si las aristas no estuvieran dirigidas.
Carlos Caballero Rosembluth pág. 2
UPDS
INGENIERÍA
FUNDAMENTOS DE MATEMÁTICAS
PRÁCTICA GRAFOS
Carlos Caballero Rosembluth
______________________________________________________________________
(b) En el grafo dirigido que se da.
8. Queremos conectar 6 ordenadores en red usando 9 cables, de manera que cada ordenador
esté conectado a otros 3. ¿Es posible? ¿Se puede hacer de varias formas? ¿Y 7 ordenadores
usando 10 cables?
9. Cinco amigos A,B,C,D,E quieren comunicar sus ordenadores para jugar en red. Los costes
conocidos, en segundos, de enviar datos entre sus ordenadores son:
A B C D
B 3
C 2
D 6
E 5 3 1
Decidir, aplicando el algoritmo correspondiente, cmo deben estar conectados los ordenadores
para que A y C tarden lo menos posible en comunicarse.
Carlos Caballero Rosembluth pág. 3
