Universidade Federal do Espírito Santo
Departamento de Informática
Profª Claudia Boeres
Teoria dos Grafos - 2014/2
Trabalho Computacional
1. Objetivo
•
Estudo e implementação de algoritmos para resolução de
problemas de grafos.
2. Trabalho em grupo
•
Esse trabalho deve ser elaborado por um grupo de 2
pessoas, cuja composição deve ser informada previamente.
3. Tarefas
•
No item 4 são apresentados doze problemas que podem ser
modelados como problemas em grafos. Cada grupo deve
escolher um problema para implementar e realizar testes
computacionais.
Detalhes
de
implementação
e
a
apresentação dos resultados devem ser organizados na
forma de slides e apresentados como um seminário.
Os
slides devem conter os seguintes itens:
a) a representação computacional escolhida para o grafo do
problema resolvido e das demais estruturas de dados, se
utilizadas.
b) indicar qual dos algoritmos de grafos apresentados em sala foi
utilizado na resolução.
c) pseudo-código do algoritmo implementado, destacando seus
detalhes de implementação.
d) mostrar quais conjuntos de teste foram elaborados.
e) mostrar a execução do algoritmo para dois conjuntos de teste
escolhidos dentre todos os elaborados.
f) Conclusões
4. Descrição dos problemas
•
Problema 1: Reconexão de computadores em rede
Considere o problema de selecionar um conjunto de T cabos de alta
velocidade para conexão de N computadores, de um universo de M
cabos de alta velocidade. Um cabo de alta velocidade pertencente a
M conecta um par de computadores e possui um custo mensal de
utilização. O objetivo do problema é minimizar o custo mensal
total de conectar N computadores em rede, sabendo-se que esse
custo é dado pela soma dos custos de cada cabo incluído no
conjunto T. Considere agora que os N computadores já estão
conectados por T ⊆ M, mas que K novos cabos de alta velocidade
tornaram-se recentemente disponíveis. Faça um programa que compute
um novo conjunto T' de cabos de alta velocidade para reconectar os
N computadores, de maneira que o custo total de T' seja menor ou
igual ao obtido pelo conjunto T, sabendo-se que nesta nova
configuração existem M + K cabos de alta velocidade disponíveis
para a conexão dos N computadores. Use o algoritmo de Prim na
resolução desse problema.
Entrada de Dados
A entrada de dados consiste em um arquivo composto de vários
conjuntos de teste, dispostos em sequência no arquivo e separados
por uma linha em branco. A organização das linhas de cada conjunto
de teste é dada por:
•
•
•
•
•
A primeira linha do conjunto de teste contém o número N de
computadores a serem conectados, com 1 ≤ N ≤ 100000;
A segunda linha do conjunto de teste contém o número M de
cabos de conexão, com N-1 ≤ M ≤ N(N-1)/2;
As próximas M linhas do conjunto de teste descrevem cada cabo
de conexão pertencente a M. Cada uma dessas linhas devem
conter os números identificadores dos computadores que são
ligados por aquele cabo, além do seu custo de utilização. Os
N computadores são rotulados de 1 a N e os custos de
utilização dos cabos são valores inteiros.
A linha seguinte deve conter o número K de cabos de conexão
adicionais considerados, com 1 ≤ K ≤ min {10, N(N-1)/2 – M};
K linhas, cada uma contendo informações de cada novo cabo de
conexão, ou seja, os números identificadores dos computadores
que são ligados por aquele cabo, além do seu custo de
utilização. O custo de utilização é definido como um valor
inteiro.
Saída de Dados
O arquivo de saída deve conter cada linha (separada por linhas em
branco) referente à resposta do seu programa para cada conjunto de
teste. Assim, cada linha possui duas informações: a primeira é o
custo de conexão dos N computadores (custo total do conjunto T)
quando foram considerados M cabos de conexão; e a segunda é o
custo total de T', quando foram considerados M+K cabos de conexão.
Se o custo de T' for igual ao de T, então o valor gerado desse
custo deve aparecer duas vezes na linha.
Exemplo
Entrada
Saída
5
6
1
1
1
1
3
4
1
2
20 17
6
6
1
1
2
3
4
5
2
1
3
2
3
4
5
4
5
5
5
5
5
8
8
16 9
3 2
2
6
3
4
5
6
5
2
2
8
3
4
4 1
6 1
•
Problema 2: Reconexão de computadores em rede
Considere o problema de selecionar um conjunto de T cabos de alta
velocidade para conexão de N computadores, de um universo de M
cabos de alta velocidade. Um cabo de alta velocidade pertencente a
M conecta um par de computadores e possui um custo mensal de
utilização. O objetivo do problema é minimizar o custo mensal
total de conectar N computadores em rede, sabendo-se que esse
custo é dado pela soma dos custos de cada cabo incluído no
conjunto T. Considere agora que os N computadores já estão
conectados por T ⊆ M, mas que K novos cabos de alta velocidade
tornaram-se recentemente disponíveis. Faça um programa que compute
um novo conjunto T' de cabos de alta velocidade para reconectar os
N computadores, de maneira que o custo total de T' seja menor ou
igual ao obtido pelo conjunto T, sabendo-se que nesta nova
configuração existem M + K cabos de alta velocidade disponíveis
para a conexão dos N computadores. Use o algoritmo de Kruskal na
resolução desse problema.
Entrada de Dados
A entrada de dados consiste em um arquivo composto de vários
conjuntos de teste, dispostos em sequencia no arquivo e separados
por uma linha em branco. A organização das linhas de cada conjunto
de teste é dada por:
•
•
•
•
•
A primeira linha do conjunto de teste contém o número N de
computadores a serem conectados, com 1 ≤ N ≤ 100000;
A segunda linha do conjunto de teste contém o número M de
cabos de conexão, com N-1 ≤ M ≤ N(N-1)/2;
As próximas M linhas do conjunto de teste descrevem cada cabo
de conexão pertencente a M. Cada uma dessas linhas devem
conter os números identificadores dos computadores que são
ligados por aquele cabo, além do seu custo de utilização. Os
N computadores são rotulados de 1 a N e os custos de
utilização dos cabos são valores inteiros.
A linha seguinte deve conter o número K de cabos de conexão
adicionais considerados, com 1 ≤ K ≤ min {10, N(N-1)/2 – M};
K linhas, cada uma contendo informações de cada novo cabo de
conexão, ou seja, os números identificadores dos computadores
que são ligados por aquele cabo, além do seu custo de
utilização. O custo de utilização é definido como um valor
inteiro.
Saída de Dados
O arquivo de saída deve conter cada linha (separada por linhas em
branco) referente à resposta do seu programa para cada conjunto de
teste. Assim, cada linha possui duas informações: a primeira é o
custo de conexão dos N computadores (custo total do conjunto T)
quando foram considerados M cabos de conexão; e a segunda é o
custo total de T', quando foram considerados M+K cabos de conexão.
Se o custo de T' for igual ao de T, então o valor gerado desse
custo deve aparecer duas vezes na linha.
Exemplo
Entrada
Saída
5
6
1
1
1
1
3
4
1
2
20 17
6
6
1
1
2
3
2
3
4
5
4
5
5
5
5
5
8
8
3 2
2
6
3
4
5
2
2
8
16 9
4
5
2
1
3
5 3
6 4
4 1
6 1
•
Problema 3: Enviando emails
Considere uma rede composta por n servidores SMTP ligados por m
cabos de rede. Cada um dos m cabos conecta dois computadores e tem
uma certa latência medida em milissegundos necessária para enviar
uma mensagem de e-mail. Faça um programa que calcule o menor tempo
necessário para enviar uma mensagem do servidor S ao servidor T
por uma sequência de cabos. Assume-se que não há atrasos
incorridos em qualquer um dos servidores. Use o algoritmo de
Dijkstra na resolução desse problema.
Entrada de Dados
A entrada de dados consiste em um arquivo composto de vários
conjuntos de teste, dispostos em sequencia no arquivo e separados
por uma linha em branco. A organização das linhas de cada conjunto
de teste é dada por:
•
•
A primeira linha do conjunto de teste contém o número n de
computadores a serem conectados, com 2 ≤ n ≤ 20000; o número
m de cabos da rede (0 ≤ m ≤ 50000); e os rótulos
identificadores de S (0 ≤ S < n) e T (0 ≤ T < n), S ≠ T;
As próximas m linhas do conjunto de teste descrevem
informações de cada cabo de rede. Cada uma dessas linhas
devem conter os números identificadores dos servidores
conectados
por
um
cabo
bidirecional
(com
rótulos
identificadores no intervalo [0, n-1]), além do valor da
latência w, ao longo do cabo (0 ≤ w ≤ 10000).
Saída de Dados
O arquivo de saída deve conter cada linha (separada por linhas em
branco) referente à resposta do seu programa para cada conjunto de
teste. Assim, cada linha deve possuir a informação do número de
milissegundos requeridos para enviar uma mensagem de S a T. Se há
um caminho entre S e T, a mensagem emitida pelo programa deve ser
“Envio de mensagens de <S> a <T>: <tempo em ms>.”. Caso contrário,
a mensagem deve ser: “Envio de mensagens de <S> a <T>: não há
caminho entre <S> e <T>.”.
Exemplo
Entrada
Saída
3
0
0
1
3
1
2
2
2 0
100
200
50
Envio de mensagens de 2 a 0: 150.
5
0
0
0
1
2
3
6
1
3
4
2
3
4
0 2
5
2
1
2
2
1
6
0
0
0
1
2
3
6
1
3
4
2
3
4
0 5
5
2
1
2
2
1
Envio de mensagens de 0 a 2: 4.
Envio de mensagens de 0 a 5: não há caminho entre 0 e 5.
•
Problema 4: Navegando nas páginas da web
Recentemente foi relatado que, em média, apenas 19 cliques são
necessários para sair de uma página e migrar para qualquer outra
na
World Wide Web. Isto é, se representamos as páginas na web
como nós em um grafo, então o comprimento médio dos caminhos
entre pares arbitrários de nós no grafo é 19.
Dado um grafo orientado em que todos os nós são atingíveis a
partir de qualquer ponto de partida, faça um programa que encontre
o comprimento médio dos caminhos mais curtos entre todos os pares
arbitrários de nós. Por exemplo, considere um grafo orientado com
quatro vértices com as seguintes listas de sucessores:
+
+
+
+
Γ (1) = {2,3}, Γ (2) = {4}, Γ (3) = {1} e Γ (4) = {3}. O grafo é
orientado, pois se existe um link de uma página A para uma página
B, não necessariamente existe um link de B para A. Considerando os
custos dos arcos unitários, podemos observar facilmente que os
comprimentos dos menores caminhos do vértice 1 para os vértices 2,
3 e 4 são respectivamente 1, 1 e 2. Do nó 2 para os nós 1, 3 e 4,
os comprimentos dos menores caminhos são 3, 2 e 1, e desta forma
podemos obter os comprimentos dos menores caminhos a partir de
todos os nós para todos os outros nós do grafo. Se considerarmos a
soma dos comprimentos dos menores caminhos de cada vértice para
todos os outros e dividirmos para o número total de pares de
vértices, obteremos a média do número de clicks para navegar de
uma página a outra na web. Neste exemplo, para um digrafo de 4 nós
e essa topologia, teríamos a média de 22/12 = 1.83 clicks. Use o
algoritmo de Floyd-Warshall na resolução desse problema.
Entrada de Dados
A entrada de dados consiste em um arquivo composto de vários
conjuntos de teste, cada um representado em uma única linha,
dispostos em linhas em sequencia no arquivo. A organização das
informações de cada conjunto de teste em uma linha é dada por:
•
A linha é composta por um número arbitrário de pares de
inteiros, a e b, cada par representando um link entre uma
página a e uma página b. Os rótulos identificadores das
páginas são valores inteiros pertencentes ao intervalo [1,
100].
A linha representativa do conjunto de teste deve ser
terminada com um par de zeros, que não devem ser tratados
como identificadores de página. Finalizando o arquivo, um par
adicional de zeros deve ser colocado em sua última linha,
representando um conjunto de teste que não é para ser
processado. Considere que o digrafo de representação das
páginas na web é um digrafo simples e f-conexo.
Saída de Dados
O arquivo de saída deve conter cada linha (separada por linhas em
branco) referente à resposta do seu programa para cada conjunto de
teste. Assim, cada linha deve possuir a informação do comprimento
médio dos caminhos mais curtos entre cada par de nós do grafo,
imprimindo a seguinte mensagem: “ comprimento médio dos caminhos
entre as páginas: <valor do comprimento médio> clicks”.
Exemplo
Entrada
Saída
1 2 2 4 1 3 3 1 4 3 0 0
1 2 1 4 4 2 2 7 7 1 0 0
0 0
Comprimento médio dos caminhos mínimos entre
as páginas = 1.83 clicks.
•
Comprimento médio dos caminhos mínimos entre
as páginas = 1.75 clicks.
Problema 5: Largura de Banda de Internet
Em uma rede de máquinas conectadas à Internet, altamente
interligadas entre si, podem existir inúmeros caminhos para a
transmissão de mensagens entre um determinado par de máquinas. A
capacidade total de transporte de mensagem (largura de banda)
entre dois nós dados é a quantidade máxima de dados por unidade de
tempo que pode ser transmitida a partir de um nó para outro.
Usando uma técnica chamada de comutação de pacotes, estes dados
podem ser transmitidos ao longo de vários caminhos, ao mesmo
tempo. Por exemplo, a figura a seguir mostra uma rede com quatro
máquinas (representadas por círculos), com um total de cinco
conexões entre elas. Cada conexão é rotulada por seu valor de
largura de banda.
No nosso exemplo, a largura de banda entre o nó 1 e nó 4 é 25, que
pode ser pensada como a soma das larguras de banda 10 ao longo do
caminho 1-2-4, 10 ao longo do caminho 1-3-4, e 5 ao longo da
caminho 1-2-3-4. Nenhuma outra combinação de caminhos entre os nós
1 e 4 fornece uma largura de banda maior. Escreva um programa que
calcula a largura de banda entre dois nós quaisquer de uma rede,
fornecidos como entrada, dadas as larguras de banda associadas a
todas as conexões existentes na rede. Neste problema, assuma que a
largura de banda de uma conexão é sempre a mesma em ambas as
direções (o que nem sempre é necessariamente verdade no mundo
real). Use o algoritmo de Ford-Fulkerson na resolução desse
problema.
Entrada de Dados
O arquivo de entrada contém descrições de várias redes. Cada
descrição inicia-se com uma linha contendo um único número inteiro
n, que é o número de nós da rede. Os nós são numerados de 1 a n. A
próxima linha contém três números s, t, c, que representam
respectivamente o nó fonte, o nó destino e o número total de
conexões na rede. As c linhas seguintes descrevem as conexões da
rede em ordem lexográfica. Cada uma destas linhas contém três
números inteiros: os dois primeiros indicam os rótulos dos nós
ligados por uma conexão e o terceiro número, o valor da sua
largura de banda. A largura de banda é um número não-negativo não
maior do que 1000.
Pode haver no máximo uma ligação entre um par de nós e um nó não
pode ser ligado a ele próprio. Todas as ligações são bidirecionais
(podendo ser representadas sem orientação), ou seja, os dados
podem ser transmitidos em ambos os sentidos ao longo de uma
conexão, mas a soma da quantidade de dados transmitidos em ambos
os sentidos, deve ser menor do que a largura de banda. A linha que
contém o número 0 segue a última descrição da rede, e termina a
entrada.
Saída de Dados
Para a descrição de cada rede, primeiro imprima o número da rede.
Em seguida, imprima a largura de banda total entre o nó de origem
s e o nó destino t, seguindo o formato da saída da amostra.
Imprima uma linha em branco após cada caso de teste.
Exemplo
Entrada
Saída
4
1
1
1
2
2
3
0
Rede 1
A largura de banda é 25.
4
2
3
3
4
4
5
20
10
5
10
20
•
Problema 6: Vulnerabilidade em redes
Uma companhia telefônica está construindo uma nova rede de cabos
de telefonia. A companhia tem por objetivo conectar várias regiões
representadas
por
suas
centrais
telefônicas,
que
estão
identificadas com rótulos inteiros numerados de 1 a N. Duas
centrais distintas não são rotuladas com o mesmo número. Os cabos,
que ligam centrais telefônicas distintas, são representados por
ligações bidirecionais. O grafo que representa a rede telefônica é
conexo, ou seja, existe pelo menos um caminho entre cada par de
centrais telefônicas. De vez em quando é possível que a fonte de
energia de uma central falhe e esta pare de funcionar. Os
funcionários da companhia perceberam que neste caso, além da
própria central ficar inoperante, essa falha pode interromper a
conexão entre outras centrais telefônicas instaladas em outros
lugares. Nestes casos, chamamos o lugar com a central telefônica
inoperante de ponto crítico. Faça um programa que identifique na
rede telefônica, o número de pontos críticos. Use o algoritmo de
busca em profundidade na resolução desse problema.
Entrada de Dados
O arquivo de entrada é composta por vários blocos de linhas
referente a cada conjunto de teste. Cada bloco descreve uma rede.
Na primeira linha de cada bloco há o número de centrais
telefônicas N < 100. As próximas N, no máximo, linhas do arquivo
contém o identificador de uma central telefônica, seguido dos
identificadores de outras centrais as quais ela está ligada
diretamente na rede. Cada conexão direta entre duas centrais na
rede está descrita em pelo menos uma das N linhas. Os
identificadores em cada linha são separados por espaços em branco.
Cada bloco de descrição de uma rede termina com uma linha contendo
apenas o valor 0. O último bloco contém uma linha com N = 0.
Saída de Dados
O arquivo de saída contém, para cada conjunto de teste (com
exceção do último) do arquivo de entrada, o número de pontos
críticos da rede.
Exemplo
Entrada
Saída
5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
0
1
2
•
Problema 7: Calculando o diâmetro de um grafo
O diâmetro de um grafo é o maior valor de excentricidade dos seus
vértices. Os vértices periféricos do grafo são todos aqueles que
possuem excentricidade igual ao diâmetro do grafo. Faça um
programa que, dado um grafo, calcule o diâmetro desse grafo, além
dos seus vértices periféricos. Use o algoritmo de Floyd-Warshall
na resolução desse problema.
Entrada de Dados
O arquivo de entrada é composto por vários blocos de linhas
referente a cada conjunto de teste, separados por uma linha em
branco. Cada bloco descreve um grafo de n vértices e m arestas. Na
primeira linha de cada bloco, os valores de n e m devem ser
indicados, com n < 100. As próximas m linhas devem conter, cada
uma, os rótulos identificadores das arestas do grafo, que devem
ser separados por espaços em branco.
A última linha do arquivo
deve conter apenas a seguinte informação: 0 0.
Saída de Dados
O arquivo de saída contém, para cada conjunto de teste do arquivo
de entrada, o valor do diâmetro do grafo, seguido dos rótulos
identificadores dos seus vértices periféricos (todos separados por
espaços em branco).
Exemplo
Entrada
Saída
7
1
1
1
2
2
3
3
3
4
6
0
417
10
2
4
5
3
4
4
5
6
5
7
0
•
Problema 8: Calculando o raio e o centro de uma árvore
O raio de um grafo é o menor valor de excentricidade dos seus
vértices. O centro do grafo é formado por todos os seus vértices
com excentricidade igual ao raio. Faça um programa que, dada uma
árvore (assumir que a entrada é sempre relativa a árvores),
calcule o raio e o centro dessa árvore. Use o algoritmo de busca
em largura na resolução desse problema.
Entrada de Dados
O arquivo de entrada é composto por vários blocos de linhas
referente a cada conjunto de teste. Cada bloco descreve uma árvore
de n vértices e n-1 arestas. Na primeira linha de cada bloco, o
valor de n deve ser indicado, com n < 100. As próximas n-1 linhas
devem conter, cada uma, os rótulos identificadores das arestas da
árvore, que devem ser separados por espaços em branco. A última
linha do arquivo deve conter apenas a seguinte informação: 0 0.
Saída de Dados
O arquivo de saída contém, para cada conjunto de teste do arquivo
de entrada, o valor do raio da árvore, seguido dos rótulos
identificadores dos vértices do centro da árvore (todos separados
por espaços em branco).
Exemplo
Entrada
Saída
7
1
2
3
3
4
6
0
23
2
3
4
6
5
7
0
•
Problema 9: Caminhos máximos
É um fato conhecido que algumas pessoas tem sempre a tendência de
chegarem atrasadas em seus compromissos... Para muitas delas, isso
ocorre devido a tendência de escolher os maiores caminhos, ao
invés dos menores, de um ponto a outro.
César possui esse tipo de característica. Mas ele possui um
motivo: por ser muito popular, quando ele sai para visitar os
amigos, ele acaba decidindo escolher o maior caminho possível da
casa dele até o último amigo que ele pretende visitar, para, assim
poder visitar todos. Felipe, que é amigo de César, entendeu a
natureza do problema. Por várias vezes ele já ficou por muito
tempo esperando por César. Mas ele não quer deixar de receber a
sua visita, mas também não quer ficar preso em casa o esperando.
Por isso, ele quer encontrar uma maneira de calcular o tempo gasto
por César para percorrer esse caminho, e desta forma, poder fazer
algo de útil enquanto espera por César em sua casa. Para isso, ele
quer saber o comprimento do maior caminho percorrido por César a
partir da casa dele. Ajude Felipe desenvolvendo um programa que
calcule o comprimento do maior caminho que pode ser calculado em
um dado digrafo a partir de um vértice de partida (que representa
a residência do César). Assuma que o digrafo é simples e sem
ciclos. Use o algoritmo de Dijkstra na resolução desse problema.
Entrada de Dados
O arquivo de entrada é composto por vários blocos de linhas
referente a cada conjunto de teste. Na primeira linha de cada
bloco, o valor de n (ordem do grafo) deve ser indicado, com 1 < n
 100, representando o número de lugares que César tem que
