离散数学教学图论

离散数学教学图论第一页，共六十页，2022年，8月28日本章重难点:重点了解图的各种概念，理解并掌握握手定理的应用以及各种矩阵的表示。难点是图的最短路径和关键路径的求法。第二页，共六十页，2022年，8月28日第11章图论第一节

图的基本概念第二节图的矩阵表示第三节生成树、最短路径和关键路径第四节特殊图（欧拉图和哈密顿图等）第五节树、二叉树和哈夫曼树第三页，共六十页，2022年，8月28日一、图的基本概念图的定义：图（graph）G由三个部分所组成：（1）非空集合V(G)称为图G的结点集，其成员称为节点或顶点（nodesorvertices）（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。第四页，共六十页，2022年，8月28日

一、图的基本概念连通图、强连通图、弱连通图

若无向图中的任意两个顶点都相互可达，则称无向图G是连通的（connected）；若有向图G的任何两个顶点都是相互可达的，则称有向图G是强连通的；如果G的任何两个顶点都是相互可达的，称有向图G是单向连通的；如果G的任何两个顶点中，至少从一个顶点到另一个顶点是可达的，称有向图G是弱连通的。第五页，共六十页，2022年，8月28日

一、图的基本概念邻接和关联无向图和有向图零图和平凡图简单图完全图（无向完全图和有向完全图）有环图第六页，共六十页，2022年，8月28日一、图的基本概念有限图和无限图设图G为<V，E，Ψ>（l）当V和E为有限集时，称G为有限图，否则称G为无限图。（2）当ΨG为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称满足Ψ(e1)=Ψ(e2)的不同边e1，e2，为重边,或平行边。正则图各顶点的度均相同的图称为正则图（regulargraph）。各顶点度均为k的正则图称为k-正则图。同构图第七页，共六十页，2022年，8月28日一、图的基本概念子图、真子图、生成子图设图G1＝<V1，E1，Ψ1>，G2＝<V2，E2，Ψ2>，称G1为G2的子图（subgraph）；如果V1V2，E1E2，Ψ1Ψ2，称G1为G2的真子图；如果G1是G2的子图，且G1G2，称G1为G2的生成子图（spanningsubgraph）；如果G1是G2的子图，且V1=V2。第八页，共六十页，2022年，8月28日握手定理的证明每个图中，节点度数的总和等于边的2倍。证明：因为每条边必关联两个节点，而一条边给予关联的每个节点的度数为1，因此在一个图中，节点度数的总和等于边数的2倍。第九页，共六十页，2022年，8月28日握手定理的运用定理1：在任何图中，度数为奇数的节点个数必定是偶数个。

证明：

（自己思考！）定理2：在任何有向图中，所有节点入度之和等于所有节点的出度之和。

证明：因为每一条有向边必对应一个入度及一个出度，所以有向图中各节点入度之和等于边数，各节点的出度之和也等于边数。第十页，共六十页，2022年，8月28日例：设图G为下列情况：(1)16条边，每个顶点都是2度；(2)21条边，3个4度顶点，其余均为３度顶点；(3)24条边，各节点的度数均相同；试求每个图有几个节点？握手定理的应用解答：利用握手定理，设图Ｇ有x个节点，则２x=16*2

x=1621*2=12+3*xx=10故图中有１３个节点．(3)

x*m=24*2第十一页，共六十页，2022年，8月28日

二、图的矩阵表示关联矩阵2.邻接矩阵3.可达矩阵4.布尔矩阵5.代价矩阵第十二页，共六十页，2022年，8月28日

二、图的矩阵表示关联矩阵无向图的关联矩阵-----以节点数为行,边数为列.若有环,则关联数为2,无关联则为0.每行之和为该顶点的度,列之和一定为2.有向图的关联矩阵-----以节点数为行,边数为列.节点与边无关系,为0,有关系,则起点为1,终点为-1;列之和一定为0,每行绝对值之和等于该节点的度数;其中1的个数为该节点的出度,-1的个数为对应节点的入度;所有元素的和为0,1的个数等于-1的个数,都等于边数m.第十三页，共六十页，2022年，8月28日

