ผลต่างระหว่างรุ่นของ "Icpc-train-2014/graphs"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 33: | แถว 33: | ||
* Graph theory | * Graph theory | ||
** [http://diestel-graph-theory.com/ Diestel] Graph Theory (free to read online). | ** [http://diestel-graph-theory.com/ Diestel] Graph Theory (free to read online). | ||
| − | ** [http://cs.bme.hu/fcs/graphtheory.pdf] | + | ** [http://cs.bme.hu/fcs/graphtheory.pdf Lecture notes by Tero Harju] |
| − | ** [ http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_Bondy_Murty.pdf Bondy Murty] | + | ** [http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_Bondy_Murty.pdf Bondy Murty] |
* Flows | * Flows | ||
** [https://archive.org/details/networkflows00ahuj Ahuja, Magnanti, Orlin] Network flows (very old version) | ** [https://archive.org/details/networkflows00ahuj Ahuja, Magnanti, Orlin] Network flows (very old version) | ||
รุ่นแก้ไขเมื่อ 05:16, 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).
- Lecture notes by Tero Harju
- Bondy Murty
- Flows
- Ahuja, Magnanti, Orlin Network flows (very old version)