visitar. A próxima linha deve conter o valor de s, 1  s  100,
que representa o ponto de partida do percurso traçado por César.
As próximas m linhas devem conter, cada uma, os rótulos
identificadores dos arcos do digrafo, um par por linha, que devem
ser separados por espaços em branco. O par p q indica que César
pode visitar q depois de visitar p. A linha após cada conjunto de
teste deve conter apenas a seguinte informação: 0 0.
Saída de Dados
O arquivo de saída contém, para cada conjunto de teste do arquivo
de entrada, o comprimento do maior caminho que começa em um ponto
inicial dado. Imprima na mesma linha o rótulo do vértice inicial e
o rótulo do vértice final deste caminho. Se existem vários
caminhos de maior tamanho com o mesmo comprimento, imprima o
rótulo final de menor valor. Imprima uma linha para cada caso de
teste.
Exemplo
Entrada
Saída
2
1
1
0
5
3
1
3
3
2
4
0
5
5
5
5
5
5
4
4
0
1 1 2
4 3 5
2 5 1
2
0
2
5
1
4
5
0
1
2
3
4
1
2
0
•
Problema 10: Aeroportos
O governo de um determinado país em desenvolvimento quer melhorar
o transporte em uma de suas áreas mais inacessíveis, na tentativa
de atrair investimentos. Pesquisas mostraram que a região é
composta de vários locais importantes que deveriam ter acesso
facilitado por um aeroporto. Uma solução trivial, porém cara, é
construir um aeroporto em cada uma dessas regiões. No entanto pode
ser mais barato construir um número menor de aeroportos e
construir estradas que os liguem a todos os locais de interesse.
Considere que as estradas são bidirecionais. Além disso, pode
haver mais do que um caminho possível entre duas regiões
distintas. Considera-se que uma região tem acesso a um aeroporto
se a própria região contém o aeroporto ou se é possível viajar por
estrada para alguma outra região que possua um aeroporto.
São dados neste problema, o custo de construção de um aeroporto e
uma lista de estradas possíveis entre pares de regiões e seus
respectivos custos. Faça um programa que ajude ao governo desse
país a decidir pela maneira mais barata de assegurar que todas as
regiões tem acesso a um aeroporto. Use um algoritmo de árvore
geradora mínima na resolução desse problema.
Entrada de Dados
O arquivo de entrada é composto por vários blocos de linhas
referente a cada conjunto de teste, separados por uma linha em
branco. A primeira linha de cada bloco deve conter os números N (0
< N  10000) de regiões, M (0  M  100000)de possíveis estradas
que podem ser construídas e A (0  A  10000), que representa o
custo de construir um aeroporto. Todos os valores da linha devem
ser separados por espaços em branco. As próximas M linhas devem
conter, cada uma, também três valores x, y e c (1  x, y  N, 0 <
c  10000), separadas por espaços em branco. Os valores x e y
representam duas regiões distintas e c, o custo de construir uma
estrada entre x e y.
Saída de Dados
O arquivo de saída contém, para cada conjunto de teste do arquivo
de entrada, uma linha, com o valor do custo total mínimo de
construir estradas e aeroportos de maneira que as regiões tenham
acesso pelo menos a um aeroporto e o valor seguinte, que
representa o número de aeroportos efetivamente construídos. Se
existem várias respostas com o mesmo custo, escolha aquela que
maximiza o número de aeroportos.
Exemplo
Entrada
Saída
4
1
4
4
2
4
2
3
1
3
100
10
12
41
23
145 1
2090 2
5
1
4
3
3
2
5
2
1000
20
40
30
•
Problema 11: Dominós
O jogo de dominó é muito divertido. As crianças se divertem
posicionando suas peças lado a lado, formando longas filas. Quando
um peça do dominó cai, derruba as outras que estão em sequencia,
destruindo toda a sequência de peças. No entanto, algumas vezes,
uma peça de dominó, ao cair, só derruba a próxima peça e mais
nenhuma. Neste caso, temos que “ajudar”, empurrando com a mão a
próxima peça para derrubá-la e obter o efeito de ver os dominós
caindo outra vez. Faça um programa que determine o número mínimo
de dominós que temos que “ajudar” a cair com a mão, para produzir
o efeito de ver todos os dominós caindo em sequência. Use o
algoritmo de busca em profundidade na resolução desse problema.
Entrada de Dados
O arquivo de entrada é composto por vários blocos de linhas
referente a cada conjunto de teste. A primeira linha de cada bloco
deve conter dois inteiros n e m (0 < n,m  100000). O número n
representa o número de peças de dominó e o valor m é o número de
linhas para seguir. As peças de dominó estão numeradas de 1 a n.
Cada uma das próximas linhas do conjunto de teste possui dois
inteiros x e y, indicando que se o dominó de rótulo x cair, então
o dominó de rótulo y deve cair também. Desta forma, o grafo que
representa como os dominós estão posicionados é direcionado.
Saída de Dados
O arquivo de saída contém, para cada conjunto de teste do arquivo
de entrada, uma linha, com um valor inteiro indicando o número
mínimo de dominós que devem ser derrubados manualmente a fim de
fazer todos os dominós caírem.
Exemplo
Entrada
Saída
3 2
1 2
2 3
1
•
Problema 12: Links críticos
Em uma rede de computadores, um link l, que conecta dois
servidores, é considerado crítico se existem pelo menos dois
servidores A e B tal que todos os caminhos que conectam A a B na
rede, passam por l. Remover esse link gera duas subredes tais que
quaisquer dois servidores de uma subrede estão interconectadas.
Use o algoritmo de busca em profundidade na resolução desse
problema.
É considerado que:
• os links são bidirecionais;
• o grafo da rede é simples;
• dois servidores estão interconectados se estão consectados
diretamente ou se estão conectados com o mesmo servidor;
• o grafo pode ser desconexo.
Escreva um programa que ache os links críticos de uma rede.
Entrada de Dados
O arquivo de entrada é composta por vários blocos de linhas
referente a cada conjunto de teste. Cada bloco descreve uma rede.
Na primeira linha de cada bloco há o número n de servidores da
rede, 0 < n < 100. As próximas n linhas do arquivo, uma para cada
servidor k, 0  k  n - 1, contém o valor do rótulo k, seguido do
número de conexões diretas de k (entre parentesis) e dos rótulos
de todos os servidores que estão ligados diretamente com k. Os
valores em cada linha são separados por espaços em branco. Cada
bloco de descrição de uma rede é separado por uma linha em branco.
Saída de Dados
O arquivo de saída contém, para cada conjunto de teste do arquivo
de entrada, uma linha, com o número de links críticos, seguido dos
pares de rótulos identificadores de cada link crítico. As linhas
do arquivo de saída são separadas por linhas em branco.
Exemplo
Entrada
Saída
8
0
1
2
3
4
5
6
7
3 0 1 3 4 6 7
(1)
(3)
(2)
(3)
(1)
(0)
(1)
(1)
1
0 2 3
1 3
1 2 4
3
7
6
5. Duração do Seminário
•
A apresentação
minutos.
do
seminário
não
deve
ultrapassar
25
6. Instâncias de teste
•
Os algoritmos devem ser executados para pelo menos 5
redes de entrada (a primeira delas deve ser referente
aos exemplos dados para cada problema). As outras 4
redes podem ser geradas com valores distintos de n e m,
mas respeitando o máximo de n = 150 nós. Todas as redes
a serem testadas devem respeitar os formatos de entrada
de dados sugeridos no item 4, de acordo com cada
problema.
7. Linguagem de Programação
•
a escolha da linguagem de programação é livre.
8. Data e procedimento de entrega do trabalho
•
Os códigos-fonte dos algoritmos, os arquivos de entrada,
assim como os slides da apresentação devem ser entregues
no
dia
10/12/2014,
até
12
horas,
para
o
email
[email protected]. Os seminários ocorrerão nos dias
10/12/2014 (quarta-feira) e 12/12/2014 (sexta-feira).