Conceito Básicos Da Teoria De Grafos

GRAFO

Um grafo G(V,A) é definido pelo par de conjuntos V e A, onde:

V - conjunto não vazio: os vértices ou nodos do grafo;

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

Seja, por exemplo, o grafo G(V,A) dado por:

V = { p | p é uma pessoa }

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

Esta definição representa toda uma família de grafos. Um exemplo de elemento desta família (ver G1) é dado por:

V = { Maria, Pedro, Joana, Luiz }

A = { (Maria, Pedro), (Pedro, Maria), (Joana, Maria), (Maria, Joana), (Pedro, Luiz), (Luiz, Pedro), (Joana, Pedro) , (Pedro, Joana) } G1:

Neste exemplo estamos considerando que a relação <v é amigo de w> é uma relação simétrica, ou seja, se <v é amigo de w> então <w é amigo de v>. Como consequência, as arestas que ligam os vértices não possuem qualquer orientação

DIGRAFO (Grafo Orientado)

Considere, agora, o grafo definido por:

V = { p | p é uma pessoa da família Castro }

A = { (v,w) | < v é pai/mãe de w > }

Um exemplo de deste grafo (ver G2) é:

V = { Emerson, Isadora, Renata, Antonio, Cecília, Alfredo }

A = {(Isadora, Emerson), (Antonio, Renata), (Alfredo, Emerson), (Cecília, Antonio), (Alfredo, Antonio)} G2:

A relação definida por A não é simétrica pois se <v é pai/mãe de w>, não é o caso de <w é pai/mãe de v>. Há, portanto, uma orientação na relação, com um correspondente efeito na representação gráfica de G.

O grafo acima é dito ser um grafo orientado (ou digrafo), sendo que as conexões entre os vértices são chamadas de arcos.

________________________________________

ORDEM

A ordem de um grafo G é dada pela cardinalidade do conjunto de vértices, ou seja, pelo número de vértices de G. Nos exemplos acima:

• ordem(G1) = 4

• ordem(G2) = 6

ADJACÊNCIA

Em um grafo simples (a exemplo de G1) dois vértices v e w são adjacentes (ou vizinhos) se há uma aresta a=(v,w) em G. Está aresta é dita ser incidente a ambos, v e w. É o caso dos vértices Maria e Pedro em G1. No caso do grafo ser dirigido (a exemplo de G2), a adjacência (vizinhança) é especializada em:

Sucessor: um vértice w é sucessor de v se há um arco que parte de v e chega em w. Em G2, por exemplo, diz-se que Emerson e Antonio são sucessores de Alfredo.

Antecessor: um vértice v é antecessor de w se há um arco que parte de v e chega em w. Em G2, por exemplo, diz-se que Alfredo e Cecília são antecessores de Antonio.

GRAU

O grau de um vértice é dado pelo número de arestas que lhe são incidentes. Em G1, por exemplo:

• grau(Pedro) = 3

• grau(Maria) = 2

No caso do grafo ser dirigido (a exemplo de G2), 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. Em G2, por exemplo:

• grauDeEmissão(Antonio) = 1

• grauDeEmissao(Alfredo) = 2

• grauDeEmissao(Renata) = 0

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

• grauDeRecepção(Antonio) = 2

• grauDeRecepção(Alfredo) = 0

• grauDeRecepção(Renata) = 1

FONTE

Um vértice v é uma fonte se grauDeRecepção(v) = 0. É o caso dos vértices Isadora, Alfredo e Cecília em G2.

SUMIDOURO

Um vértice v é um sumidouro se grauDeEmissão(v) = 0. É o caso dos vértices Renata e Emerson em G2.

LAÇO

Um laço é uma aresta ou arco do tipo a=(v,v), ou seja, que relaciona um vértice a ele próprio. Em G3 há três ocorrências de laços para um grafo não orientado. G3:

________________________________________

GRAFO REGULAR

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

O grafo G4, por exemplo, é dito ser um grafo regular-3 pois todos os seus vértices tem grau 3. G4:

GRAFO COMPLETO

Um grafo é dito ser completo quando 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 número máximo possível de arestas para um dados n. Ele é, também regular-(n-1) pois todos os seus vértices tem grau n-1.

GRAFO BIPARTIDO

Um grafo é dito ser 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.

Para exemplificar, sejam os conjuntos H={h | h é um homem} e M={m | m é um mulher} e o grafo G(V,A) (ver o exemplo G5) onde:

• V = H U M

• A = {(v,w) | (v ∈ H e w ∈ M) ou (v ∈ M e w ∈ H)

e <v foi namorado de w>} G5:

O grafo G6 é uma K3,3, ou seja, um grafo bipartido completo que contém duas partições de 3 vértices cada. Ele é completo pois todos os vértices de uma partição estão ligados a todos os vértices da outra partição. G6: K3,3

GRAFO ROTULADO

Um grafo G(V,A) é dito ser rotulado