Definición de Grafos:

Un grafo es una estructura matemática que se utiliza para representar relaciones entre objetos. En
matemáticas y ciencias de la computación un grafo es un conjunto no vacío, de objetos llamados
vértices (o nodos) y una selección de pares de vértices, llamados aristas (o arcos) que pueden ser
orientados o no.

El origen de la palabra grafo es griego (grafos: dibujo, imagen) y su significado etimológico es

"trazar".

Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por
líneas (las aristas).

¿Para qué sirven?

Los grafos permiten estudiar las relaciones que existen entre unidades que interactúan con otras.

Aparecen con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos
podrían ser los siguientes: un gráfico de una serie de tareas a realizar indicando su secuenciación
(un organigrama), grafos matemáticos que representan las relaciones binarias, una red de
carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad. En cada caso es
conveniente representar gráficamente el problema dibujando un grafo como un conjunto de
puntos (nodos o vértices) con líneas conectándolos (aristas o arcos).
Tipos de Grafos

 Grafo simple. o simplemente grafo es aquel que acepta una sola una arista uniendo dos
vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que
une dos vértices específicos. Es la definición estándar de un grafo.

Un grafo simple es un grafo que no tiene bucles (es decir, aristas que conectan un vértice
consigo mismo) ni aristas paralelas (es decir, dos aristas que conectan el mismo par de
vértices).

 Multígrafo o pseudografo son grafos que aceptan más de una arista entre dos vértices.
Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una
subclase de esta categoría de grafos. También se les llama grafos no-dirigido.

 Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas,
representada gráficamente por una flecha.

Un grafo dirigido es un grafo en el que las aristas tienen una dirección, es decir, que una
arista conecta un vértice de origen a un vértice de destino.

 Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero
generalmente) o un etiquetado a los vértices.

 Grafo ponderado: un grafo ponderado es un grafo en el que cada arista tiene un peso o
valor asociado.

 Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.

  Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas
son incidentes a 3 o más vértices.

 Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.

Los grafos son una estructura matemática que se utiliza para representar relaciones entre objetos.
Estos objetos se denominan vértices o nodos, y las relaciones entre ellos se representan mediante
aristas o bordes. Los grafos se utilizan en una amplia variedad de campos, como la informática, las
redes, la ingeniería y la física.

En cuanto a la representación de grafos, hay varias formas de representar un grafo. Algunas de las
formas más comunes son:

Matriz de adyacencia: una matriz de adyacencia es una matriz cuadrada que representa las
aristas de un grafo. Cada entrada en la matriz indica si hay una arista entre dos vértices.

Lista de adyacencia: una lista de adyacencia es una lista que representa las aristas de un
grafo. Para cada vértice, la lista indica los vértices adyacentes (es decir, los vértices
conectados por una arista).

Matriz de incidencia: una matriz de incidencia es una matriz que representa las aristas de
un grafo y los vértices a los que están conectados. Cada columna representa una arista, y
cada fila representa un vértice. Una entrada en la matriz es 1 si el vértice está conectado a
la arista y 0 en caso contrario.

En cuanto a los algoritmos de manipulación de grafos, hay muchos algoritmos diferentes que se
utilizan para manipular y analizar grafos. Algunos ejemplos comunes incluyen:

Algoritmo de búsqueda en profundidad (DFS): Es un algoritmo que permite recorrer todos

los nodos de un grafo. El algoritmo comienza por un nodo raíz y visita todos sus nodos
adyacentes antes de avanzar a los siguientes nodos no visitados. El DFS se implementa
típicamente con una función recursiva.

Ejemplo en pseudocódigo:
Algoritmo de búsqueda en anchura (BFS): Es un algoritmo que también permite recorrer
todos los nodos de un grafo, pero lo hace de manera iterativa. El BFS comienza en un nodo
raíz y visita todos sus nodos adyacentes antes de avanzar a los siguientes nodos en el
mismo nivel.

Ejemplo en pseudocódigo:

Algoritmo de Dijkstra: Es un algoritmo que encuentra el camino más corto entre dos nodos
en un grafo con pesos en las aristas. El algoritmo comienza en un nodo raíz y asigna una
distancia tentativa a todos los nodos. Luego, el algoritmo selecciona el nodo con la
distancia tentativa más corta y actualiza las distancias tentativas de sus nodos adyacentes
si se puede mejorar la distancia.

Ejemplo en pseudocódigo:
Algoritmo de Kruskal: Es un algoritmo que encuentra el árbol de expansión mínimo de un
grafo no dirigido y ponderado. El algoritmo comienza ordenando las aristas por peso y
luego agrega las aristas más ligeras a un árbol si no forma un ciclo con las aristas ya
seleccionadas.

Ejemplo en pseudocódigo: