Actividad 7
Grafos
Actividad:
1. Definir que es un grafo
2. ¿Qué uso se le dan a los grafos?
3. ¿Cómo se pueden clasificar los grafos?
4. ¿Cómo se pueden representar los grafos?
1. Un grafo es una composición de un conjunto de objetos conocidos como vértices que se relacionan con otros vértices a través de un conjunto de conexiones conocidas como lados.
2. 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.
3. 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.
4. Representación por incidencia
- Lista de incidencia
El grafo está representado por un arreglo de aristas, identificadas por un de pares de vértices, que son los que conecta esa arista.
- Matriz de incidencia
El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).
Representación por adyacencia
- Listas de adyacencia
El grafo está representado por un arreglo de listas de adyacencia. Para un vértice i, la lista de adyacencia está formada por todos los vértices adyacentes a i. Puede construirse en tiempo lineal, y las inserciones pueden hacerse al principio de cada lista, con lo que se asegura tiempo constante.
- Matriz de adyacencia
Una matriz de adyacencia es una matriz M de dimensión n*n, en donde n es el número de vértices que almacena valores booleanos, donde M[i,j] es verdadero (o contiene un peso) si y solo si existe un arco que vaya del vértice i al vértice j. La inicialización llevaría un tiempo del O ( #(V2)).
Fuentes:
- Qué son los grafos. (2020, 10 marzo). GraphEverywhere. https://www.grapheverywhere.com/que-son-los-grafos/
- Representación de un grafo - mate_discretas_atilanocarrillo. (s. f.). Recuperado 28 de octubre de 2022, de https://sites.google.com/site/matediscretasatilanocarrillo/unidad-3-relaciones-graficos-y-arboles/representacion-de-un-grafo
Actividad 2
