Material da aula de representação e busca em grafos

Resumo da aula
Grafos: vértices e arestas;
Conceitos: grafos (não-)direcionados, simples, (des)conexo, euleriano, halmiltoniano, árvore, ciclo;
Representações: Matriz ou lista de adjacência

Problemas que tem grafos que foram apresentados (o nome técnico):
Bipartite Matching
Fluxo Máximo (Maxflow)
8-puzzle
Shortest Path
Traveling Salesman Problem
Data Recovery (procurem por Live Archive Data Recovery no Google)
Ciclo formado de todas as peças de um dominó do formato (a,b), a<b<=n (se é possível)
Pontes de Konigsberg

DFS implementação e exemplos de problemas (teste de conexidade, contagem de componentes conexas e menor maior aresta)
BFS implementação e menor caminho sem pesos

Os vídeos da semana:
De Stanford, Algorithms Part II (https://class.coursera.org/algo2-2012-001/lecture/index):
II. Graph Representations [Part I Review] - estou mandando esse vídeo porque é a versão resumida e com o conteúdo mais focado pro que a gente vai usar

De Stanford, Algorithms, Part I (https://class.coursera.org/algo-2012-002/lecture/index):
X. Graph Search Overview
X. Breath-First Search (BFS): The Basics
X. BFS and Shortests Paths
X. BFS and Undirected Connectivity
X. Depth-First Search (DFS): the Basics

O resto vocês podem ir vendo, como sempre, mas não vão ser muito úteis nos problemas e na próxima aula.

Os problemas:
UVa 439: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=380
USACO Demo Bronze, problemas 11 e 12: http://cerberus.delos.com:790/contestgate
SPOJ PT07Y: http://www.spoj.com/problems/PT07Y/
Live Archive 2613: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=614
Codeforces Quarrel: http://codeforces.com/problemset/problem/29/E
Live Archive 5127: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3128

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License