Álgebra Lineal
Grafos y Dígrafos
Estudiantes: Areli Montserrat Cruz Zuñiga
Maximiliano Martínez García
Docente: M.C.Q. Marlén Ramírez Orizaga
Matemáticas III para la carrera de Ingeniería en Sistemas y Tecnologías Industriales
Universidad Politécnica de San Luis potosí
San Luis Potosí, SLP
Primer parcial del periodo de otoño 2023
4 de septiembre
Resumen
Este trabajo tiene la finalidad de presentar de manera clara y concisa la manera en la que dimos
solución a un problema asignado durante el parcial, para el cual tuvimos la oportunidad de
presentar soluciones mas graficas.
Empezando por el entendimiento del problema, donde desde un inicio se nos informó que este
seria resuelto por el método de grafos y dígrafos, por lo que la solución requerirá de una
representación gráfica del problema.
Para este trabajo describiremos cómo construimos esta estructura gráfica, cómo asignamos valores
a sus elementos, y cómo seleccionamos elementos clave para la resolución del problema. También
explicaremos cómo nuestro enfoque está directamente relacionado con la solución del problema
en cuestión.
Respectivamente nosotros mediante este documento explicaremos y desarrollaremos la solución
de un problema que se nos ha otorgado a mediados del parcial, explicando a detalle su método en
que consiste y como se relaciona en la elaboración de este, como ya se leyó en el título el método
que se utilizará para resolverlo será mediante grafos y dígrafos.
Introducción
Primeramente, para poder desarrollarlo necesitamos saber en qué consiste este método. En
palabras mas banales se necesita saber que significa un “Grafo y un Dígrafo”, independientemente
de que en su nombre podemos encontrar cierta similitud, son prácticamente lo mismo. Buscando su
definición, se le denomina “Grafo a un conjunto de nodos o vértices, y un conjunto de arcos o aristas, donde
cada arco o arista une un par de nodos”. (Joyanes Aguilar & Zahonero Martínez, 2008). Los grafos permiten
estudiar las relaciones que existen entre unidades que interactúan con otras. Por lo tanto, sus características
permiten muchas posibilidades en cuestión de análisis y solución de datos.
Ya teniendo conocimiento de esto podemos entender que un grafo esta normalmente representado de esta
manera:
Figura 1.- Representación visual de un grafo.
Existen diversos tipos de grafos, en los cuales cuentan con distintas características al resolverlo.
• Grafo dirigido
Un grafo dirigido conocido también como dígrafo consta de un conjunto de vértices y aristas donde cada
arista se asocia de forma unidireccional a través de una flecha con otro. Las aristas dependiendo de su salida
o ingreso reciben la calificación de entrante o saliente, la condición común, es que siempre tienen un destino
hacia un nodo.
• Grafo no dirigido
Los grafos no dirigidos son aquellos que constan un conjunto de vértices que están conectados a
un conjunto de aristas de forma no direccional. Esto significa que una arista puede indistintamente
recorrerse desde cualquiera de sus puntos y en cualquier dirección.
Desarrollo
El desarrollo planteado intentara ser tan claro como se pueda ser, Sin embargo, hay que
tomar en cuenta que aun para nosotros que somos gente considerablemente experimentada en el
campo, nos resultan difíciles algunos conceptos.
El problema planteado nos dice lo siguiente:
“Cinco personas se conectan todas mediante correo electrónico. Siempre que una de ellas escucha
un trozo de chismorreo interesante, lo envía por correo electrónico a alguien más en el grupo, de
acuerdo con la tabla que se muestra abajo
Tabla 1.Tabla de distribución respecto a la conversación.
Remitente Destinatarios
Ann Carla, Ehaz
Bert Carla, Dana
Carla Ehaz
Dana Ann, Carla
Ehaz Bert
1. A) Dibuje el dígrafo que modela “esta red de chismorreo” y encuentre a su matriz de
adyacencia A
Este paso es sencillo, se basa meramente en la interpretación grafica del dígrafo
planteado en la tabla e intentar traducirlo a un dígrafo gráfico.
Por lo que, tras una simple interpretación del problema, él dígrafo nos quedaría de la
siguiente manera :
.
Figura 1. Descripción grafica del funcionamiento de la “red de chismorreo”.
Entendamos que para poder pasar esto a una matriz de adyacencia, debemos comprender
el cómo funciona una matriz de adyacencia. A resumidas cuentas, una matriz de
adyacencia funciona de manera que, en un dígrafo, solo se contaran las conexiones
directas de un nexo con un nexo y en un solo sentido, por lo que, si interpretamos
siguiendo este patrón al dígrafo, se nos presenta de la siguiente manera:
Figura 2. Matriz de adyacencia correspondiente a la “red de chismorreo”.
B) Define un paso como el tiempo que una persona tarda en enviar un correo
electrónico a todos los de su lista. (Por lo tanto, en un paso, en un paso, el chisme va de Ann
tanto a Carla como a Ehaz.) Si Bert escucha un rumor ¿Cuántos pasos transcurrirán para que
todos los demás escuchen el rumor? ¿Qué calculo matricial revela esto?
La matriz adyacente solo revela a las personas que se enteraron del chisme tras un
solo paso, sin embargo si quisieramos saber quien se entero de el chisme a los 2 pasos, el
calculo matricial seria el siguiente:
Sin embar
c) Si Ann escucha un rumor ¿Cuántos pasos transcurrirán para que todos los demás escuchen
el rumor? ¿Que calculo matricial revela esto?
d) En general, Si A es la matriz de adyacencia de un dígrafo, ¿Cómo puede si el vértice i está
conectado al vértice j mediante una trayectoria (de cierta longitud)?
Para saber si el vértice i está conectado al vértice j a través de una trayectoria de cierta longitud
en un dígrafo utilizando la matriz de adyacencia:
1.- Eleva la matriz de adyacencia a la potencia deseada (la longitud máxima de la trayectoria
que buscas).
2.-Comprueba si la entrada correspondiente a (i, j) en la matriz resultante es mayor que cero.
Si es mayor que cero, significa que existe una trayectoria de esa longitud entre el vértice i y el
vértice j en el dígrafo.
Conclusión
El problema fue elaborado excitosamwnte y los resultado dieron a conocer que en efecto,
no tarda más de dos líneas en que todos estén enterados del tema, o del chisme en este caso. Con
una colaboración en cuestión a los datos obtenidos pudimos obtener su matriz y si determinante
para poder conocer esta información con mayor efectividad con los grafos.
Lista de referencias
Videos de YouTube
Amado, A. F. [@abelfloresamado2965]. (2021, April 9). P1 Aplicaciones de matrices GRafos y
digrafos. Matemática de los chismes. Recuperado de Youtube. P1 Aplicaciones de matrices
GRafos y digrafos. Matemática de los chismes
De TD, E. T. [@ElTallerDeTD]. (2022, July 16). Teoría de GRAFOS en INFORMÁTICA: Que
es un grafo, Tipos de Grafos, como representarlos y ejemplos. Recuperado de Youtube. Teoría de
GRAFOS en INFORMÁTICA: Que es un grafo, Tipos de Grafos, como representarlos y ejemplos
