Actividad 9
Investigar sobre el tema de grafos y realizar un reporte.
¿Qué es un Grafo?
Un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas
o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras.
Un grafo es una representación gráfica de diversos puntos que se conocen como nodos o
vértices, los cuales se encuentran unidos a través de líneas que reciben el nombre de aristas.
Componentes Básicos
Nodos (Vértices): Son los puntos fundamentales del grafo.
Aristas: Son las conexiones entre nodos. Pueden ser dirigidas (con una dirección) o no
dirigidas.
Peso: Algunas aristas pueden tener un peso asignado, representando una medida, distancia o
costo asociado.
Tipos de Grafos:
Grafo No Dirigido: Las aristas no tienen dirección. La relación es bidireccional. Grafo
Dirigido: Las aristas tienen dirección, indicando una relación unidireccional. Grafo
Ponderado: Las aristas tienen un peso asociado.
Grafo No Ponderado: Las aristas no tienen peso asociado.
Grafo Cíclico: Contiene ciclos, es decir, es posible regresar al mismo nodo siguiendo una serie de aristas.
Grafo Acíclico: No contiene ciclos.
Grafo Conexo: Todos los nodos están conectados por al menos un camino.
Grafo Disconexo: Existen nodos que no están conectados a ningún otro nodo.
Algoritmos Importantes:
Recorrido en Profundidad (DFS): Explora lo más posible a lo largo de cada rama antes de
retroceder.
Recorrido en Anchura (BFS): Explora todos los vecinos de un nodo antes de pasar a los
vecinos del siguiente nivel.
Algoritmo de Dijkstra: Encuentra el camino más corto entre dos nodos en un grafo ponderado.
Algoritmo de Kruskal: Encuentra el árbol de expansión mínima en un grafo ponderado no
dirigido.
Clasificación de Grafos
Los grafos pueden ser clasificados de diversas maneras según sus características. Los grafos
simples son aquellos que surgen cuando una única arista logra unir dos vértices. Los grafos
complejos, en cambio, presentan más de una arista en unión con los vértices.
Adicionalmente tenemos el multigrafo que es una versión ligeramente más compleja en la que
los nodos que conforman el grafo se conectan con otros nodos a través de aristas múltiples o
paralelas.
Importancia de los Grafos
Los grafos son muy utilizados en el estudio de ciencias naturales y otras áreas del conocimiento.
En el ámbito empresarial y tecnológico se han empezado a explotar sus potencialidades. Su
alcance con fines empresariales recorren desde la posibilidad de estudiar las relaciones de los
clientes con los productos que ofrecemos, hasta la posibilidad de entender a profundidad todos y
cada uno de los procesos relacionales que se desarrollan dentro de una organización y que son
imperceptibles a simple vista.