GRAFOS


Os problemas que deram origem à teoria de grafos conduziram a configurações de pontos com linhas ligando alguns deles. Para eles, era irrelevante se as linhas eram rectilíneas ou curvas, onde estavam colocadas, se eram curtas ou longas. No que respeita a linhas, o único facto a considerar é que elas ligam dois pontos dados.(4)

definição

Assim acontece com o conceito matemático abstracto de Grafo.Um grafo G é um par (V, A), em que V representa um conjunto de pontos (vértices) e A um conjunto de segmentos (arestas ou arcos) ligando alguns pares de pontos de V. (3)(4)

 

Por exemplo, a figura abaixo pretende representar um grafo de sete vértices e cinco arestas,

em que V = {A, B, C, D, E, F, G} e A = {AD, AE, CD, DE, FG}.
Dois vértices dizem-se adjacentes quando há um arco ou aresta a uni-los. A e D são vértices adjacentes, mas A já não é adjacente a C e muito menos adjacente a F, por exemplo.
 
No caso da figura acima, não nos preocupámos em distinguir AD de DA. Trata-se de uma linha ligando dois pontos e o sentido é irrelevante. Mas há problemas (ruas de sentido único, ruas com duas faixas de rodagem...) em que o sentido da ligação é importante e teremos de considerar as ligações acompanhadas do seu sentido (isto é, as arestas não são simplesmente pares, passam a ser pares ordenados em que (A,D) é diferente de (D, A)). A grafos de arestas orientadas, chama-se grafos orientados (ou dirgidos). (3)
 
[De modo muito semelhante aparecem outras definições. Por exemplo: Um grafo é um objecto abstracto constituído por um conjunto de pontos (sem propriedades) e por um conjunto de linhas entre esses pontos (sendo a única propriedade de um linha a de ser incidente em dois pontos distintos ou coincidentes) Se se quiserem ordenar as duas incid~encias ou orientar a linha, então o grafo é uma aplicação dupla das linhas nos pontos: uma aplicação para designar a primeira incidência (ou incidência inicial) da linha, a outra para designar a segunda (terminal) da linha. Os especialistas em grafos empregam vértice ou nó em vez de ponto, aresta em vez de linha e arco em vez de linha orientada. (5)]
 
Ainda utilizando o grafo acima representado, vamos esclarecer alguns conceitos úteis:
 
A e D são extremidades da aresta AD,
 
Em D incidem três arestas, a saber AD,DE e DC e diz-se que D é um vértice (vertex) de valência (ou grau) 3; B tem valência zero, A tem valência 2, F tem valência 1.
 
Posso ir de A para C, pelo caminho AEDC ou pelo caminho DC (chamo caminho entre dois vértices X e Y, a uma sequência de arestas unindo pontos sucessivamente adjacentes, partindo de X e acabando em Y ou, de modo equivalente a uma sequência de vértices na qual entre entre quaisquer dois vértices sucessivos existe uma aresta).
 
Quando um caminho começa e acaba num mesmo ponto dizemos que temos um circuito. São exemplos de circuitos os caminhos AEDA ou EDAE. E chamamos comprimento de um circuito ao número de arestas que o constitui: AEDA é um circuito de comprimento 3.
 
 
Um grafo é conexo quando entre quaisquer dois dos seus vértices há um caminho que os une. O grafo da figura não é conexo, pois não há qualquer caminho que una o vértice A com o vértice F, por exemplo. Mas podemos considerar que {A, C, D, E} é uma parte conexa desse grafo.
 
Chamamos grafo completo a um grafo em que quaisquer dois dos seus pontos são adjacentes, isto é, há uma aresta para cada par dos seus vértices.
 
Chama-se grafo nulo a um grafo sem arestas. Não tem qualquer interese para o nosso estudo.
 
Pode acontecer que entre dois pontos haja mais do que uma aresta (por exemplo, num problema de controle de parcómetros colocados nos dois lados da rua) e será por isso preciso encontrar notações que as distingam. Isto é interessante para o nosso estudo.
 
[E podem também considerar-se arestas que comecem e acabem num mesmo ponto - chamam-se a essas arestas lacetes e fala-se de multigrafos quando existem lacetes. Mas isto não tem qualquer interesse para o nosso estudo.]
 
Muitas vezes aos vértices chamamos nós, cruzamentos, entroncamentos ou junções com o sentido óbvio. E às arestas chamaremos passeios ou ruas.....
 

voltar ao sumário