Universidad de la Frontera
Facultad de Ingenierı́a y Ciencias Temuco, Abril 14 de 2022
Departamento de Matemática y Estadı́stica
Tarea Grupal 2
Matemática para la computación I (IME046)
Profesor: Vı́ctor Vargas.
Nombre: Carrera:
1. Siete ciudades a, b, c, d, e, f y g están conectadas por un sistema de autopistas como sigue:
I-22 va de a a c pasando por b.
I-33 va de c a d y entonces pasa por b y continúa hacia f .
I-44 va de d por e hacia a.
I-55 va de f a b, pasando por g y
I-66 va de g a d.
Entonces
a) Use los vértices para las ciudades y las aristas dirigidas para los tramos de autopista que las
unen y dibuje un grafo que modele la situación.
b) Enumere los caminos simples de g a a
c) ¿Cuál es el menor número de segmentos de autopista que tendrı́an que cerrarse para inte-
rrumpir el paso de b a d?
d) ¿Es posible salir de la ciudad c y regresar a ella, visitando una sola vez las otras ciudades?
e) ¿Es posible comenzar en alguna ciudad y viajar por todas las autopistas exactamente una
vez?
2. Dados V = {1, 2, 3, 4, 5} y E = {(1, 2), (2, 5), (3, 2), (3, 4), (5, 1), (5, 4)}:
a) Graficar G = (V, E).
b) Escribir la matriz de adyacencia.
c) Verifique que en la matriz de adyacencia la suma por filas es g + (i).
¿A qué es igual la suma por columnas?
d) Escribir la matriz de incidencia.
e) Verifique que en la matriz de incidencia la suma por columnas es cero.
¿A qué es igual la suma por filas?
3. La siguiente es una matriz de adyacencia de un grafo:
0 1 1 0
1 0 2 1
1 2 0 1
0 1 1 1
Responda las siguientes preguntas, analizando la matriz:
a) Cuántos caminos de longitud 2 existen de v2 a v3 ?
b) Cuántos caminos de longitud 2 existen de v3 a v4 ?
c) Cuántos caminos de longitud 3 existen de v1 a v4 ?
d) Cuántos caminos de longitud 3 existen de v2 a v3 ?
4. a) Dé dos ejemplos de grafos que tengan circuitos de Euler, pero no circuitos hamiltonianos.
b) Dé dos ejemplos de grafos que tengan circuitos hamiltonianos, pero no circuitos de Euler.
c) Dé dos ejemplos de grafos que tengan circuitos de Euler, y circuitos hamiltonianos, pero que
no sean los mismos.
5. Considere el grafo dado por la siguiente instrucción
G3 = GraphData[”IcosahedralGraph”]
Determine el número de vértices y de aristas que tiene el grafo.
Determine la matriz de adyacencia y calcule g + (V 3) donde V 3 corresponde al tercer vértice
según la enumeración de Mathematica.
Determine la cantidad de caminos distintos de longitud 8, que conectan el vértice v3 con el
vértice v5 .
Determine la matriz de incidencia.
Determine si el grafo tiene un ciclo Euleriano.
Determine si el grafo tiene un camino Hamiltoniano.
6+6+6+6+6=30 puntos
AYUDA:
El software Mathematica tiene implementadas varias rutinas que nos facilitarán el estudio de grafos,
además de contener varias grafos clásicos ya implementados.
Por ejemplo: CompleteGraph[6] ó CycleGraph[7] ó WheelGraph[7] producen respectivamente los grafos:
Ahora usando los comandos de Mathematica podemos obtener mucha información de cada uno de
ellos,como por ejemplo,
Si el grafo es simple: SimpleGraphQ
(a) Grafo completo 6 (b) Grafo cı́clico 7 (c) Grafo de rueda 7
Figura 1: Distintos grafos
La cantidad de aristas: EdgeCount
La cantidad de vértices: VertexCount
La relaciones entre los vértices: EdgeList
La matriz de adyacencia: AdjacencyMatrix
La matriz de incidencia: IncidenceMatrix
Ası́ como también existen rutinas que nos permiten:
Determinar si dos grafos son isomorfos: IsomorphicGraphQ
Buscar ciclos eulerianos: FindEulerianCycle
Buscar caminos hamiltonianos: FindHamiltonianPath
Por ejemplo: en el grafo rueda de orden 7 tenemos que:
g3 := WheelGraph[7]
M = AdjacencyMatrix[g3]
MatrixForm[M]
0 1 1 1 1 1 1
1 0 1 0 0 0 1
1 1 0 1 0 0 0
1 0 1 0 1 0 0
1 0 0 1 0 1 0
1 0 0 0 1 0 1
1 1 0 0 0 1 0
Si queremos calcular potencias podemos usar el siguiente comando:
MatrixPower[M, 3] // MatrixForm
12 10 10 10 10 10 10
10 4 7 4 6 4 7
10 7 4 7 4 6 4
10 4 7 4 7 4 6
10 6 4 7 4 7 4
10 4 6 4 7 4 7
10 7 4 6 4 7 4
Que corresponde a la tercera potencia de la matriz M.
