GBC042 - Teoria dos Grafos - 2º Sem. de 2023 (ref. 1º/2023)

Sobre a disciplina

• Onde: Bloco 1B - Sala 204
• Quando: terças e quartas, 15:00
• Avaliação: a nota final será composta de até 70 (35 + 35) pontos referentes a provas e de até 30 pontos referentes a trabalho.

Avisos

Notas da prova 2
apresentacoes trabalho pratico 28/21 e 29/11. Recuperacao: 5/12 Notas da prova 1
Notas até semana 3
Nos dias 08 e 09 de agosto não haverá aula.

Exercícios-Problemas (EP)

Semana 1 (DFS, BFS): Slides, EP 1, EP 2 (Importante: fazer 2 soluções: 1 com DFS e 1 com BFS), EP 3, EP 4

Semana 2 (Ordenação Topológica): Slides EP1, EP2 EP3

Semana 3 (Pontes e Pontos de Articulação):
EP1: UVa 00315 - Network - Todos fazem.
EP2: UVa 10765 - Doves & Bombs - Só grupos 1, 6, 8, 10
EP3: UVa 12363 - Hedge Mazes - Só grupos 2, 7, 9, 11
EP4: Uva 12783 - Weak Links - Só grupos 1, 3, 8, 10
EP5: Kattis birthday - Só grupos 2, 4, 9, 11
EP6: Kattis caveexploration - Só grupos 1, 3, 5, 10
EP7: UVa 00610 - Só grupos 2,4,6,11
EP8: Kattis kingpinescape - Só grupos 3,5,7
EP9: UVa 00796 - Só grupos 4,6,8
EP10: UVa 10199 - Só grupos 5,7,9

Semana 4 (Componentes Fortemente Conectados): apresentações 05/09/2023
EP1: UVa 11838 - Come and Go - Feito em sala: código.
EP2: UVa 247 - Calling circles - Só grupos 1, 11
EP3: UVa 11709 - Trust Groups - Só grupos 1,2
EP4: UVa 11770 - Lighting away - Só grupos 2,3
EP5: UVa 1229 - Sub-dictionary - Só grupos 3,4
EP6: Kattis cantinaofbabel - Só grupos 4,5
EP7: Kattis dominos - Só grupos 5,6
EP8: Kattis equivalences - Só grupos 6,7
EP9: Kattis loopycabdrivers - Só grupos 7,8,10
EP10: Kattis reversingroads - Só grupos 8,9,11
EP11: Kattis test2 - Só grupos 9,10

Semana 5: Árvores Geradoras e assuntos conectados (union-find, Prim, Kruskal, ...)
EP1: UVa 11228 - Transportation System - Só grupos 1,2
EP2: UVa 11631 - Dark Roads - Só grupos 3,4
EP3: UVa 11474 - Heavy Cycle Edges - Só grupos 5,6
EP4: UVa 00908 - Re-Connecting Computer Sites - Só grupos 7,8
EP5: UVa 01174 - IP-TV - Só grupos 9,10
EP6: UVa 01208 - Oreon - Só grupos 1,11
EP7: Kattis lostmap - Só grupos 2,3
EP8: Kattis minspantree - Só grupos 4,5
EP9: Kattis communicationssatellite - Só grupos 6,7
EP10: Kattis drivingrange - Só grupos 8,9
EP11: Kattis freckles - Só grupos 10,11
EP1 - Apresentação do Grupo 1
EP2 - Apresentação do Grupo 3
EP3 - Não recebido.
EP4 - Apresentação do Grupo 7
EP5 - Não recebido.
EP6 - Apresentação do Grupo 11
EP7 - Apresentação do Grupo 2
EP8 - Apresentação do Grupo 4
EP9 - Apresentação do Grupo 6
EP10 - Não recebido.
EP11 - Apresentação do Grupo 10

