Se um par de vértices ( u, v ) não é o mesmo que o par ( v, u ), dizemos que a aresta ( u, v ) é direcionada do vértice 'u', chamada de cauda da aresta, para o vértice v, chamado de cabeça da aresta. Também dizemos que a aresta ( u, v ) sai de 'u' e entra em 'v'.
Um grafo cujo cada aresta é direcionada é chamado de direcionado. Grafos direcionados também são chamados de dígrafos.
Uma vez que nossa definição não permite múltiplas arestas entre os mesmos vértices de um grafo não direcionado, temos a seguinte desigualdade para o número de arestas | E | possível em um gráfico não direcionado com | V | vértices e seus loops.
O <= | E | <= | V | ( | V | - 1 / 2)
Um grafo com cada par de seus vértices conectados por uma aresta é chamado completo. Uma notação padrão para o grafo completo com | v | vértices é K | V |.
Um grafo com relativamente poucas arestas possíveis faltando é chamado de denso. Um grafo com poucas arestas em relação a número de seus vértices é chamado de esparso.
- 3 more items...