Actividad 7
Grafos
Actividad:
1. Definir que es un grafo
2. ¿ Que uso se le dan a los grafos?
3. ¿ Como se pueden clasificar los grafos?
4. ¿ Como se pueden representar los grafos?
¿Qué es un grafo?
En primera instancia debemos entender que es un grafo. Un grafo es una composición de un conjunto de objetos conocidos como nodos que se relacionan con otros nodos a través de un conjunto de conexiones conocidas como aristas.
Los grafos permiten estudiar las relaciones que existen entre unidades que interactúan con otras.
Podemos representar diversas situaciones o elementos con grafos. Estos son extraordinariamente útiles en situaciones complejas, es por esto, que es común conseguir la implementación de análisis de grafos en estudios de ciencias exactas, ciencias sociales y en aplicaciones informáticas.
Veamos a continuación los tipos de grafos que podemos implementar.
Propiedades principales de los grafos
Como ya hemos podido observar los grafos son un mundo por sí solo. Contienen un conjunto de características y dinámicas operativas que los convierten en una combinación interesante de datos e información de mucha utilidad para el mundo empresarial. Estos poseen algunas características interesantes que debemos conocer.
Entre las principales propiedades que posee un grafo está la adyacencia. La adyacencia se trata de la relación que existe entre dos aristas que comparten la conexión o relación con un vértice común. La incidencia, se trata simplemente de cuando un vértice está unido a otro.
También debemos entender las propiedades de ponderación de los grafos que corresponden a una función en la que cada arista es clasificada, cuantificada en diversos términos para aumentar la expresividad de modelo. Esta característica en especial es muy útil en estudios de optimización.
Por último pero no menos importante destacamos al etiquetado. Este trata de la distinción que se realiza en los vértices mediante una marca que los hace distinguible de otros.
Informacion tomada de: GraphEverywhere, E. (2020). Qué son los grafos. GraphEverywhere. https://www.grapheverywhere.com/que-son-los-grafos/
¿ Que uso se le dan a los grafos?
Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en toda las áreas de Ingeniería.Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.Para la administración de proyectos, utilizamos técnicas como técnica de revisión y evaluación de programas (PERT) en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red. Esta medida permite cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse gráficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el poder se transmite y a quiénes.Se emplea en problemas de control de producción, para proyectar redes de ordenadores, para diseñar módulos electrónicos modernos y proyectar sistemas físicos con parámetros localizados (mecánicos, acústicos y eléctricos).Se usa para la solución de problemas de genética y problemas de automatización de la proyección (SAPR). Apoyo matemático de los sistemas modernos para el procesamiento de la información. Acude en las investigaciones nucleares (técnica de diagramas de Feynman).5Los grafos son importantes en el estudio de la biología y hábitat. El vértice representa un hábitat y las aristas (o "edges" en inglés) representa los senderos de los animales o las migraciones. Con esta información, los científicos pueden entender cómo esto puede cambiar o afectar a las especies en su hábitat.
Informacion tomada de: GraphEverywhere, E. (2020). Qué son los grafos. GraphEverywhere. https://www.grapheverywhere.com/que-son-los-grafos/
¿ Como se pueden clasificar los grafos?
Existen definiciones que debemos conocer a profundidad, para entender las amplias posibilidades que nos brindan los grafos para estudiar relaciones entre diferentes tipos de información. En primer lugar debemos conocer es la composición exacta de un grafo y algunos conceptos asociados.
Un grafo en su totalidad es un par ordenado compuesto por vértices (v) y aristas (e); donde en la gran mayoría de los casos los vértices son de cuantificación finita. El número de vértices que componen al grafo, son las que conocemos como orden. Existe también el concepto de grado que se corresponde al número de arcos al que pertenecen de forma externa y en cuanto a las aristas también conseguimos el concepto de bucle que no es más que una arista relacionada de diversas formas con el mismo nodo.
Teniendo claros estos conceptos, podemos empezar a profundizar en las definiciones de tipos de grafos. Existen diversos tipos de grafos, analizaremos en esta oportunidad los esquemas de grafos más conocidos como son los grafos dirigidos, no dirigidos y etiquetados.
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.
Grafos etiquetados
Esta clasificación es denominada como grafos etiquetados o grafos dirigidos con pesos. Este tipo de grafos concentran aristas que pueden poseer información adicional donde podemos reflejar nombres, costos, valores u otros datos.
Estos grafos también son denominados como redes de actividad y el número asociado al arco, se le denomina factor de peso. Este grafo es el que más comúnmente utilizamos para representar situaciones de la vida real.
Informacion tomada de: GraphEverywhere, E. (2020). Qué son los grafos. GraphEverywhere. https://www.grapheverywhere.com/que-son-los-grafos/
4. ¿ Como se pueden representar los grafos?
Listas de aristas
Una forma sencilla de representar un grafo es solo una lista, o un arreglo, de \[ |E| \] aristas, a la que llamamos una lista de aristas. Para representar una arista, solo tenemos un arreglo de dos números de vértices, o un arreglo de objetos que contienen los números de vértices sobre los que inciden las aristas. Si las aristas tienen pesos, agrega ya sea un tercer elemento al arreglo o más información al objeto, que dé el peso de la arista. Como cada arista contiene solo dos o tres números, el espacio total para una lista de aristas es \[ \Theta(E) \]
Imagen tomadad de:kahanacademy. (s. f.). kahanacademy. https://es.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs
Matrices de adyacencia
Para un grafo con \[ |V| \] vértices, una matriz de adyacencia es una matriz de \[ |V| \times |V| \] de ceros y unos, donde la entrada en el renglón \[ i \] y la columna \[ j \] es 1 si y solo si la arista \[ (i, j) \] está en el grafo. Si quieres indicar un peso de la arista, ponlo en la entrada del renglón \[ i \], columna \[ j \] y reserva un valor especial (tal vez null) para indicar una arista ausente.
Imagen tomadad de:kahanacademy. (s. f.). kahanacademy. https://es.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs
Listas de adyacencia
Representar un grafo con listas de adyacencia combina las matrices de adyacencia con las listas de aristas. Para cada vértice \[ i \], almacena un arreglo de los vértices adyacentes a él. Típicamente tenemos un arreglo de \[ |V| \] listas de adyacencia, una lista de adyacencia por vértice
Informacion tomadad de:kahanacademy. (s. f.). kahanacademy. https://es.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs
A continuacion encontrara el taller solicitado en clase:
Recorrido en los grafos: