Conceitos básicos de grafos
Queres ir de autocarro de uma freguesia para outra e perguntas-te: «Há ligação direta? Ou tenho de mudar?» Para responder, não precisas do mapa todo: basta saber quem está ligado a quem. Um esquema só com pontos e linhas chega, e é a isso que se chama grafo. Vais ver que o mesmo esquema serve para autocarros, amizades, estradas ou redes sociais.
Vértices e arestas
Imagina que a empresa ViaCávado liga quatro freguesias: Arcozelo (A), Barcelos (B), Carvalhal (C) e Tamel (T). Há carreiras diretas entre A e B, entre B e C e entre B e T.
Para modelar a situação, escolhemos o que é essencial: cada freguesia vira um ponto e cada carreira direta vira uma linha. As distâncias e a forma do mapa não interessam.
Dois vértices ligados por uma aresta dizem-se adjacentes. No exemplo, A e B são adjacentes, mas A e C não.
Há mais três casos particulares:
-
Laço: aresta que liga um vértice a ele próprio (por exemplo, uma carreira circular que parte e volta à mesma paragem).
-
Vértice isolado: vértice que não é extremo de nenhuma aresta.
-
Arestas múltiplas: duas ou mais arestas a ligar o mesmo par de vértices (por exemplo, duas pontes entre as mesmas margens).
A empresa de autocarros ViaCávado assegura ligações diretas entre cinco freguesias do concelho de Barcelos: Arcozelo (A), Barcelos (B), Carvalhal (C), Gilmonde (G) e…
A empresa de autocarros ViaCávado assegura ligações diretas entre cinco freguesias do concelho de Barcelos: Arcozelo (A), Barcelos (B), Carvalhal (C), Gilmonde (G) e Tamel (T). As ligações existentes são: AB, AC, BT, CT e GT.
- a) Representa esta situação por um grafo, indicando o que representam os vértices e as arestas.
- b) Quantos vértices e quantas arestas tem o grafo?
- c) Determina o grau de cada vértice. Qual é a freguesia com mais ligações diretas?
Ordem e grau
No grafo da secção anterior, a ordem é $4$. Os graus são: $A$: 1, $B$: 3, $C$: 1, $T$: 1. O vértice B tem o grau mais alto: é a freguesia com mais ligações diretas.
Repara que a soma dos graus é $1+3+1+1=6$, e o grafo tem $3$ arestas. Cada aresta tem dois extremos, por isso contribui com $2$ para a soma dos graus:
$$\text{soma dos graus} = 2 \times \text{n.º de arestas}$$Isto serve de verificação: se a soma dos graus der um número ímpar, contaste mal.
Num grupo de trabalho de uma turma do 11.º ano, a Marta (M), o Nuno (N), o Pedro (P), a Rita (R) e o Simão (S) indicaram as suas amizades dentro do grupo. O grafo das…
Num grupo de trabalho de uma turma do 11.º ano, a Marta (M), o Nuno (N), o Pedro (P), a Rita (R) e o Simão (S) indicaram as suas amizades dentro do grupo. O grafo das amizades tem vértices {M, N, P, R, S} e arestas MN, MP, NR, PS e RS.
- a) Determina o grau de cada vértice e interpreta o seu significado no contexto do grupo.
- b) Calcula a soma dos graus de todos os vértices. Que relação existe entre essa soma e o número de arestas?
- c) O grafo é conexo? Justifica.
Caminhos e circuitos
Num grafo podemos «andar» de vértice em vértice, sempre através de arestas.
Considera as ligações do vale do Douro: $PR$, $RN$, $NC$ e $PN$ entre Porto (P), Régua (R), Pinhão (N) e Pocinho (C).
Do Porto ao Pocinho há, por exemplo, o caminho $P\to R\to N\to C$, de comprimento $3$, e o caminho $P\to N\to C$, de comprimento $2$. Um caminho pode repetir vértices (e arestas), mas muitas vezes pede-se que não repita.
Um circuito neste grafo: $P\to R\to N\to P$, de comprimento $3$: começa e acaba em P.
Uma agência de viagens organiza percursos no vale do Douro entre quatro localidades: Porto (P), Régua (R), Pinhão (N) e Pocinho (C). As ligações disponíveis são: PR, RN,…
Uma agência de viagens organiza percursos no vale do Douro entre quatro localidades: Porto (P), Régua (R), Pinhão (N) e Pocinho (C). As ligações disponíveis são: PR, RN, NC e PN.
- a) Indica dois caminhos diferentes para ir do Porto ao Pocinho, sem repetir localidades.
- b) Qual é o comprimento (número de arestas) de cada um desses caminhos?
- c) Um turista quer ir da Régua ao Pinhão passando pelo Porto. Escreve o caminho correspondente como sequência de vértices e indica se algum vértice se repete.
Grafos conexos e ponderados
No exemplo do grupo de trabalho (Marta, Nuno, Pedro, Rita e Simão) com amizades $MN$, $MP$, $NR$, $PS$ e $RS$, é possível ir de qualquer pessoa a qualquer outra por «amigo de amigo»: o grafo é conexo. Se acrescentássemos um sexto aluno sem nenhum amigo no grupo, esse vértice isolado tornaria o grafo não conexo.
Por vezes, as arestas têm um número associado: quilómetros, minutos, euros. Chama-se peso, e o grafo diz-se ponderado. Por exemplo, na carreira da ViaCávado, a aresta $AB$ pode ter peso $12$ (km). O peso de um caminho é a soma dos pesos das arestas que percorre: se $AB=12$ e $BT=7$, então o caminho $A\to B\to T$ tem peso $19$ km.
De volta ao início: para saber se podes ir de uma freguesia a outra, basta ver se há um caminho entre os dois vértices; e se o grafo for conexo, há sempre.
Em resumo
-
Um grafo tem vértices e arestas; a posição do desenho não importa, só quem está ligado a quem.
-
Adjacentes: ligados por uma aresta. Laço: aresta de um vértice a si próprio. Vértice isolado: sem arestas.
-
A ordem é o número de vértices; o grau de um vértice é o número de arestas que nele terminam. A soma dos graus é o dobro do número de arestas.
-
Um caminho é uma sucessão de vértices adjacentes; o comprimento é o número de arestas. Um circuito é um caminho fechado.
-
Um grafo é conexo se existe caminho entre quaisquer dois vértices; é ponderado se as arestas têm pesos.