El concepto básico de un gráfico es, un modelo matemático que sirve para representar las relaciones entre objetos de un conjunto.
| Un grafo es una estructura de datos, estructuras de datos no lineales las cuales se utilizan para representar relaciones entre objetos estos objetos estan unidos por vetices o nodos(en la imagen estan representados por 🙂), que están conectados a través de aristas, líneas o conexiones. |
|---|
Pasando de teoría de conjuntos a teoría de grafos
Solo ver del min3:33 hasta el minuto 9
Solo ver del min3:33 hasta el minuto 9
Nodos/Vertice
A nivel conceptual, un nodo es un punto o entidad fundamental en un grafo, cada nodo cuenta con un identificador y una arista (adyacencia). Representa una ubicación, un objeto, o cualquier entidad discreta que se quiere modelar en el conjunto de datos.
La relación entre nodos se establece a través de las aristas ↪️. En un grafo dirigido, hay un sentido en la relación, mientras que en un grafo no dirigido, la relación es bidireccional.
| En la imagen 1 si el emoji 🥰 quiere llegar hasta el emoji 😍 tiene que recorrer 5 nodos o ↪️ para llegar. Esto es porque los nodos de la imagen son unidireccionales, per a simple vista se ve que se podria acortar el camino.
Dirigido (unidireccional): En un grafo dirigido, las aristas tienen una dirección. Esto significa que la relación entre dos nodos tiene una orientación específica, yendo de un nodo de inicio a un nodo de destino. En este caso, se puede hablar de "nodo inicial" y "nodo final" en el contexto de una arista dirigida. | En la imagen 1 si el emoji 🥰 quiere llegar hasta el emoji 😍 tiene que recorrer 2 nodos o ↪️ para llegar. Esto es porque los nodos de la imagen 2 son bidireccionales.
No dirigido (bidireccional): En un grafo no dirigido, las aristas no tienen una dirección específica. La relación entre dos nodos es simétrica, lo que significa que la conexión entre ellos funciona en ambas direcciones. No hay un concepto de "nodo inicial" o "nodo final" en el contexto de una arista no dirigida. | | --- | --- |
Peso $W$
Se refiere a un valor asociado con cada arista. Este valor numérico indica alguna medida o costo asociado con la conexión entre dos nodos. Los grafos que tienen pesos en sus aristas se llaman "grafos ponderados". El peso puede ser un número entero, decimal, o incluso una medida no numérica en algunos casos.
| Si usamos el ejemplo anterior (si el emoji 🥰 quiere llegar hasta el emoji 😍), determinamos los pesos de las aristas son semanas y que cada vez que usemos una arista se suma a nuesto peso que empieza en 0, si elejimos la ruta que tiene 2 nodos(😜 😴) nuestro peso será de 45, en cambio si usamos una ruta que sea de 5 nodos (😀 😎 😄 😴 😱) nuestro peso será de 18. |
|---|
-
Notacion:
$$ G=(N,V) \space donde \space N,V \space son \space nodos \\ $$
