Grafos

Conceitos básicos

Grafo é uma estrutura de dados formado por dois conjuntos, que são os vértices e arestas
Vértices(nós) = objeto simples que pode ter nome e outros atributos
Aresta(arcos) = conexão entre dois vértices

Grafos direcionados são aqueles onde as arestas possuem sentido definido.

Grafos não direcionados são aqueles onde as arestas não possuem sentido definido.

O grau de um vértice direcionado é o número de arestas que saem dele(out- degree) mais o número de arestas que chegam nele(in-degree)

O grau de um vértice não direcionado é o número de arestas que incidem nele.

O comprimento de um caminho é o número de arestas nele.

O ciclo de um grafo direcionado se baseia quando o primeiro e o último vértices se encontram formando um círculo fechado, e o caminho contém pelo menos uma aresta.

No ciclo de um grafo não direcionado o caminho contém pelo menos três arestas.

Grafo conectado é quando pelo menos de um dos vértices é possível atingir todos os demais.

Fortemente conectado é quando de todos os vértices é possível atingir todos os demais.

Grafos são isomorfos se existir uma bijeção, tal que G=(V,A) e G'=(V',A')

Subgrafos é a parte integrante de um grafo original.

A versão direcionada de um grafo não direcionado G=(V,A) é um grafo direcionado G'=(V',A') onde (u,v) € A' e se somente se (u,v) € A

A versão não direcionada de um grafo direcionado G=(V,A) é um grafo não direcionado G'=(V',A') onde (u,v) € A' e se somente se u # v (u,v) € A

Exemplos:
Redes de estradas entre cidades: tipicamente, um grafo não dirigido:estradas em geral são de mão-dupla.
Redes de ruas em uma cidade: quase sempre um grafo dirigido: algumas ruas podem ser de mão-única.

Grafo ponderado possui pesos associados as arestas
Grafo bipartido-grafo não direcionado no qual V pode ser particionado em dois conjuntos V1 e V2
Hipergrafo - grafo não