Exercícios: Conceitos básicos

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.

1. a) Representa esta situação por um grafo, indicando o que representam os vértices e as arestas.
2. b) Quantos vértices e quantas arestas tem o grafo?
3. c) Determina o grau de cada vértice. Qual é a freguesia com mais ligações diretas?

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.

1. a) Determina o grau de cada vértice e interpreta o seu significado no contexto do grupo.
2. b) Calcula a soma dos graus de todos os vértices. Que relação existe entre essa soma e o número de arestas?
3. c) O grafo é conexo? Justifica.

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.

1. a) Indica dois caminhos diferentes para ir do Porto ao Pocinho, sem repetir localidades.
2. b) Qual é o comprimento (número de arestas) de cada um desses caminhos?
3. 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.