Semana 6: Variantes de Árvores Geradoras (entrega antes da aula do dia 19/09/2023)
EP1: UVa 01013 - Island Hopping - Só grupos 1,2,3
EP2: UVa 01216 - The Bug Sensor Problem - Só grupos 4,5,6
EP3: UVa 01235 - Anti Brute Force Lock - Só grupos 7,8,9
EP4: UVa 10457 - Magic Car - Só grupos 10,11
EP5: UVa 01234 - RACING - Só grupo 1
EP6: UVa 10842 - Traffic Flow - Só grupo 2
EP7: UVa 10147 - Highways - Só grupo 3
EP8: UVa 10397 - Connect the Campus - Só grupo 4
EP9: UVa 01216 - Irrigation - Só grupo 5
EP10: UVa 00534 - Frogger - Só grupo 6
EP11: UVa 00544 - Heavy Cargo - Só grupo 7
EP12: UVa 10048 - Audiophobia - Só grupo 8
EP13: UVa 10462 - Is There A Second Way Left? - Só grupo 9
EP14: UVa 10600 - ACM Contest and Blackout - Só grupo 10
EP15: Kattis Arctic Network - Só grupo 11

Semana 7 - Menores caminhos - BFS - Código exemplo UVa 336
EP1: UVa 429 - Word Transformation - Só grupo 1
EP2: UVa 11352 - Crazy King - Só grupo 1
EP3: UVa 10653 - Bombs! NO They Are Mines! - Só grupo 2
EP4: UVa 11792 - Krochanska is Here! - Só grupo 2
EP5: UVa 12160 - Unlock the Lock - Só grupo 3
EP6: UVa 12826 - Incomplete Chessboard - Só grupo 3
EP7: Kattis buttonbashing - Só grupo 4
EP8: Kattis fire2 - Só grupo 4
EP9: Kattis grid - Só grupo 6
EP10: Kattis mallmania - Só grupo 6
EP11: UVa 00388 - Galactic Import - Só grupo 8
EP12: UVa 00314 - Robot (1) - Só grupo 8
EP13: UVa 00627 - The Net - Só grupo 10
EP14: UVa 00383 - Shipping Routes - Só grupo 10
EP15: UVa 00762 - We Ship Cheap - Só grupo 11
EP16: UVa 00859 - Chinese Checkers - Só grupo 11
EP17: UVa 00924 - Spreading the News - Só grupo 12
EP18: UVa 00949 - Getaway - Só grupo 12

Semana 8 - data de entrega adiada para 23/10

EP1: UVa 10067 - Playing with Wheels - Grupo 1
EP2: UVa 10801 - Lift Hopping - Grupo 2
EP3: UVa 11367 - Full Tank? - Grupo 3
EP4: UVa 11492 - Babel - Grupo 4
EP5: UVa 12160 - Unlock the Lock - Grupo 6
EP6: UVa 13127 - Bank Robbery - Grupo 8
EP7 : Kattis getshorty - Grupo 10
EP8 : Kattis emptyingbaltic - Grupo 11
EP9 : Kattis shoppingmalls - Grupo 12

Semana 9 - data de entrega para 23/10

UVa 00821 - Grupo 1
UVa 01247 - Grupo 2
UVa 10354 - Grupo 3
UVa 11463 - Grupo 4
UVa 00341 - Grupo 6
Kattis - allpairspath - Grupo 8
Kattis - importspaghetti - Grupo 10
Kattis - hotels - Grupo 11
Kattis - slowleak - Grupo 12

Problemas opcionais sobre Matching em grafos bipartidos

UVa 11138 - Nuts and Bolts
UVa 00670 - The Dog Task
Kattis - bookclub

Problemas opcionais sobre circuitos Eulerianos

UVa 00291 - The House of Santa
UVa 10054 - The Necklace
UVa 10596 - Morning Walk

Outras informações conectadas a grafos

• Algorithm vizualization
• Data structures vizualization
• U. Washington - CSE417
• How DFS works
DFS, BFS ...
• Graph classes
• Graph matching
• O problema do fluxo máximo
• Minimum spanning trees calculator
• Chromatic index
• MAS341 - Graph Theory
• Open Source Stripe GraphQL API