通过对信息系统项目管理师考试历年真题进行分析，管理运筹学这部分内容重点要求考生掌握线性规划、动态规划、图论、决策分析等。这部分内容考题难度很大，考生在备考过程中要重点掌握。以下是图论知识点精讲内容，供您参考学习。

       图论-图与最小生成树

       图由点和边构成的，可以反映一些对象之间的关系。图论中的点通常记为Vi，点之间的连线称之为边，通常记为ei。带箭头的连线，称之为弧，图论中的弧记为ai。

       如果“A认识B“，我们用一条连接A、B的箭头指向B的弧来表示。

       由点和边构成的图叫无向图（简称图），无向图记作为G=（V，E），其中V是图G的点的集合，E是图G的边集合。

       由点和弧构成的图叫有向图，有向图记为D=（V，A），其中V为图D的点集合，A为图D的弧的集合。

       最小生成树问题

       一个无圈的连通图即为树。

       最小生成树就是在一个赋权的连通的无向图G找出一个生成树，并使得这个生成树的所有边的权数之和最小。

       求解最小生成树的破圈算法如下：

       （一）在给定的赋权的边通图上任找一个圈；

       （二）在所找的圈中去掉一条权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）；

       （三）如果所余下的图中不含圈，则计算结束，所余下的图即为最小生成树。否则返回步聚（一）。

       【例】用破圈法求下图（a）中的最小生成树。

图（a）

       解：（一）去掉圈（V1，V6，V7，V1）中权值（权值为10的边）最大边[V1，V6]后，如图（b）所示：

图（b）

       （二）去掉圈（V5，V4，V3，V5）中权值为8的边[V5，V4]后，如图（c）所示：

图（c）

       （三）同理依次去掉权值为5，4，4的边后，最终得到的最小生成树如图（d）所示：

图（d）

       在图（d）中已找不到任何一个图了，可知其即为图（a）的最小生成树，这个最小生成树的所有边的总权数为3+3+3+1+2+7=19。

       返回目录：信息系统项目管理师备考知识点集锦之管理运筹学

       相关推荐：

       项管备考知识点集锦之管理运筹学考情分析

       信息系统项目管理师考试培训视频教程

       信息系统项目管理师考试辅导教材推荐