Grafo orientado

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências (Encontre fontes: ABW  • CAPES  • Google (N • L • A)). (Agosto de 2022)

Um grafo orientado,^[1] grafo dirigido,^[2] grafo direcionado^[3] ou digrafo é um par ${\displaystyle G=(V,A)}$ (algumas vezes ${\displaystyle G=(V,E)}$)^(edge) de:^[4][5][6]

• Um conjunto V, cujos elementos são chamados vértices ou nodos,
• um conjunto A de pares ordenados de vértices, chamados arcos, arestas direcionadas, ou setas (e às vezes simplesmente arestas com o conjunto correspondente chamado E ao invés de A).

Ele difere de um grafo não-direcionado comum, em que o último é definido em termos de pares não ordenados de vértices, que são normalmente chamados arestas.

Por exemplo, ser possível ir de um nó A para um nó B, mas não o contrário através desse arco.

Às vezes, um digrafo é chamado de um digrafo simples para distinguí-lo de um multigrafo direcionado (ou multidigrafo ou ainda quiver), em que os arcos constituem um multiconjunto, ao invés de um conjunto, de pares ordenados de vértices. Além disso, em um digrafo simples laços não são permitidos. Por outro lado, alguns textos permitem laços, arcos múltiplos, ou ambos em um digrafo.