离散数学教学图论.pptVIP

本章重难点: 重点了解图的各种概念，理解并掌握握手定理的应用以及各种矩阵的表示。 难点是图的最短路径和关键路径的求法。 一 、图的基本概念 图的定义： 图（graph）G由三个部分所组成： （1）非空集合V(G)称为图G的结点集，其成员称为节点或顶点（nodes or vertices） （2）集合 E(G)，称为图G的边集，其成员称为边(edges)。 （3）函数ΨG：E(G)→(V(G)，V(G))，称为边与顶点的关联映射。 度的相关定义： 在任何图中，结点v的度（degree）d(v)是v所关联边的数目。 而在有向图中，结点v的出度（out-degree）d+(v)是v作为有向边起点的数目，v的入度（in-degree）d-(v)是v作为有向边终点的数目，这时结点v的度是它的出度与入度的和；结点v的环使其度增加2。 一 、图的基本概念 连通图、强连通图、弱连通图 若无向图中的任意两个顶点都相互可达，则称无向图G是连通的（connected）； 若有向图G的任何两个顶点都是相互可达的，则称有向图G是强连通的； 如果G的任何两个顶点都是相互可达的，称有向图G是单向连通的； 如果G的任何两个顶点中，至少从一个顶点到另一个顶点是可达的，称有向图G是弱连通的。 一 、图的基本概念 邻接和关联 无向图和有向图 零图和平凡图 简单图 完全图（无向完全图和有向完全图） 有环图 一 、图的基本概念 有限图和无限图 设图G为 V，E，Ψ （l）当V和E为有限集时，称G为有限图，否则称G为无限图。 （2）当ΨG为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称满足Ψ(e1) = Ψ(e2)的不同边e1，e2，为重边,或平行边。 正则图 各顶点的度均相同的图称为正则图（regular graph）。 各顶点度均为k的正则图称为k-正则图。 同构图 一 、图的基本概念 子图、真子图、生成子图 握手定理的证明 每个图中，节点度数的总和等于边的2倍。 证明： 因为每条边必关联两个节点，而一 条边给予关联的每个节点的度数为1，因此在一个图中，节点度数的总和等于边数的2倍。 握手定理的运用 定理1：在任何图中，度数为奇数的节点个数必定是偶数个。 证明： （自己思考！） 定理2：在任何有向图中，所有节点入度之和等于所有节点的出度之和。 证明： 因为每一条有向边必对应一个入度及一个出度，所以有向图中各节点入度之和等于边数，各节点的出度之和也等于边数。 例：设图G为下列情况： (1) 16条边，每个顶点都是2度； (2) 21条边，3个4度顶点，其余均为３度顶点； (3) 24条边，各节点的度数均相同； 试求每个图有几个节点？ 二、图的矩阵表示 关联矩阵 2. 邻接矩阵 3. 可达矩阵 4. 布尔矩阵 5. 代价矩阵 二、图的矩阵表示 关联矩阵 无向图的关联矩阵 ----- 以节点数为行,边数为列.若有环,则关联数为2,无关联则为0.每行之和为该顶点的度,列之和一定为2. 有向图的关联矩阵 ----- 以节点数为行,边数为列.节点与边无关系,为0,有关系,则起点为1,终点为-1;列之和一定为0,每行绝对值之和等于该节点的度数;其中1的个数为该节点的出度,-1的个数为对应节点的入度;所有元素的和为0,1的个数等于-1的个数,都等于边数m. 二、图的矩阵表示 2. 邻接矩阵 无向图的邻接矩阵 ----- 行和列均为节点的数目;是个对称距阵,行之和等于列之和,均等于该顶点的度;主对角线都为0,除非有环才为1;边的数目m为1的数目总和的一半. 有向图的邻接矩阵 ----- 行和列均为节点的数目;不是对称距阵,行之和等于该顶点的出度,列之和等于该顶点的入度;主对角线都为0,除非有环才为1;边的数目m为非0的数目的总和. 二、图的矩阵表示 可达矩阵 --- 行和列均为节点的数目;节点和节点之间若至少存在一条路则为1,不存在路则为0. 4.布尔矩阵 --- 由可达距阵转变,把非0的数值均改为1即可. 代价矩阵 --- 若邻接距阵元素为1的以权值表示,距阵元素为0的则以∞表示. 三、生成树、最短路径和关键路径 生成树定义 1、深度优先遍历 2、广度优先遍历 最小生成树 构造最小生成树的三种方法： 1、Kruskal算法 2、管梅谷算法 3、Prim算法