1.判断出一个有向图是否有环的是：a.最短路径有向图最短路径Dijkstra不一定能够判断有环，除非Visted数字记录0（false），1（已经访问），    　　2（再一次重复访问）；

　　　　　　　　　　　　　　　　b.括扑排序：通过入度0之后记录顶点数与原Vetex相比较

　　　　　　　　　　　　　　　　C.DFS(深度优先遍历)，图处理成树结构时候，找到一个节点保存节点，DFS找到重复节点表面图中有环

D.但是BFS（广度优先遍历），层次遍历方式，A->C，B->C，图中两条边指向一个公共点C，nodeC访问重复，但是不能判断其中出现环情况

2.有权无向图中的最小代价生成树并不是唯一的，有许多种等价的树，例如：图的形状权1的等边三角形，最小生成树有多种

3.缩短关键路径某个关键活动并不能缩短整个工程：关键路径A,B，关键A活动减少但是并不影响关键B，减小A
有可能让整个工程量减少

4.在用Floyd算法求解各顶点间的最短路径时,每个表示两点间路径的path(k-1)[I,J]一定是path(k)[I,J]的子集(k=1,2,3,…,n)()
不一定
path(k-1)[I,J]:I到J过程中[1,...,k-1]集合中中间节点最短路径

5.N个顶点图连通，有向图N条边，无向图N-1条边
无向图连通 边>N-1
有向图连通 边E>N

6.计算图的最大流量：按层计算，瞻前顾后
1).计算每一层流向终点的最大输出能力
2）.计算总体流量，同时各个层中流量最小一层

第一层S最大输出能力：11+22+10=43
第二层1,2,3：朝终点输出能力（必须入度，出度考虑）：10+17+14=41 --10表示节点4最大输出能力，143最大的输入能力
第三层4,5,6：朝终点输出能力：10+16+16=42
综合考虑：41

7.对于无向图N个顶点，最多有（N-1）*N/2;

连通：顶点Vi到Vj有路径就是连通，连通图：任意两点是连通的，
要保证连通具有10个顶点的无向图，至少需要（37）条边；保证前9个顶点任意两辆连接 9*8/2=36，最后一点有一条路径就是10个顶点连通36+1=37
10个顶点形成连通图则有10个顶点两两连接--叫强连通图：10*9/2=45

将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。

8.AOV网络：顶点表示活动网，关键路径：网中最长路径；

一个事件最迟开始时间=min{以该事件为尾的弧活动最迟开始时间，，最迟结束时间与该活动的持续时间的差}

最迟完成时间=后一个事件最迟开始成时间-持续时间
自由时间=最迟开始成时间-最早完成时间

图论知识错题本