ACTIVIDAD 7-GRAFOS
Actividad:
1. Definir que es un grafo
Los grafos son una composición de un grupo de objetos que se denominan nodos. Su estructura de datos no es lineal y tienen una naturaleza, en general dinámica. En ellos se almacenan diferentes elementos para procesar o conocer, cada uno con fines específicos. En algunos casos, se puede utilizar un vector para simbolizar un grafo. En este enfoque, cada nodo se puede representar mediante un índice en el vector, y los valores en el vector se usan para almacenar información adicional sobre cada nodo.
2. ¿Qué uso se le dan a los grafos?
Son utilizados para el modelado de problemas y como representación de las relaciones entre pares de nodos o vértices. Estos elementos son famosos por su capacidad de manejar altos volúmenes de datos y ser procesados de forma sencilla por motores de búsqueda.
Clic para ver la pagina de origen
3. ¿Cómo se pueden clasificar los grafos?
Hay diferentes tipos de grafos en el mundo de la programación, los básicos son los dirigidos y no dirigidos. También hay otras clasificaciones:
- Simple: es aquel que acepta una sola arista uniendo dos vértices diferentes. Esto es equivalente a decir que una arista diferente es la que une dos vértices específicos.
- Completo: si cada par de vértices se une por una arista.
- Multigrafo: Este acepta más de una arista entre dos vértices y estas aristas se llaman múltiples o lazos
- Etiquetado: son aquellos que se ha añadido un peso a las aristas o un etiquetado a los vértices
- Aleatorio: las aristas están asociadas a una probabilidad.
- Hipergrafo: las aristas tienen más de dos extremos, tienen 3 o más vértices.
- Infinito: vértices y aristas de cardinal infinito.
Grafo dirigido
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. Estas, dependiendo de su salida o ingreso, reciben la calificación de entrante o saliente.
Tanto a las aristas como a los vértices les puede ser asociada información y se le llama etiqueta. Si lo que se asocia es un número obtiene el nombre de peso, costo o longitud. Un grafo cuyas aristas o vértices tienen pesos parecidos recibe el nombre de grafo etiquetado o ponderado. Los grafos dirigidos se representan mediante una flecha en la arista.
Grafo no dirigido
Tienen como definición aquellos que constan de un conjunto de vértices que se conectan a unas diversas aristas que no poseen una dirección. Puede una arista recorrerse desde cualquiera de sus puntos y en la dirección que desee.
Todo grafo dirigido simétrico se puede evidenciar como un grafo no dirigido. Por ello se pueden observar como un caso particular de grafos dirigidos. En un grafo no dirigido, el triangular superior de su matriz es igual a su triangular inferior, y viceversa.
4. ¿Cómo se pueden representar los grafos?
Listas de aristas
[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]
clic acá para ver la pagina de origen
Matrices de adyacencia
Listas de adyacencia
[ [1, 6, 8], [0, 4, 6, 9], [4, 6], [4, 5, 8], [1, 2, 3, 5, 9], [3, 4], [0, 1, 2], [8, 9], [0, 3, 7], [1, 4, 7] ]
Conclusiones
son una composición de un grupo de objetos que se denominan nodos tienen un conjunto de vértices (o nodos) y un conjunto de aristas (o arcos) que los unen. Gráficamente, se suelen representar los vértices como puntos en el plano y las aristas como segmentos que los unen.
Su estructura de datos no es lineal y son dinámicos, se utiliza para representar relaciones entre elementos, son esenciales en una variedad de aplicaciones, como inteligencia artificial, redes sociales, redes de transporte y muchas más.
Nota: Recuerde que cada pregunta debe ir acompañada de:
- Los enlaces de donde consulto la información (normas Apa) .
- De un aporte personal con sus propias palabras de lo que entendió de lo consultado.
- De una imagen que tenga relación con el tema o pregunta con su respectivo enlace (normas Apa)
- Insertar un video video (youtube) que explique o aclare la pregunta con su enlace respectivo (normas Apa)
- Debajo del video realizar un resumen de lo que dice o explica el autor del video.