二、图的矩阵表示2.邻接矩阵无向图的邻接矩阵-----行和列均为节点的数目;是个对称距阵,行之和等于列之和,均等于该顶点的度;主对角线都为0,除非有环才为1;边的数目m为1的数目总和的一半.有向图的邻接矩阵-----行和列均为节点的数目;不是对称距阵,行之和等于该顶点的出度,列之和等于该顶点的入度;主对角线都为0,除非有环才为1;边的数目m为非0的数目的总和.第十四页，共六十页，2022年，8月28日

二、图的矩阵表示可达矩阵---行和列均为节点的数目;节点和节点之间若至少存在一条路则为1,不存在路则为0.4.布尔矩阵---由可达距阵转变,把非0的数值均改为1即可.代价矩阵---若邻接距阵元素为1的以权值表示,距阵元素为0的则以∞表示.第十五页，共六十页，2022年，8月28日三、生成树、最短路径和关键路径生成树定义1、深度优先遍历2、广度优先遍历最小生成树构造最小生成树的三种方法：1、Kruskal算法2、管梅谷算法3、Prim算法第十六页，共六十页，2022年，8月28日第四节欧拉图和哈密顿图欧拉图的由来：哥尼斯堡七桥问题—哥尼斯堡城市有一条横贯全城的普雷格尔河，河中有两个小岛，城的各部分用七座桥连接，每逢假日，城中居民进行环城逛游，这样就产生了一个问题，能不能设计一次遍游，使得从某地出发对每座跨河桥只走一次，而在遍历了七桥之后却又能回到原地。第十七页，共六十页，2022年，8月28日第四节欧拉图和哈密顿图通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路（欧拉路）。通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。只有具有欧拉回路的图才能称为欧拉图。具有欧拉通路而无欧拉回路的图称为半欧拉图。第十八页，共六十页，2022年，8月28日第四节欧拉图和哈密顿图欧拉在1736年的论文中提出了一条简单准则，确定了哥尼斯堡七桥问题是不能解的。定理1：无向图是欧拉图当且仅当G是连通图且没有奇度顶点。定理2：无向图是半欧拉图当且仅当G是连通的且恰有两个奇度顶点。第十九页，共六十页，2022年，8月28日第四节欧拉图和哈密顿图定理3：有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度等于出度。定理4：有向图D是半欧拉图当且仅当D是单向连通的且恰有两个奇度顶点，其中一个顶点的入度比出度大1，另一个顶点出度比入度大1，而其余顶点的入度等于出度。第二十页，共六十页，2022年，8月28日第四节欧拉图和哈密顿图欧拉图的应用：一笔画问题：一个图能一笔画出是指从图某一点出发，不间断地画完整个图，最后回到起点。第二十一页，共六十页，2022年，8月28日第四节欧拉图和哈密顿图哈密顿图的由来—周游世界问题：一个数学游戏，能不能在一个十二面体中找到一条回路，使它含有这个图的所有结点？把每个结点看成一个城市，连接两个结点的边看成是交通线，也即能否找到旅游线路，沿着交通线经过每个城市恰好一次再回到原来的出发地？第二十二页，共六十页，2022年，8月28日第四节欧拉图和哈密顿图经过图中所有顶点一次且仅一次的通路称为哈密顿通路（哈密顿路）。通过图中所有顶点一次且仅一次的回路称为哈密顿回路。只有具有哈密顿回路的图才能称为哈密顿图。具有哈密顿通路而无哈密顿回路的图称为半哈密顿图。第二十三页，共六十页，2022年，8月28日第四节欧拉图和哈密顿图定理1（必要条件）：设无向图G=<V,E>是哈密顿图，则对于任意V1V且V1≠空集，均有P（G-V1）≤∣V1∣定理2（充分条件）：设G是n阶无向简单图，若对于G中任意不相邻的顶点u，v，均有d（u）+d（v）≥n-1，则G中存在哈密顿通路。推论：设G为n（n≥3）阶无向简单图，若对于G中任意两个不相邻的顶点u，v均有d（u）+d（v）≥n，则G中存在哈密顿回路。第二十四页，共六十页，2022年，8月28日第四节欧拉图和哈密顿图哈密顿图的应用在某次国际会议的预备会中，共有8人参加，他们来自不同的国家，已知他们中任何两个无共同语言的人，与其余有共同语言的人数之和大于或等于8，试证明能将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。第二十五页，共六十页，2022年，8月28日一、无向树1.

