Desenhe o grafo que representa as rotas marítimas, utilizando os portos como vértices e as rotas como arestas. As rotas existentes são:
- Rio de Janeiro (Brasil) - Lisboa (Portugal)
- Lisboa (Portugal) - Roterdã (Holanda)
- Roterdã (Holanda) - Hamburgo (Alemanha)
- Rio de Janeiro (Brasil) - Cidade do Cabo (África do Sul)
- Cidade do Cabo (África do Sul) - Mumbai (Índia)
- Cingapura (Singapura) - Sydney (Austrália)
- Sydney (Austrália) - Auckland (Nova Zelândia)
- Hamburgo (Alemanha) - Cingapura (Singapura)
Passo 1
O que o problema pede:
- Desenhar o grafo que representa as rotas marítimas, usando portos como vértices e rotas como arestas.
Informações fornecidas (cada item é uma aresta / rota):
- Rio de Janeiro — Lisboa
- Lisboa — Roterdã
- Roterdã — Hamburgo
- Rio de Janeiro — Cidade do Cabo
- Cidade do Cabo — Mumbai
- Cingapura — Sydney
- Sydney — Auckland
- Hamburgo — Cingapura
Esses são todos os dados que vou usar. Não há outras rotas nem restrições adicionais no enunciado.
Passo 2
Escolha do modelo e explicação rápida do que é um grafo (aula curta e amigável):
- Um grafo é uma estrutura formada por um conjunto de vértices
e um conjunto de arestas . Escrevemos isso como . - Neste problema as rotas marítimas são naturalmente bidirecionais (pode-se navegar em ambos os sentidos), então vou usar um grafo não direcionado: cada aresta é um par não-ordenado
. - Duas representações úteis e fáceis de desenhar numa prova:
- lista de adjacência (para cada vértice, quem são os vizinhos);
- desenho esquemático (posicionar vértices e ligar com linhas).
Vou montar ambas: a lista de vértices e arestas em forma matemática, depois a lista de adjacência, e por fim um desenho esquemático (ASCII) que você pode copiar no caderno.
Passo 3
Identificar os vértices
(os portos). Vou nomeá-los com o nome completo para ficar claro:
Listar as arestas
como pares não-ordenados (peguei cada par do enunciado):
Passo 4
Lista de adjacência (para cada vértice, escrever os vizinhos — isso ajuda a desenhar rápido na prova). Cada linha é um pequeno mapa local:
Dica didática: para desenhar, comece desenhando vértices com muitos vizinhos e conecte-os; a lista acima mostra exatamente quem ligar a quem.
Passo 5
Matriz de adjacência (opcional, mas útil para provas formais). Vou fixar a ordem dos vértices como na Passo 3. A matriz
é
com entradas
se há aresta entre o vértice
e
, e
caso contrário. Ordenação:
. Então
Explicação rápida: a matriz é simétrica (grafo não-direcionado) e cada linha mostra ligações do vértice correspondente.
Passo 6
Graus dos vértices e conectividade (coisas que o desenho revela e que costumam cair em prova):
- Graus (número de arestas incidentes) de cada porto:
- Observação: só
e são folhas (grau ). - O grafo é conectado: existe um caminho entre qualquer par de vértices (por exemplo, de
até via — — — —ã — — — ).
Passo 7
Desenho esquemático (passo a passo para traçar no caderno). Dicas: posicione os vértices em posições que lembrem, grosseiramente, a geografia: Europa à esquerda-cima, Brasil à esquerda-baixo, África e Índia no meio, Sudeste Asiático e Oceania à direita. Depois ligue com linhas. Abaixo há um desenho ASCII esquemático que você pode copiar tal qual; linhas representam arestas. (A arte ASCII é só um esquema para prova — no caderno você pode desenhar vértices circulares e ligar com linhas retas.)
(Lisboa)
|
(Roterdã)
|
(Hamburgo) --- (Cingapura) --- (Sydney) --- (Auckland)
|
(Rio de Janeiro)
|
(Cidade do Cabo)
|
(Mumbai)
Explicando o esquema:
-
conecta para cima a e para baixo a . -
segue para que segue paraã . -
liga a que segue até e depois . -
liga para .
Passo 8
Como apresentar isso na prova (o que costuma pedir o professor):
- Se pedirem “desenhe o grafo”, copie o esquema ASCII trocando os nomes por bolinhas com os nomes ao lado e ligue com linhas.
- Se pedirem "escreva
", use a definição de e que dei no Passo 3. - Se pedirem “grau dos vértices” ou “matriz/adjacência”, use o Passo 4 e Passo 5.
- Se pedirem “é conexo?”, responda que sim e, se pedirem, apresente um caminho entre quaisquer dois vértices (por exemplo do passo 6).
Resposta
(Lisboa)
|
(Roterdã)
|
(Hamburgo) --- (Cingapura) --- (Sydney) --- (Auckland)
|
(Rio de Janeiro)
|
(Cidade do Cabo)
|
(Mumbai)