ผลต่างระหว่างรุ่นของ "Icpc-train-2014/graphs"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '== Outlines == * Basic definitions * Graph search ** Properties of DFS and BFS ** Topological ordering, DAG, strongly connected compon...') |
Jittat (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 5 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 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 | ||
| แถว 17: | แถว 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 | ||
** 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 | ||
| + | * Special graphs | ||
| + | ** Trees | ||
| + | ** Cycles | ||
| + | ** Grid graphs | ||
| + | ** Planar graphs | ||
| + | ** Chordal graphs | ||
| + | |||
| + | == References == | ||
| + | * Graph theory | ||
| + | ** [http://diestel-graph-theory.com/ Diestel] Graph Theory (free to read online). | ||
| + | ** [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 and Murty, Graph Theory with Applications] | ||
| + | * Flows | ||
| + | ** [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)
