XXVI Olimpíada Brasileira de Informática

Grafos

Em computação um grafo é uma estrutura composta de vértices (mostrados como círculos na figura (a) 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 estradas 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 X tem divisa com outro país Y ligamos os dois vértices que representam os países X e Y com uma aresta. Por exemplo, a figura (a) abaixo representa as divisas do mapa da figura (b).

Questão 1. A figura abaixo mostra um grafo e cinco mapas. Na figura, 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. Um grafo representando as estradas entre oito cidades -- A, B, C, D, E, F, G e H -- contém oito arestas: A--C, A--G, A--H, B--C, C--F, D--E, E--C e F--H. Se um vendedor deseja sair de uma cidade qualquer e visitar o maior número de cidades, usando apenas as estradas do grafo, sem passar mais de uma vez pela mesma cidade, qual o maior número de cidades que ele pode visitar (contando com a cidade da qual ele sai)?
4
5
6
7
8

Questão 3. Continuando a questão anterior, qual das alternativas abaixo é uma cidade em que o vendedor pode iniciar sua viagem?
A
E
D
B
H

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