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 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 estados de um país, usando vértices para representar os estados e arestas para indicar se um determinado estado tem divisa geográfica com outro estado: se um estado A tem divisa com outro estado B ligamos os dois vértices que representam os estados A e B com uma aresta.

Questão 1. A figura abaixo à esquerda mostra um grafo que representa as divisas entre estados de um país que tem cinco estados; a figura abaixo à direita mostra cinco mapas.

Na figura acima, o grafo à esquerda representa as divisas entre estados de qual dos mapas?
Mapa 1
Mapa 2
Mapa 3
Mapa 4
Mapa 5

Questão 2. No grafo da figura abaixo os vértices representam os bairros de uma cidade (bairros são identificados por letras). Cada aresta indica que o par de bairros ligados pela aresta são vizinhos geográficos (ou seja, fazem divisa um com o outro). Como o povo da cidade é fanático por voleibol, a prefeitura decidiu construir ginásios de voleibol em alguns bairros, mas com a seguinte restrição: se um ginásio de voleibol é construído em um determinado bairro, em nenhum bairro que seja vizinho (que tenha divisa) com esse bairro um outro ginásio de voleibol será construído. Por exemplo, se um ginásio for construído na cidade A, nenhum ginásio será construído nas cidades B, E ou C.

Qual das alternativas seguintes é uma lista correta de cidades em que um ginásio de voleibol pode ser construído, considerando em cada cidade da lista será construído um ginásio de voleibol?
A, F, H
A, C, E, H
B, C, E, H
B, C, F, G
B, C, G

Tarefas Iniciação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação