O que é um grafo orientado e quais são as suas principais características?

Um grafo dirigido (ou dígrafo) é uma estrutura de dados composta por um conjunto de vértices (nós) e um conjunto de arcos direcionados que conectam esses vértices. Cada arco tem uma direção que indica qual vértice é o inicial e qual é o final.

Características principais:

• Vértices (Nós / Vertices): Elementos do grafo representados por pontos. Podem representar objetos, estados ou etapas.
• Arcos (Edges / Arcs): Ligações entre vértices. Em um grafo dirigido, o arco tem uma direção que indica a transição de um vértice para outro. São representados por um par ordenado (u, v), onde u é o vértice inicial e v o final.
• Direcionalidade: Característica chave que distingue um grafo dirigido de um não dirigido. O movimento só é possível ao longo da direção do arco. Um arco de A para B não implica que seja possível mover-se de B para A, a menos que exista um arco separado de B para A.
• Círculos (Loops): Arcos que conectam um vértice a si mesmo (v, v).
• Arcos múltiplos (Multiple Edges): Vários arcos conectando o mesmo par de vértices na mesma direção. Em grafos dirigidos simples, arcos múltiplos não são permitidos.
• Vértices isolados: Vértices sem arcos de entrada ou saída.
• Grau do vértice:
  • Grau de entrada (In-degree): Número de arcos que entram em um vértice.
  • Grau de saída (Out-degree): Número de arcos que saem de um vértice.

Aplicações em QA:

• Grafos de estados para testar autômatos finitos.
• Grafos de fluxo de controle para análise de código e construção de casos de teste.
• Modelagem de dependências em sistemas (por exemplo, dependências entre serviços ou módulos).
• Teste de cenários de uso com sequências estritas de ações.