XXVI Olimpíada Brasileira de Informática

Grafos

Em computação um grafo é uma estrutura composta de vértices (mostrados como círculos nas figuras abaixo) e arestas (mostradas como linhas que conectam os círculos). Grafos são utilizados para modelar uma infinidade de situações na vida real, como rodovias que existem entre cidades ou pessoas que se conhecem. Grafos podem também ser usados para modelar as divisas entre países, usando vértices para representar os países e arestas para indicar se um determinado país tem divisa com outro país: se um país A tem divisa com outro país B ligamos os dois vértices que representam os países A e B com uma aresta.

Questão 1. A figura abaixo mostra um grafo e cinco mapas. O grafo representa as divisas entre países de qual dos mapas?


Mapa 1
Mapa 2
Mapa 3
Mapa 4
Mapa 5

Questão 2. A figura abaixo mostra um mapa e cinco grafos. Qual o grafo que representa as divisas entre países do mapa?


Grafo 1
Grafo 2
Grafo 3
Grafo 4
Grafo 5

Tarefas Iniciação Nível Júnior
Promoção
logo sbc
Patrocínio
Apoio
Coordenação