ผลต่างระหว่างรุ่นของ "Icpc-train-2014/graphs"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '== Outlines == * Basic definitions * Graph search ** Properties of DFS and BFS ** Topological ordering, DAG, strongly connected compon...') |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 6: | แถว 6: | ||
** Topological ordering, DAG, strongly connected components | ** Topological ordering, DAG, strongly connected components | ||
* Coloring | * Coloring | ||
| + | ** Vertex coloring | ||
| + | ** Edge coloring | ||
* Euler tour | * Euler tour | ||
* MST | * MST | ||
| แถว 19: | แถว 21: | ||
** Weakly-poly time: largest augmentation | ** Weakly-poly time: largest augmentation | ||
** Strongly-poly time algorithm: Edmond-Karp | ** Strongly-poly time algorithm: Edmond-Karp | ||
| + | ** Blocking-flow algorithms | ||
** Bipartite matching | ** Bipartite matching | ||
| − | ** | + | ** Unit networks |
| − | ** | + | ** Other properties for bipartite matching |
* Min-cost flows | * Min-cost flows | ||
| + | ** Optimality criteria | ||
| + | ** Negative cycle cancellation algorithm | ||
| + | ** Cheapest augmentation algorithm | ||
รุ่นแก้ไขเมื่อ 04:54, 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
