山东大学算法设计和分析期末
虽然是早上考的试，但是有些忘却了，尽力写吧，感觉和之前在上看到的历年题有些变化，题号不是正确的，是属于想到哪写到哪（大体前后顺序是对的） 证明题的题干是英文，是5、6两道题 可能是9道大题（写全了），也可能是10道大题（我忘了一道） 总体题量还算可以，有大佬最后20分钟前交卷了。 希望对学弟学妹们有帮助！
1.
给一个图 （1）bfs树 （2）dfs发现时间和完成时间，并标注每条边的分类
2.
给出一个有向图（3个节点，4条边） 用floyd或者扩展矩阵算法（书上的两个算法），写出所有的d矩阵和pi矩阵
4.
给出一个图，求该图的所有残留网络的图还有每次增加的p的大小，以及求出最大流和最小割
5.
归纳法证明对于一个图来说，松弛了k次后，有d[k] = s到k的最短路
6.
连通图，每条边权重不同，有一个割的轻量边为e，求证e一定在MST中
7.
给定s,v,t求从s到t不经过v的路径有几条，给出一个动态规划算法，说明各变量定义和递推关系式（类似作业题）
8.
两个条件 （a）u,v是一条边 （b）u到v有路径 问哪个条件使得在u完成之前，一定能发现v 给出正确条件的简短解释，给出错误条件的反例
9.
有同学给出一个算法，将V分成两个集合V1和V2，V1中有u，V2中有v，（u,v）是连接V1和V2的最短边，分别分治的求出V1和V2中的MST，则图的MST就是V1和V2和（u,v），问该算法正确吗，若正确，则证明，不正确则给出反例（类似作业题）
10.
给一个有向图，有源点s，c(v) = s到v路径上最小容量的最大值，让你设计一个算法类似dijkstra，完成本例，并且写出算法，并且分析为什么是正确的
