Escola Secundária Almeida Garrett 11º ANO – MACS

GRAFOS – DEFINIÇÕES BÁSICAS (II)

DEFINIÇÕES:

CAMINHO – Ligação sucessiva de vértices adjacentes.

CIRCUITO – Caminho que começa e acaba no mesmo vértice.

COMPRIMENTO DE UM CAMINHO – Número de arestas que o constituem.

GRAFO COMPLETO – Grafo em que todos os vértices são adjacentes dois a dois.

GRAFO CONEXO – Grafo em que existe, pelo menos, um caminho a ligar cada par de vértices.

GRAFO REGULAR – Grafo em que todos os vértices têm o mesmo grau.

GRAFO SIMPLES – Grafo sem arestas paralelas nem laços.

MULTIGRAFO – Grafo que apresenta laços ou mais do que uma aresta a ligar um par de vértices.

VÉRTICE ISOLADO – Vértice que não tem ligação com nenhum outro vértice.

Observe os cinco grafos seguintes:

GRAFO I

GRAFO II

GRAFO III

GRAFO IV

GRAFO V

Escola Secundária Almeida Garrett 11º ANO – MACS

GRAFOS – DEFINIÇÕES BÁSICAS (II)

Centro

Norte

Alentejo

L.V.T.

Algarve

1. Identifique:

a. O(s) multigrafo(s).

b. O(s) completo(s).

c. O(s) não conexo(s).

d. O(s) regular(es).

2. Desenhe:

a. Um grafo completo com 4 vértices.

b. Um grafo regular com 5 vértices.

c. Um multigrafo completo com 5 vértices.

3. Considere, no GRAFO II, o caminho 6431.

a. Qual é o comprimento deste caminho?

b. Indique um caminho de menor comprimento que comece e acabe nos mesmos vértices.

c. Identifique um caminho neste grafo que passa em todas a suas arestas mas em que cada uma é atravessada

uma e uma só vez.

4. Dê exemplo de um:

a. Caminho de comprimento 5 no GRAFO III.

b. Circuito de comprimento 4 no GRAFO V.

c. Circuito de comprimento 7 no GRAFO IV.

d. Circuito que passe uma e uma só vez por todos os vértices do GRAFO V.

5. As Unidades Territoriais Estatísticas de Portugal designam as sub-regiões estatísticas em que se divide o território

português, de acordo com o Regulamento (CE) n.º 1059/2003 do Parlamento Europeu e do Conselho de 26 de Maio de

2003. O Regulamento instituiu uma Nomenclatura Comum

das Unidades Territoriais Estatísticas (NUTS). As sub-regiões

estatísticas de Portugal são de três níveis - NUTS I, NUTS II e

NUTS III1. A figura apresenta as sub-regiões de nível NUTS I.

a. Modele o mapa da figura através de um grafo.

Considere para vértices as regiões indicadas. As

arestas devem traduzir a relação de fronteira entre

as regiões.

b. Para o grafo que construiu indique:

i. A dimensão e a ordem.

ii. A valência de cada vértice.

c. Averigúe se o grafo é:

i. Completo.

ii. Regular.

iii. Conexo.

iv. Simples.

1 UNIDADES TERRITORIAIS ESTATÍSTICAS DE PORTUGAL. In: WIKIPÉDIA, a enciclopédia livre. Flórida: Wikimedia Foundation, 2010. Disponível em:

<http://pt.wikipedia.org/w/index.php?title=Unidades_Territoriais_Estat%C3%ADsticas_de_Portugal&oldid=21870215>. Acesso em: 18 set. 2010.