¿Qué es un grafo dirigido y cuáles son sus características?

Un grafo dirigido es un grafo que tiene un conjunto de vértices (nodos) y un conjunto de aristas (arcos), donde cada arco tiene una dirección.

Características:

• Aristas dirigidas: El movimiento a lo largo del arco solo es posible en una dirección, indicada por una flecha.
• Grado del vértice: Para un grafo dirigido, se define el grado de entrada (el número de aristas que terminan en el vértice) y el grado de salida (el número de aristas que comienzan en el vértice).
• Caminos y ciclos: Un camino es una secuencia de vértices conectados por aristas en la dirección correcta. Un ciclo es un camino que comienza y termina en el mismo vértice. Los grafos dirigidos pueden contener ciclos dirigidos.
• Conectividad: Se distingue entre conectividad débil (ignorando las direcciones de las aristas, el grafo es conexo como no dirigido) y conectividad fuerte (para cualesquiera dos vértices A y B, existe un camino dirigido de A a B y de B a A).
• Representación: Pueden ser representados mediante listas de adyacencia o matrices de adyacencia, donde para un grafo dirigido, la matriz generalmente no es simétrica.

Ejemplo de representación mediante lista de adyacencia:

# Grafo G = (V, E), donde V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

grafo = {
    0: [1],
    1: [2],
    2: [0]
}

Ejemplo de representación mediante matriz de adyacencia:

# Grafo G = (V, E), donde V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

matriz = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # sin aristas salientes desde 2
]