ผลต่างระหว่างรุ่นของ "Icpc-train-2014/graphs"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 3 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 19: | แถว 19: | ||
** Ford-Fulkerson algorithm | ** Ford-Fulkerson algorithm | ||
** Flow decomposition | ** Flow decomposition | ||
| − | ** Weakly- | + | ** Weakly poly-time: largest augmentation |
| − | ** Strongly- | + | ** Strongly poly-time algorithm: Edmond-Karp |
** Blocking-flow algorithms | ** Blocking-flow algorithms | ||
** Bipartite matching | ** Bipartite matching | ||
| แถว 29: | แถว 29: | ||
** Negative cycle cancellation algorithm | ** Negative cycle cancellation algorithm | ||
** Cheapest augmentation algorithm | ** Cheapest augmentation algorithm | ||
| + | * Special graphs | ||
| + | ** Trees | ||
| + | ** Cycles | ||
| + | ** Grid graphs | ||
| + | ** Planar graphs | ||
| + | ** Chordal graphs | ||
== References == | == References == | ||
* 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 and Murty, Graph Theory with Applications] |
* 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) | ||
รุ่นแก้ไขปัจจุบันเมื่อ 15:03, 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
- Special graphs
- Trees
- Cycles
- Grid graphs
- Planar graphs
- Chordal graphs
References
- Graph theory
- Diestel Graph Theory (free to read online).
- Lecture notes by Tero Harju
- Bondy and Murty, Graph Theory with Applications
- Flows
- Ahuja, Magnanti, Orlin Network flows (very old version)
