Actividad 9. Grafos y Árboles

Actividad 9
PROGRAMA ACADÉMICO
LICENCIATURA Ingeniería en Tecnologías de la Información; Ingeniería Industrial

NOMBRE DE LA ASIGNATURA Matemáticas para computación CUATRIMESTRE 03
3
SEMANA CURSO BASE 11 NOMBRE DE LA ACTIVIDAD Grafos y Árboles

NOMBRE DEL TUTOR CENTRO
CONTENIDO
I. PROGRAMÁTICO COMPETENCIA A DESARROLLAR EN LA ACTVIDAD
Módulo IV: Teoría de grafos, árboles y redes Aplica los conceptos básicos de grafos para resolver
4.1. Elementos, características y componentes de problemas afines al área computacional e industrial,
los grafos. relacionados con el recorrido, búsqueda y ordenamiento en
4.1.1 Elementos, características y componentes grafos.
de los grafos.
4.1.1.1 Tipos de grafos.
4.1.2. Representación de los grafos.
4.1.2.1. Matemática.
4.1.2.2. Computacional.
4.1.3. Algoritmos de recorrido y búsqueda.
4.1.3.1. El camino más corto.
4.1.3.2. A lo ancho.
4.1.3.3. En profundidad.
4.2. Árboles.
4.2.1. Componentes y propiedades.
4.2.2. Clasificación por altura y numero de
nodos
4.2.3. Árboles con peso.
4.2.3.1. Recorrido de un árbol.
4.3. Redes.
4.3.1. Teorema de flujo máximo.
4.3.2. Teorema de flujo mínimo.
II. JUSTIFICACIÓN DE LA ACTIVIDAD

Los árboles son un tipo de grafo que sirve como herramienta útil en todos los problemas donde la información está
jerarquizada y para la toma de decisiones. Esta estructura es de bastante uso, incluso fuera del campo de la
informática; como ejemplo tenemos los árboles genealógicos, los árboles gramaticales, los organigramas, procesos
industriales, entre otros. En el campo de la informática se aplica la estructura de árboles en una amplia variedad de
problemas, por lo que lo convierte en una herramienta fundamental.
Los árboles conforman las estructuras no lineales y dinámicas de datos más importantes en la rama de la informática.
Se les llama Dinámicas ya que estas estructuras pueden cambiar en el momento en que se ejecuta el programa. Y son
no lineales debido a que a cada elemento pueden seguirle varios elementos. Los árboles son una estructura de
jerarquización sobre una colección de objetos o elementos a los cuales conocemos como nodos, uno de estos nodos
es conocido como raíz y de él parte toda la descendencia.
Aplicaciones que se han extendido al área de la Ingeniería Industrial, donde el análisis de procesos de producción y la
jerarquización de sus actividades es importante en el cumplimiento de metas y objetivos.
Página 1 de 3
III. MATERIAL Y/O EQUIPO NECESARIO
Software organizador gráfico
Documento con los ejercicios a resolver
Lápiz, borrador, hojas en blanco
Equipo de cómputo con conexión a internet
Software SimuladorDigital_095
IV. DESARROLLO DE LA ACTIVIDAD
Para cada uno de los siguientes ejercicios, incluir de manera clara y detallada el procedimiento que lo lleva a la
solución.
1. Responde las siguientes preguntas.

