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 V e um conjunto de arestas E. Escrevemos isso como G=(V,E).
  • 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 \{u,v\}.
  • Duas representações úteis e fáceis de desenhar numa prova:
    1. lista de adjacência (para cada vértice, quem são os vizinhos);
    2. 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 V (os portos). Vou nomeá-los com o nome completo para ficar claro:
V = \{\text{Rio de Janeiro},\\ \text{Lisboa},\\ \text{Roterdã},\\ \text{Hamburgo},\\ \text{Cidade do Cabo},\\ \text{Mumbai},\\ \text{Cingapura},\\ \text{Sydney},\\ \text{Auckland}\}.ã
Listar as arestas E como pares não-ordenados (peguei cada par do enunciado):
\begin{aligned} E = \{&\{\text{Rio de Janeiro},\\ \text{Lisboa}\},\\\ &\{\text{Lisboa},\\ \text{Roterdã}\},\\\ &\{\text{Roterdã},\\ \text{Hamburgo}\},\\\ &\{\text{Rio de Janeiro},\\ \text{Cidade do Cabo}\},\\\ &\{\text{Cidade do Cabo},\\ \text{Mumbai}\},\\\ &\{\text{Cingapura},\\ \text{Sydney}\},\\\ &\{\text{Sydney},\\ \text{Auckland}\},\\\ &\{\text{Hamburgo},\\ \text{Cingapura}\}\}. \end{aligned}ãã

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:
\begin{aligned} \text{Rio de Janeiro}:&\\ \{\text{Lisboa},\\ \text{Cidade do Cabo}\}\\\ \text{Lisboa}:&\\ \{\text{Rio de Janeiro},\\ \text{Roterdã}\}\\\ \text{Roterdã}:&\\ \{\text{Lisboa},\\ \text{Hamburgo}\}\\\ \text{Hamburgo}:&\\ \{\text{Roterdã},\\ \text{Cingapura}\}\\\ \text{Cidade do Cabo}:&\\ \{\text{Rio de Janeiro},\\ \text{Mumbai}\}\\\ \text{Mumbai}:&\\ \{\text{Cidade do Cabo}\}\\\ \text{Cingapura}:&\\ \{\text{Hamburgo},\\ \text{Sydney}\}\\\ \text{Sydney}:&\\ \{\text{Cingapura},\\ \text{Auckland}\}\\\ \text{Auckland}:&\\ \{\text{Sydney}\} \end{aligned}ããã
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 A é 9\times9 com entradas A_{ij}=1 se há aresta entre o vértice i e j, e 0 caso contrário. Ordenação: 1=\text{Rio de Janeiro},\\\ 2=\text{Lisboa},\\\ 3=\text{Roterdã},\\\ 4=\text{Hamburgo},\\\ 5=\text{Cidade do Cabo},\\\ 6=\text{Mumbai},\\\ 7=\text{Cingapura},\\\ 8=\text{Sydney},\\\ 9=\text{Auckland}ã. Então
A= \begin{pmatrix} 0&1&0&0&1&0&0&0&0\\\\ 1&0&1&0&0&0&0&0&0\\\\ 0&1&0&1&0&0&0&0&0\\\\ 0&0&1&0&0&0&1&0&0\\\\ 1&0&0&0&0&1&0&0&0\\\\ 0&0&0&0&1&0&0&0&0\\\\ 0&0&0&1&0&0&0&1&0\\\\ 0&0&0&0&0&0&1&0&1\\\\ 0&0&0&0&0&0&0&1&0 \end{pmatrix}.
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:
\begin{aligned} \deg(\text{Rio de Janeiro})&=2,\\\ \deg(\text{Lisboa})&=2,\\\ \deg(\text{Roterdã})&=2,\\\ \deg(\text{Hamburgo})&=2,\\\ \deg(\text{Cidade do Cabo})&=2,\\\ \deg(\text{Mumbai})&=1,\\\ \deg(\text{Cingapura})&=2,\\\ \deg(\text{Sydney})&=2,\\\ \deg(\text{Auckland})&=1. \end{aligned}ã
  • Observação: só \text{Mumbai} e \text{Auckland} são folhas (grau 1).
  • O grafo é conectado: existe um caminho entre qualquer par de vértices (por exemplo, de \text{Mumbai} até \text{Auckland} via \text{Cidade do Cabo} \text{Rio de Janeiro} \text{Lisboa} \text{Roterdã}ã \text{Hamburgo} \text{Cingapura} \text{Sydney} \text{Auckland}).

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:
  • \text{Rio de Janeiro} conecta para cima a \text{Lisboa} e para baixo a \text{Cidade do Cabo}.
  • \text{Lisboa} segue para \text{Roterdã}ã que segue para \text{Hamburgo}.
  • \text{Hamburgo} liga a \text{Cingapura} que segue até \text{Sydney} e depois \text{Auckland}.
  • \text{Cidade do Cabo} liga para \text{Mumbai}.

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 G=(V,E)", use a definição de V e 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

V = \{\text{Rio de Janeiro},\\ \text{Lisboa},\\ \text{Roterdã},\\ \text{Hamburgo},\\ \text{Cidade do Cabo},\\ \text{Mumbai},\\ \text{Cingapura},\\ \text{Sydney},\\ \text{Auckland}\}ã
\begin{aligned} E = \{&\{\text{Rio de Janeiro},\\ \text{Lisboa}\},\\ \{\text{Lisboa},\\ \text{Roterdã}\},\\ \{\text{Roterdã},\\ \text{Hamburgo}\},\\\ &\{\text{Rio de Janeiro},\\ \text{Cidade do Cabo}\},\\ \{\text{Cidade do Cabo},\\ \text{Mumbai}\},\\\ &\{\text{Cingapura},\\ \text{Sydney}\},\\ \{\text{Sydney},\\ \text{Auckland}\},\\ \{\text{Hamburgo},\\ \text{Cingapura}\}\} \end{aligned}ãã
                  (Lisboa)
                    |
                 (Roterdã)
                    |
                 (Hamburgo) --- (Cingapura) --- (Sydney) --- (Auckland)
                    |
             (Rio de Janeiro)
                    |
             (Cidade do Cabo)
                    |
                  (Mumbai)

Exercícios relacionados