Antonio Cesar Munari2015-04-30 14-18-41726

Prévia do material em texto

Grafos: Introdução 
 Visão geral do tema e comentários genéricos sobre tipos de problemas que 
podem ser solucionados com grafos, com exemplos. 
 Formas de representação, pelo menos matriz e lista de adjacências. 
 Formas de percurso: bfs e dfs. 
Referência principal: 
 Grafos_UFF\AlgoritmosGrafosParte1.ppt (matriz, lista de adjacências, 
matriz de incidência) 
 Grafos_UFF\AlgoritmosGrafosParte6.ppt (percursos bfs e dfs) 
Referência complementar 
 Curso_UFRJ\aula_1.pdf (conceito e exemplos de problemas com grafos) 
 Curso_UFRJ\aula_2.pdf (mais exemplos de problemas, terminologia e 
propriedades dos grafos) 
 Curso_UFRJ\aula_3.pdf (formas de representação de grafos: matriz de 
adjacência, matriz de incidência, lista de adjacência) 
 Curso_UFRJ\aula_4.pdf (formas de percurso em grafos: ideia geral, bfs e 
dfs, conceito de componentes conexos) 
 Curso_UFRJ\aula_5.pdf (análise detalhada dos algoritmos bfs e dfs; 
conectividade em grafos) 
 Curso_UFRJ\aula_6.pdf (elementos de complexidade de algoritmos) 
 Curso_UFRJ\aula_7.pdf (grafos direcionados, dag’s e ordenação 
topológica) 
Prática: 
 Problema da constelação, com suas 4 implementações básicas (madj+bfs, 
madj+dfs, ladj+bfs, ladj+dfs) 
Problemas indicados: (marcados em negrito são os prioritários) 
 116 – Unidirectional TSP (Vale a pena usar como quebra gelo?) 
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&
page=show_problem&problem=52 
 
 1387 – Transmissão de Energia 
http://br.spoj.com/problems/ENERGIA/ 
 
 2286 – Quantas dependências? 
http://br.spoj.com/problems/DEPENDEN/ 
 
 
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=52
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=52
http://br.spoj.com/problems/ENERGIA/
http://br.spoj.com/problems/DEPENDEN/
 10926 – How Many Dependencies? 
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21
&page=show_problem&problem=1867 
 
 844 – Número de Erdös 
http://br.spoj.com/problems/NUMERDOS/ 
 
 1822 – Natureza 
http://br.spoj.com/problems/NATUREZA/ 
 
 10685 – Nature 
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18
&page=show_problem&problem=1626 
 
 280 – Vertex 
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&
page=show_problem&problem=216 
 
 336 – A node too far 
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&
page=show_problem&problem=272 
 
 18539 – Rodovia 
http://br.spoj.com/problems/RODOVI13/ 
 
 1082 – Componentes conexos 
http://www.urionlinejudge.com.br/judge/pt/problems/view/1082 
 
 1128 – Ir e Vir 
http://www.urionlinejudge.com.br/judge/pt/problems/view/1128 
 
 8304 – Ir e Vir 
http://br.spoj.com/problems/IREVIR/ 
 
 1209 – Festas de São Petersburgo (dá?) 
http://www.urionlinejudge.com.br/judge/pt/problems/view/1209 
 
 1469 – Chefe 
http://www.urionlinejudge.com.br/judge/pt/problems/view/1469 
 
 12648 – Boss 
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=602
&page=show_problem&problem=4377 
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1867
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1867
http://br.spoj.com/problems/NUMERDOS/
http://br.spoj.com/problems/NATUREZA/
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1626
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1626
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=216
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=216
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=272
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=272
http://br.spoj.com/problems/RODOVI13/
http://www.urionlinejudge.com.br/judge/pt/problems/view/1082
http://www.urionlinejudge.com.br/judge/pt/problems/view/1128
http://br.spoj.com/problems/IREVIR/
http://www.urionlinejudge.com.br/judge/pt/problems/view/1209
http://www.urionlinejudge.com.br/judge/pt/problems/view/1469
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=602&page=show_problem&problem=4377
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=602&page=show_problem&problem=4377
 
 762 – We Ship Cheap 
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&
page=show_problem&problem=703 
 
 10004 – Bicoloring 
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12
&page=show_problem&problem=945 
 
 10608 – Friends 
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18
&page=show_problem&problem=1549 
 
 819 – Pedágio 
http://br.spoj.com/problems/PEDAGIO/ 
 
 1332 – Dengue 
http://br.spoj.com/problems/DENGUE/ 
 
 2612 – Buracos de Minhoca 
http://br.spoj.com/problems/BURACOS/ 
 
 1081 – DFSr - Profundidade com Hierarquia 
http://www.urionlinejudge.com.br/judge/pt/problems/view/1081 
 
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=703
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=703
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=945
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=945
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1549
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1549
http://br.spoj.com/problems/PEDAGIO/
http://br.spoj.com/problems/DENGUE/
http://br.spoj.com/problems/BURACOS/
http://www.urionlinejudge.com.br/judge/pt/problems/view/1081