a) ¿Cuáles son las diferencias entre Árboles y Grafos?
b) ¿Cuáles son las Partes de los Grafos?
c) ¿Cuáles son las formas de representar a los Grafos?
d) ¿Qué significa el término Implementar en Programación?
e) ¿Cuáles son los tipos de Grafos?}
2. Esta es la copia del plano de una casa antigua que usted quiere visitar, y se le pide que, si es posible, se pueda
pasar por cada cuarto cruzando por cada puerta solo una vez.
(a) Determine si existe solución al problema.
(b) Si existe solución, muestre el recorrido, y si no, modifique el número de puertas de modo que exista solución.
3. A una fiesta de final de carrera acuden un grupo de amigos cuyos nombres son: Alicia (A), Berta (B), Celia
(C), Daría (D), Elena (E), Felipe (F), Gerardo (G), Hilario (H), Ignacio (I) y Jacobo (J). Cada chica solo
acepta bailar con un chico según el esquema siguiente: A acepta como pareja a F,G,H. B acepta como pareja
a G,I. C acepta como pareja a F,G. D acepta como pareja a G,I,J. E acepta como pareja a F,G,H.
a) Dibujar el grafo que modela la situación anterior, representando cada persona por un vértice.
b) .Es posible conseguir que, a la vez, cada chica baile con un chico de los que acepta como pareja de baile?
En caso afirmativo dar dichas parejas de baile. En caso contrario, encontrar el número máximo de parejas
de baile posibles cumpliendo las condiciones indicadas.
4. Un operador por cable que aúna televisión y teléfono quiere introducirse en una comarca que consta de 8
poblaciones, que etiquetamos alfabéticamente desde la A hasta la H. En la siguiente tabla cada entrada indica
el número de rollos de cable que se han de utilizar para conectar entre sí las poblaciones correspondientes a
su fila y columna, sobrentendiendo que los huecos vacíos corresponden a poblaciones que no pueden
conectarse directamente y que las entradas diagonales indican el número de rollos de cable que han de
utilizarse para cubrir el servicio en la población en cuestión.
Se pide:
Determinar, mediante el algoritmo apropiado, cuál es el número mínimo de

rollos de cable a utilizar y una ruta para conectar las poblaciones A y H, sin
necesidad de dar cobertura a las demás poblaciones por las que la línea pase.
Página 2 de 3
5. En el grafo de la figura siguiente, el árbol de camino mínimo con raíz en el vértice a (árbol enraizado en a que
contiene los caminos mínimos desde este vértice a todos los demás) verifica:
Una vez resueltos los ejercicios escanearlos e integrarlos en un archivo PDF
V. RESULTADOS
Portafolio de ejercicios resueltos
VI. CRITERIOS DE EVALUACIÓN (RÚBRICA)
VI. ANEXO TEÓRICO (OPCIONAL)

Se recomienda consultar, como recursos complementarios:
http://virtual.umng.edu.co/distancia/ecosistema/odin/odin_desktop.php?path=Li4vb3Zhcy9pbmdlbmllcmlhX2luZm9ybWF0aW
NhL2VzdHJ1Y3R1cmFfZGVfZGF0b3MvdW5pZGFkXzQv#slide_5
https://issuu.com/violetaleon8/docs/estructura_de_datos_2_grafos
https://www.cs.us.es/~jalonso/cursos/i1m-15/temas/tema-22.pdf
http://profe-alexz.blogspot.com/2012/01/teoria-de-grafos-y-ejercicios-resueltos_16.html
http://bibing.us.es/proyectos/abreproy/92106/fichero/TFG-2106-MARTINEZ.pdf
http://fernandojimenezmotte.com/mi-articulo/teoria-grafos-aplicaciones-la-fisica-quimica-arquitectura-trafico-vehicular-big-
data/
https://sci2s.ugr.es/sites/default/files/files/TutorialsAndPlenaryTalks/CharlaMineriaCienciogramasTAMIDA2013.pdf
VII BIBLIOGRAFÍA
 Jiménez, J. A. Matemáticas para la computación. Alfaomega. 2015. Tercera edición.
 Villalpando, J. F. Matemáticas discretas: Aplicaciones y ejercicios. Patria.2014. Primera edición.
 Espinosa, R. Matemáticas discretas. Alfaomega. 2010. Primera edición.
 Kenneth H. Rosen (2004) Matemática Discreta y Aplicaciones. España. McGraw-Hill.
Página 3 de 3

Actividad 9. Grafos y Árboles

Cargado por

Copyright:

Formatos disponibles

Actividad 9. Grafos y Árboles

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Actividad 9. Grafos y Árboles

Cargado por

Copyright:

Formatos disponibles

Actividad 9

LICENCIATURA Ingeniería en Tecnologías de la Información; Ingeniería Industrial

SEMANA CURSO BASE 11 NOMBRE DE LA ACTIVIDAD Grafos y Árboles

II. JUSTIFICACIÓN DE LA ACTIVIDAD

1. Responde las siguientes preguntas.

Determinar, mediante el algoritmo apropiado, cuál es el número mínimo de

Una vez resueltos los ejercicios escanearlos e integrarlos en un archivo PDF

VI. ANEXO TEÓRICO (OPCIONAL)

También podría gustarte