ผลต่างระหว่างรุ่นของ "Icpc-train-2014/graphs"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 29: | แถว 29: | ||
** Negative cycle cancellation algorithm | ** Negative cycle cancellation algorithm | ||
** Cheapest augmentation algorithm | ** Cheapest augmentation algorithm | ||
| + | |||
| + | == References == | ||
| + | * Graph theory | ||
| + | ** [http://diestel-graph-theory.com/ Diestel] Graph Theory (free to read online). | ||
| + | ** [http://cs.bme.hu/fcs/graphtheory.pdf] | ||
| + | ** [ http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_Bondy_Murty.pdf Bondy Murty] | ||
| + | * Flows | ||
| + | ** [https://archive.org/details/networkflows00ahuj Ahuja, Magnanti, Orlin] Network flows (very old version) | ||
รุ่นแก้ไขเมื่อ 05:15, 2 พฤศจิกายน 2557
Outlines
- Basic definitions
- Graph search
- Properties of DFS and BFS
- Topological ordering, DAG, strongly connected components
- Coloring
- Vertex coloring
- Edge coloring
- Euler tour
- MST
- Red/blue rules
- Shortest paths
- Optimality criteria
- Dijkstra's algorithm
- Graphs with negative weights: Bellman-Ford algorithm, Johnson's algorithm
- Finding negative cycles
- Maximum flows
- Ford-Fulkerson algorithm
- Flow decomposition
- Weakly-poly time: largest augmentation
- Strongly-poly time algorithm: Edmond-Karp
- Blocking-flow algorithms
- Bipartite matching
- Unit networks
- Other properties for bipartite matching
- Min-cost flows
- Optimality criteria
- Negative cycle cancellation algorithm
- Cheapest augmentation algorithm
References
- Graph theory
- Diestel Graph Theory (free to read online).
- [1]
- [ http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_Bondy_Murty.pdf Bondy Murty]
- Flows
- Ahuja, Magnanti, Orlin Network flows (very old version)
