Grafo

Dado um par de conjuntos V e A, onde

V - conjunto não vazio de vértices/nodos

A - conjunto de pares ordenados a = (v,w), v e w ∈ V: as arestas do grafo.

Exemplo

Seja o grafo G(V,A) dado por

V = {p | p é uma pessoa}

A = { (v, w) | < v é amigo de w > }

Nesse exemplo, a relação é simétrica , isso é, se < v é amigo de w >, então < w é amigo de v >. Assim, as arestas que ligam os vértices não possuem orientação.

Grafo Regular

Um grafo é regular quando todos os seus vértices tem o mesmo grau.

Grafo Completo

Um grafo é completo quandoo há uma aresta entre cada par de seus vértices. Estes grafos são designados por Kn, onde n é a ordem do grafo.

Um grafo Kn possui o máximo possível de arestas para um dado n. Ele é, também regular - (n-1), pois todos os seus vértices tem grau n-1.

Digrafo (Grafo Orientado)

Dado o grafo definido por:

V = { p | p é uma pessoa da familia Jorgensen} A = { (v,w) | < v é pai/mãe de w > }

Essa relação é não simétrica , resultando em uma orientação no grafo. Esse tipo de grafo é dito grafo orientado ou digrafo , onde as conexões entre vértices são chamadas de arcos.

Grafo Bipartido

Um grafo é dito bipartido quando seu conjunto de vértices V puder ser particionado em dois subconjuntos V1 e V2, tais que toda aresta de G une um vértice de V1 a outro de V2

Um grafo é bipartido completo se todos os vértices de uma partição estão ligados a todos os vértices da outra partição

Conceitos de Grafos

Ordem

A ordem de um grafo G é dada pela cardinalidade do conjunto de vértices (número de vértices).

Adjacência

Em um grafo simples, dois vértices v e w são adjacentes (ou vizinhos) se há uma aresta a=(v,w) em G. Essa aresta é incidente a ambos v e w.

Se o grafo for dirigido, a adjacência é especializada em:

Sucessor: um vértice w é sucessor de v se há um arco que parte de v e chega em w.

Antecessor> um vértice v é antecessor de w se há um arco que parte de v e chega em w.

Grau

O grau de um vértice é dado pelo número de arestas que lhe são incidentes.

No caso de digrafos, a noção de grau é especializada em:

Grau de emissão: o grau de emissão de um vértice v corresponde ao número de arcos que partem de v.

Grau de recepção: o grau de recepção de um vértice v corresponde ao número de arcos que chegam a v.

Fonte

Um vértice v é fonte se seu grau de recepção é nulo.

Sumidouro

Um vértice v é sumidouro se seu grau de emissão é nulo.

Laço

Um laço é uma aresta ou arco do tipo a = (v,v), que relaciona um vértice a ele próprio.