资源描述：
《离散数学PPT教学图论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、欢迎进入第11章图论本章重难点:重点了解图的各种概念，理解并掌握握手定理的应用以及各种矩阵的表示。难点是图的最短路径和关键路径的求法。第11章图论第一节图的基本概念第二节图的矩阵表示第三节生成树、最短路径和关键路径第四节特殊图（欧拉图和哈密顿图等）第五节树、二叉树和哈夫曼树一、图的基本概念图的定义：图（graph）G由三个部分所组成：（1）非空集合V(G)称为图G的结点集，其成员称为节点或顶点（nodesorvertices）（2）集合E(G)，称为图G的边集，其成员称为边(edges)。（3）函数ΨG：E(G)→(V(G)，V(G))，称为边与
2、顶点的关联映射。度的相关定义：在任何图中，结点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是单向连通的
3、；如果G的任何两个顶点中，至少从一个顶点到另一个顶点是可达的，称有向图G是弱连通的。一、图的基本概念邻接和关联无向图和有向图零图和平凡图简单图完全图（无向完全图和有向完全图）有环图一、图的基本概念有限图和无限图设图G为（l）当V和E为有限集时，称G为有限图，否则称G为无限图。（2）当ΨG为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称满足Ψ(e1)=Ψ(e2)的不同边e1，e2，为重边,或平行边。正则图各顶点的度均相同的图称为正则图（regulargraph）。各顶点度均为k的正则图称为k-正则图。同构图一、图的基本概念子图
4、、真子图、生成子图设图G1＝，G2＝，称G1为G2的子图（subgraph）；如果V1V2，E1E2，Ψ1Ψ2，称G1为G2的真子图；如果G1是G2的子图，且G1G2，称G1为G2的生成子图（spanningsubgraph）；如果G1是G2的子图，且V1=V2。握手定理的证明每个图中，节点度数的总和等于边的2倍。证明：因为每条边必关联两个节点，而一条边给予关联的每个节点的度数为1，因此在一个图中，节点度数的总和等于边数的2倍。握手定理的运用定理1：在任何图中，度数为奇数的节点个数必定是偶数个。证明
5、：（自己思考！）定理2：在任何有向图中，所有节点入度之和等于所有节点的出度之和。证明：因为每一条有向边必对应一个入度及一个出度，所以有向图中各节点入度之和等于边数，各节点的出度之和也等于边数。例：设图G为下列情况：(1)16条边，每个顶点都是2度；(2)21条边，3个4度顶点，其余均为３度顶点；(3)24条边，各节点的度数均相同；试求每个图有几个节点？握手定理的应用解答：利用握手定理，设图Ｇ有x个节点，则２x=16*2x=1621*2=12+3*xx=10故图中有１３个节点．(3)x*m=24*2二、图的矩阵表示关联矩阵2.邻接矩阵3.可达矩阵4
6、.布尔矩阵5.代价矩阵二、图的矩阵表示关联矩阵无向图的关联矩阵-----以节点数为行,边数为列.若有环,则关联数为2,无关联则为0.每行之和为该顶点的度,列之和一定为2.有向图的关联矩阵-----以节点数为行,边数为列.节点与边无关系,为0,有关系,则起点为1,终点为-1;列之和一定为0,每行绝对值之和等于该节点的度数;其中1的个数为该节点的出度,-1的个数为对应节点的入度;所有元素的和为0,1的个数等于-1的个数,都等于边数m.二、图的矩阵表示2.邻接矩阵无向图的邻接矩阵-----行和列均为节点的数目;是个对称距阵,行之和等于列之和,均等于该顶
7、点的度;主对角线都为0,除非有环才为1;边的数目m为1的数目总和的一半.有向图的邻接矩阵-----行和列均为节点的数目;不是对称距阵,行之和等于该顶点的出度,列之和等于该顶点的入度;主对角线都为0,除非有环才为1;边的数目m为非0的数目的总和.二、图的矩阵表示可达矩阵---行和列均为节点的数目;节点和节点之间若至少存在一条路则为1,不存在路则为0.4.布尔矩阵---由可达距阵转变,把非0的数值均改为1即可.代价矩阵---若邻接距阵元素为1的以权值表示,距阵元素为0的则以∞表示.三、生成树、最短路径和关键路径生成树定义1、深度优先遍历2、广度优先遍
8、历最小生成树构造最小生成树的三种方法：1、Kruskal算法2、管梅谷算法3、Prim算法第四节欧拉图和哈密顿图欧拉图的由来：哥尼斯堡七
