CAPÍTULO III
Este capítulo apresenta uma definição dos conceitos básicos referentes a teoria dos grafos.
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 pertencentes a 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 é dado por:
V = { Maria, Pedro, Joana, Luiz }
A = { (Maria, Pedro) , (Joana, Maria) , (Pedro, Luiz) , (Joana, Pedro) }
Graficamente este grafo pode ser apresentado pelo diagrama ao lado.
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 conseqüê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 é:
V = { Emerson, Isadora, Renata, Antonio, Rosane, Cecília, Alfredo }
A = {(Isadora, Emerson), (Antonio, Renata), (Alfredo, Emerson), (Cecília, Antonio), (Alfredo, Antonio)}
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.
GRAFOS MISTOS
Grafos mistos
podem ser vistos como uma generalização do conceito de grafos não-orientados e grafos orientados. São grafos que possuem tanto arestas não orientadas como arestas orientadas. Vários dos conceitos básicos associados a grafos como caminhos e conexidade podem ser facilmente estendidos para grafos mistos.
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 ao lado:
- ordem(G1) = 4 G1:
- 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.
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.
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.