定义：①无回路的连通无向图称为无向树，简称树。②树中度数为1的顶点称为树叶，度数大于1

的顶点称为内部结点或分枝点。③若图G的每个连通分图都是树,G称为森林

。第五节树、二叉树和哈夫曼树

第二十六页，共六十页，2022年，8月28日

2、树的五个等价定义Th1.无向图T是树，当且仅当下列条件之一成立：

1.无回路且m=n-1的图

2.连通且m=n-1的图

3.无回路，但增加任一新边，得到且仅得到一个基本回路

4.连通但删去任一边，图便不连通。(n>=2)5.每一对顶点间有唯一的一条通路。(n>=2)

第二十七页，共六十页，2022年，8月28日证明：证明思路

(1)树=>1(2)1=>2(3)2=>3(4)3=>4(5)4=>5(6)5=>6第二十八页，共六十页，2022年，8月28日

(1)树=>1

即无回路的连通无向图=>无回路且m=n-1证明：对顶点数作归纳证明。

n=1时，m=0，∴m=n-1成立设n=k命题成立，当n=k+1时，因树连通而无回路，所以至少有一个度数为1的顶点v，在T中删去v，及其关联边，得k个顶点的树T`由归纳假设，它有k-1条边。∴原图T边数为k-1+1,顶点数为k+1∴m=n-1成立。∴树是无回路且m=n-1的图。

第二十九页，共六十页，2022年，8月28日(2)无回路且m=n-1的图=>连通且m=n-1的图反证法.证明：设T不连通，有k个连通分图T1...Tk(k≥2)，顶点数及边数分别为n1...nk,m1...mk,因每个连通分图是无回路连通图，故符合树的定义，所以ni=mi-1成立∴n=m-kk>1,这与m=n-1前提矛盾∴T连通且具有m=n-1的图

第三十页，共六十页，2022年，8月28日(3)2=>3即连通且m=n-1的图=>无回路，但增加任一新边，得到且仅得到一个基本回路。证明：(a)T无回路，因T是连通,并且m=n-1的图，故当n=1时，m=n-1=0,无回路设顶点数为n-1时无回路。当顶点数为n时，m=n-1，故至少有一个顶点v，使d(v)=1，删去v及其关连边得图T’

则由归纳假设T’无回路，再加回v及关联边得图T，则T也无回路。

第三十一页，共六十页，2022年，8月28日(b)在连通图T中,任意取两点vi，vj,因为T连通所以vi，vj存在一路经，若增加新边(vi,vj)，则得一回路，且该回路是唯一的。(否则，删去新边，路经中必有回路。)第三十二页，共六十页，2022年，8月28日(4)3=>4.即无回路，但增加任一新边，得到且仅得到一个基本回路=>连通，但删去任一边，图便不连通。(n>=2)

证明：若图不连通，则存在vi,vj,,，使vi,vj之间没有路，增加边<vi,vj>不产生回路，与前提矛盾。因T无回路，故删去任一边，图便不连通。第三十三页，共六十页，2022年，8月28日(5)4=>5.即连通，但删去任一边，图便不连通。(n>=2)=>每一对顶点间有唯一的一条通路。证明：因图连通，故任二顶点间有一条通路，若二顶点间路径不唯一，则T中有回路，删去回路上任一条边，图仍连通，与假设矛盾，所以，每一对顶点间必有唯一的一条通路(6)5=>树定义（无回路的连通无向图）因每一对顶点有唯一的一条通路，故图连通，若图有回路，则任二顶点有两条不同通路，与题设矛盾。第三十四页，共六十页，2022年，8月28日证：若T中只有一片树叶，则d（vi）≥2（n-1）+1=2n-1

若T中没有树叶，则d（vi）≥2n

均与d（vi）=2m=2（n-1）矛盾。3、Th2：结点数大于等于2的任意树，至少有两片树叶。第三十五页，共六十页，2022年，8月28日二、生成树1、生成树定义：

若无向图的一个生成子图T是树，则称T为G的生成树，T中的边称为树枝，E（G）-E（T）称为树T的补，其中的每一边称为树T的弦。注：(1)由定义知，只有连通图才有生成树。(2)连通图的生成树不唯一，至少有一棵，因通过不断地删去图G中的回路中的边，总能得到一棵生成树。第三十六页，共六十页，2022年，8月28日

•e1•e2•e6e7e3•e5

•e4

•e8基本回路：生成树{e1,e7,e5,e6}，{e1，e7，e5，e2，e4}{e7,e2,e3,e4}，{e1，e6，e5，e2，e4}{e5,e4,e8}，{e7，e6，e5，e2，e4}第三十七页，共六十页，2022年，8月28日(3)设连通图G有n个顶点，m条边，则G的任一生成树有n-1条边，m-(n-1)条弦，m-n+1称为连通图的秩。2.图G中任一条回路和任何一棵生成树的补至少有一条公共边。证明：若G中一条回路和一生成树的补无公共边，则表示该回路在该生成树中。这与生成树定义矛盾。3.图G中任何一个边割集和任何一棵生成树至少有一条公共边。证明：若G中一个边割集和一生成树无公共边，则表示该边割集所分离的结点不在生成树中，这导致与生成树的定义矛盾。第三十八页，共六十页，2022年，8月28日三、最小生成树1、最小生成树定义：设图G=<V，E，W>是赋权连通简单图，其中每一边的权W(i，j)是非负实数。生成树T的权定义为W(T)=W（i，j），（i，j）T，使W(T）具有最小值的生成树称为G的最小生成树。2、最小生成树求法----kruskal算法。第三十九页，共六十页，2022年，8月28日

设图G有n个顶点，m条边，w(e1)≤…≤w(em)k←1，A←

若A{ek}导出子图不包含回路，则AA∪{ek}

kk+1N0

A=n-1Yes结束

第四十页，共六十页，2022年，8月28日证明：因T是有n-1条边，且无回路的图。由树的等价定义可知，它是树。又∵T包含了n个顶点，故包含了G的全部顶点。∴T是G的生成树。算法的正确性证明①证明边集A最后所得子图T是G的生成树。第四十一页，共六十页，2022年，8月28日②、T是最小生成树注：当G中的权相等时，仍可用本算法，只是所得之最小生成树不唯一。第四十二页，共六十页，2022年，8月28日③证明T是最小生成树（证明方法：T逐步转化T’

证明：设T是最小生成树，T’是由krusal算法生成的树，若T与T’不同，但有公共边e1...ei(i>=0),则ei+1T’ei+1T,则在T{ei+1}中有一回路r,而T’是树，因任一回路与生成树的补必有一公共边，所以在r中必存在一条边fT’

对于树T(边集至少为e1...ei,f)，若用ei+1代换f，得一棵新树T1(边集至少为e1...eiei+1)

则T1的权W(T1)=W(T1)+W(ei+1)-W(f)第四十三页，共六十页，2022年，8月28日因为T为最小生成树∴W(T)≤W(T1)∴W(ei+1)≥W(f)又根据T’生成法自e1...ei之后将取f而不是ei+1而现在T’取ei+1∴W(ei+1)≤W(f)∴W(ei+1)=W(f)∴T1也是G的最小生成树。而T1与T’的公共边比T与T’的公共边多1，用T1置换T，重复上面论证直至T与T’有n-1条公共边，从而证得T’也是G的最小生成树。

第四十四页，共六十页，2022年，8月28日一、有向树定义:1.若一个有向图T的底图是无向树，且恰有一个结点的入度为0，其余所有结点入度为1，称T为有向树。入度为0的结点称为根，出度不为0的结点称为分枝点或内部结点，出度为0的结点称为数叶或外部结点。注意：有向树通常采用根在顶点上，所有边方向向下的图表示.(箭头也可省略)

有向树及应用第四十五页，共六十页，2022年，8月28日2.基本概念:设a和b是树T的结点，若从a到b有一条边称a是b的父亲，b是a的儿子，同一个分枝点的儿子，称为“兄弟”。若从a到c有一有向路径，称a是c的祖先，c是a的子孙.由结点a和它所有的后代导的子图，称为T的子树.从树根r到一结点a的路径所含的边数称为a的路径长度。树T中最长的路径称为树T的高度。例题:abc第四十六页，共六十页，2022年，8月28日由有向树的结构可知，它还可以递归定义如下:3.有向树有一个根，其余的结点划分为m≥0个不相交的集合T1...Tm，且每个集合是子有向树。第四十七页，共六十页，2022年，8月28日4.有向树的括号表示①若T中只有一个结点，则此结点就是它的括号表示。②若T由根v和子树T1T2...Tn组成，则T的括号表示为v(T1T2...Tn）.

5.m元完全树，正则树的定义定义:在树T中若每一结点的儿子个数小于或等于m,称T为m元树;在树T中若每一结点的儿子个数等于m或者等于0，称T为完全m元树。若完全m元树所有树叶层次相同，称为正则m元树。第四十八页，共六十页，2022年，8月28日5.有向森林定义

一个有向图G，若它的每个连通分量是有向树，称G为(有向)森林，在森林中，若所有树是有序树，且给每棵树指定次序，称此森林为有序森林.bcbcabc完全3元树完全2元树正则2元树第四十九页，共六十页，2022年，8月28日

6、有序树，有序森林与二元树相互转换①有序树转换为二元树，转换过程为：

a)在各兄弟结点之间加一连线。

b)对任何结点，除最左的儿子之外，擦掉该结点与其余儿子的联线。

c)对新图向下旋转45度。bcbc------->第五十页，共六十页，2022年，8月28日

2.有序森林转换为二元树转换过程

a)设置一个总根，联结各树的根，得T`b)把T`转换为二元树

c)删除总根第五十一页，共六十页，2022年，8月28日

二.完全m元树性质

1.设完全m元树，叶数为t，分枝数为i，则t=(m-1)i+1

解:i=[(t-1)/(m-1)]=[(10-1)/(3-1)]=5答:至少执行5次加法指令.例：若t=i(m-1)+1计算机有一计算三数之和的加法器,现求十个数之和,问至少执行多少次加法指令?证明:若把完全m元树视为m个选手参加淘汰赛,则t表示选手总数,i表示比赛场数,每场比赛淘汰m-1人,共淘汰i(m-1)人,剩下一个冠军,所以

t=(m-1)i+1第五十二页，共六十页，2022年，8月28日2、内部通数长度I定义：各分枝点路径长度之和。内部通数长度E定义：各叶子路径长度之和.

性质：完全二叉树T有E=I+2n

其中:n为分枝点数第五十三页，共六十页，2022年，8月28日证：对n用数学归纳法:

当n=1,则叶数为2，I=0，E=2，E=I+2n成立;

当n=2,则叶数为3，I=1，E=5，E=I+2n成立;

设n=k-1时，结论成立;则n=k时，若删去长度为e+l其关系为兄弟的叶子，得T`，T`与原树比较，减少一个长度为e的分枝点、二个长度为e+1的叶子，增加一长度为e的叶子，E`=I`+2（k-1）而I`=I-e.所以E`=E-2（e+1)+e,即E-2(e+1)+e=I-e+2(k-1)

所以E=I+2k.第五十四页，共六十页，2022年，8月28日

三、前缀码和最优树1、问题的引出：