UNIVERSIDADE FEDERAL DE SANTA CATARINA
DEPTO DE INFORMÁTICA E ESTATÍSTICAS – INE 5413 – Recuperação 03/12/2009
1)
(1,0) Seja o grafo G(V,A) dado por:
V = { p | p é uma estudante da UFSC }
A = { (v,w) | < v é colega de curso de w > }
Marque V(verdade) ou F(falso) em cada uma dos itens que se seguem (cada marcação errada anula uma certa):
I – A relação A é simétrica;
II – A relação A é transitiva;
III – A relação A é reflexiva;
IV – O grafo G é orientado;
2)
(1,0) Seja o grafo G ao lado. Marque V(verdade) ou F(falso) em cada uma dos
itens que se seguem (cada marcação errada anula uma certa):
I – G é um grafo planar;
II – G é um grafo completo;
III – O número cromático de G é 3;
IV – G tem 2 componentes conexas;
3)
(1,0) Sejam G1 e G2 dois grafos eulerianos sem vértices em comum. Seja v1 um vértice de G1 e v2 um vértice de G2. Seja G
um grafo consistindo da união de G1 e G2 juntamente com a aresta (v1,v2). O que pode ser dito a respeito de G? (cada
marcação errada anula uma certa):.
I – G sempre contém exatamente 1 (uma) ponte;
II – G é conexo;
III – G é euleriano;
IV – G pode conter mais do que 2 (dois) vértices de corte;
4)
(1,0) Seja G(V,A) um grafo não orientado sem laços e sem arestas múltiplas. Considere o algoritmo que se segue:
n ← ordem(G) – 1;
Para cada v ∈ vértices(G) faça
Se grau(G,v) ≠ n então
Retorna falso
Fim se
Fim
Retorna verdade
Qual a propriedade de grafos (dentre as vistas durante o semestre) que é verificada por este algoritmo?
5) (1,0) Seja G um grafo não orientado, desconexo, sem laços, sem arestas múltiplas e de ordem n. Marque V(verdade) ou
F(falso) em cada uma dos itens que seguem (cada marcação errada anula uma certa):
I - Pelo menos dois de seus vértices não estão ligados por cadeia alguma;
II - Se n = 10, então G pode ser formado por vértices de graus 2, 6 , 3, 4, 5, 1, 4, 8, 6, 4;
III - O tamanho de G (número de arestas) ≤ n(n-1)/2;
IV – O grau do vértice de maior grau ≤ n-2;
6) (1,0) A empresa Internet Floripa S.A. possui um conjunto de centrais distribuídas pela Ilha de Santa Catarina. De cada
central partem conexões capilares para um grande número de residências (seus usuários). Como forma de melhorar a
qualidade do serviço aos seus usuários, esta empresa resolveu refazer as conexões entre as centrais, substituindo os atuais
cabos por fibra ótica de forma a propiciar conexões de altíssimas velocidades entre as centrais. O responsável técnico
construiu um grafo G(V,A) com as possibilidades de conexão entre as centrais, dado por: V={v| v é uma central}; A={(x, y,
c) | o custo para conectar as centrais x e y é de c unidades monetárias}. Numa primeira etapa esta empresa pretende apenas
garantir a conexão mínima entre as centrais, com o menor custo possível. Como se poderia determinar quais conexões
deveriam ser implantadas de imediato?
a)
Procurar a SCIE Minimal de menor cardinalidade e conectar estes vértices aos seus adjacentes considerando
as arestas de menor custo;
b) Obter o ciclo hamiltoniano de custo mínimo;
c) Escolher um vértice qualquer e computar os caminhos de custo mínimo deste vértice para os demais
vértices do grafo;
d) Obter uma árvore T’(V, A’), A’⊆A cuja somatória dos custos das arestas seja mínimo;
e) Calcular o fluxo máximo entre as centrais, e selecionar as caminhos que contenham arestas saturadas;
7) (2,0) No Campus da UFSC, deseja-se instalar câmeras de observação de modo que se tenha uma visão de todo o
campus. Para isto, o campus foi dividido em várias áreas que abrangem todo o campus. Em cada área foram
identificados pontos (um ou mais) candidatos a instalação das câmeras de observação. Uma característica de
cada um destes pontos é que dele se pode observar toda a área onde ele está, mas também permite a observação
de outras áreas e de outros pontos de observação próximos. Esta relação de vigilância (quais áreas e pontos
podem ser observadas a partir de quais pontos) já foi determinada pela equipe de segurança do campus. Como
em muitos casos observou-se que de um mesmo ponto de observação pode-se vigiar mais de uma área, a direção
do campus optou por procurar instalar o menor número de câmeras de forma a reduzir o custo de implantação do
sistema. Como se poderia identificar este conjunto mínimo de câmeras necessárias? Defina um modelo de grafos
G(V,A) para este problema e discorra sobre como farias para identificar onde deveriam ser instalados as câmeras
de observação.
8) (2,0) Considere a hierarquia de classes de uma linguagem de programação orientada a objetos.
a) presente um modelo de grafos G(V,A) que represente esta hierarquia;
b) em que situações é possível que haja ciclos neste grafo definido no item a)? Justifique sua resposta;
c) apresente um exemplo de hierarquia baseada no modelo descrito em a) e neste exemplo identifique os
vértices correspondentes à base, anti-base, raiz, anti-raiz, conforme o caso;
d) o que se pode afirmar sobre a planaridade desta família de grafos?