D1 Matchings 18/10/11

• Reminder of bipartite graphs
• Matchings - trivial, maximal, complete
• Alternating paths to improve matchings
• Exam questions involving matchings

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpMWQzNzJhMjQtZDZhYi00OTFkLTlkOWUtMWUxNmM4NDQxZTYz&hl=en_US

D1 Shortest path 11/10/11

• Using Dijkstra's algorithm to find shortest path

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpYTg5ZTY0Y2QtZDAzMC00NjI1LTk4MWUtYzhmNDU1ZWNkMTM3&hl=en_US

D1 Route inspection 04/10/11

• Reminder of traversable (Eulerian) and semi-traversable (semi-Eulerian) graphs
• The route inspection problem
• Examples of using the route inspection problem

https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2J1T-insOmpMzhlZmYxMGEtZWUxNS00N2U0LThhMjItMjBjZjc3OTNmMDNm&hl=en_US