Wintersemester 2004/2005 ist vorbei

周三参加了Graphenalgorithmen Theorie und Algorithmen的考试，这样2004/2005冬季学期就算结束了。这学期上的课真是不多，除了Graphenalgorithmen Theorie und Algorithmen外，就剩下Intelligente Systeme 和Digitale Library.

在准备Graphenalgorithmen Theorie und Algorithmen这门考试而反复阅读笔记的时候，发现上了一学期的课（每周4课时Vorlesung和2课时的Uebung），讲的内容其实并不算是太多，知识内容比较细。在此先简单总结一下课程内容，抽空再把笔记有条理的digitalisiert，因为这是教授第一次开这门课，讲义准备的有时不是很充分。



第一章讲的是图论的基本知识，由于是Hauptstudium的课程，所以一些很基本的定义就没有再重复了，只是简单回顾了一下DFS，topologische Sortierung等算法，并介绍了由教授参与编写的一个C++数据库LEDA。

第二章讨论的是最短路径问题（shortest path problem），常见的问题如single source problem, all pairs problem等。算法解决的网络类型包括不带环的图和边的值可为负值的网络。主要的算法包括Bellman/Ford算法，Dijkstra算法。

第三章分析的是max flow problem。首先引入了Restnetzwerk（residual network）和Schnitt(cut)，erhoehender Pfad(augmenting path)等基本概念，接着介绍了Labeling Algorithnus(label algorithm)，实现了MaxFlowLabeling算法并作了Laufzeita分析。另外还介绍了capacity scaling algorithm，shortest augmenting path algorithm以及对shortest augmenting path algorithm的改进算法，shortest augmenting path algorithm with Gap-Heuristik，preflow push algorithm，FIFO preflow push algorithm.

第四章介绍的是针对最小费用问题min cost problem的算法。首先介绍的是feasible flow，判断一个flow是否是最优的flow的3个不同的方法，cycle canceling optimality，reduced cost optimality和complementary slackness optimality（考试时还靠这个东东来着）。算法包括successive shortest path algorithm和capacity scaling 和cost scaling algorithm。这些算法的Idee并不难理解，可是分析和实现起来却是很困难。