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

Un grafo dirigido (o digrafo) es una estructura de datos que consiste en un conjunto de vértices (nodos) y un conjunto de aristas dirigidas (arcos) que conectan estos vértices. Cada arista tiene una dirección que indica qué vértice es el inicial y cuál es el final.

Características principales:

• Vértices (Nodos / Vertices): Elementos del grafo representados por puntos. Pueden representar objetos, estados o etapas.
• Aristas (Edges / Arcs): Conexiones entre vértices. En un grafo dirigido, la arista tiene una dirección que indica la transición de un vértice a otro. Se representan como un par ordenado (u, v), donde u es el vértice inicial y v el final.
• Direccionalidad: Característica clave que distingue un grafo dirigido de uno no dirigido. El movimiento solo es posible a lo largo de la dirección de la arista. Una arista de A a B no implica que se pueda mover de B a A, a menos que exista una arista separada de B a A.
• Caminos (Loops): Aristas que conectan un vértice consigo mismo (v, v).
• Aristas múltiples (Multiple Edges): Varias aristas que conectan el mismo par de vértices en la misma dirección. En grafos dirigidos simples, no se permiten aristas múltiples.
• Vértices aislados: Vértices sin aristas entrantes ni salientes.
• Grado del vértice:
  • Grado de entrada (In-degree): Número de aristas entrantes a un vértice.
  • Grado de salida (Out-degree): Número de aristas salientes de un vértice.

Aplicaciones en QA:

• Grafos de estados para probar autómatas finitos.
• Grafos de flujo de control para análisis de código y creación de casos de prueba.
• Modelado de dependencias en sistemas (por ejemplo, dependencias entre servicios o módulos).
• Pruebas de escenarios de uso con secuencias estrictas de acciones.