西交《运筹学》重要知识点解析和例题分析第六部分.doc

《运筹学》重要知识点解析和例题分析第六部分 一．图的基本概念 定义 一个图G是指一个二元组(V(G),E(G))，即图是由点及点之间的联线所组成。其中: 1）图中的点称为图的顶点(vertex)，记为：v 2）图中的连线称为图的边(edge)，记为：，是边 e 的端点。 3）图中带箭头的连线称为图的弧(arc)，记为：，是弧 a 的端点。 —— 要研究某些对象间的二元关系时，就可以借助于图进行研究 分类 无向图：点集V和边集E构成的图称为无向图(undirected graph)，记为： G(V，E)—— 若这种二元关系是对称的，则可以用无向图进行研究 有向图：点集V和弧集A构成的图称为有向图(directed graph) ，记为：D(V，A)—— 若这种二元关系是非对称的，则可以用有向图进行研究 有限图: 若一个图的顶点集和边集都是有限集，则称为有限图.只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图. 图的特点： 1 图反映对象之间关系的一种工具，与几何图形不同。 2 图中任何两条边只可能在顶点交叉，在别的地方是立体交叉，不是图的顶点。 3 图的连线不用按比例画，线段不代表真正的长度，点和线的位置有任意性。 4 图的表示不唯一。如：以下两个图都可以描述“七桥问题”。 点(vertex)的概念 1 端点：若e =[u，v] (E，则称u，v 是 e 的端点。 2 点的次：以点 v 为端点的边的个数称为点 v 的次，记为：。 在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为或 dG(v). 在有向图中，从顶点v引出的边的数目称为顶点v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d -(v). 称= d+(v)+d -(v)为顶点v的度或次数． 3 奇点：次为奇数的点。 4 偶点：次为偶数的点。 5 孤立点：次为零的点。 6 悬挂点：次为1的点。 定理 推论 任何图中奇点的个数为偶数． 链(chain)的概念 1 链：一个点、边的交替的连续序列称为链，记为μ。 2 圈(cycle)：若链μ的，即起点＝终点，则称为圈。 3 初等链（圈）：若链（圈）中各点均不同，则称为初等链（圈） 。 4 简单链（圈） ：若链（圈）中各边均不同，则称为间单链（圈） 。 圈一定是链，链不一定是圈 路PATH 路(path)：顶点和边均互不相同的一条途径。 若在有向图中的一个链μ中每条弧的方向一致，则称μ为路。（无向图中的路与链概念一致。） 回路(circuit)：若路的第一个点与最后一个点相同，则称为回路。 连通性: 点i和j点是连通的：G中存在一条（i，j）路 G是连通的：G中任意两点都是连通的 例 在右边的无向图中： 途径或链： 迹或简单链： 路或路径： 圈或回路： 在右边的有向图中： 链 不是路 链 且是路 链 是回路 连通图 简单图(simple graph)：一个无环、无多重边的图称为间单图。 多重图(multiple graph)：一个无环，但有多重边的图称为多重图。 连通图(connected graph)：若图中任何两点间至少有一条链，则称为连通图 。否则，为不连通图。 连通分图：非连通图的每个连通部分称为该图的连通分图。 基础图：去掉有向图中所有弧上的箭头，得到的图称为原有向图的基础图。 图G＝(V, E)是多重图 图G＝(V, E)为不连通图 但G’＝(V’, E’)是G的连通分图 其中：V’＝{v1, v2, v3, v4} E’＝{e1, e2, e3, e4, e5, e6, e7} 二．树（tree） 1、树的定义 树：一个无圈的连通图称为树。 2、树的性质 （1） 设图G＝(V, E)是一个树，点数P(G) ≥ 2，则 G 中至少有两个悬挂点。 （2） 图G＝(V，E)是一个树==G不含圈，且恰有p-1条边（p是点数）。 （3） 图G＝(V，E)一个树== G 是连通图，且q(G)＝p(G)－1 （q是边数）。 （4） 图G＝(V，E)是树 == 任意两个顶点之间恰有一条链。 图的支撑树(spanning tree) 1 支撑子图：设图G＝(V，E)，图G’＝(V’，E’)的V’＝V， E’ ( E，则称G’是G的一个支撑子图。 —— 图G’＝(V’，E’)的点集与图G＝(V，E)的点集相同，V’＝V，但图G’＝(V’，E’)的边集仅是图G＝(V，E)的子集E’ ( E。 2 支 撑 树：设图T＝(V，E’)是图G＝(V，E)的支撑子图，如果T＝(V，E’)是一个树，则称 T 是 G 的一个支撑树。 特点——边少、点不少。 最小树(mini