离散数学课件11图论总复习

图论小结本章内容特点:概念很多,而且有些概念很相近,容易弄错,要特别仔细.另外本章内容容易理解,也不那么抽象.下面再将内容归纳一下:一.图的概念图的定义,有向边,无向边,平行边,环邻接点,邻接边,孤立结点有向图,无向图,简单图,混合图,零图,平凡图,多重图,完全图,子图,生成子图,补图,结点的度,结点的出度,结点的入度,图的最大度Δ(G),最小度δ(G),

图所有结点度数总和与边的关系,出度和与入度和关系图的同构二.路与回路路,回路,迹,闭迹,通路,圈

无向图的连通性:连通图,连通分支,连通分支数W(G),

点割集,割点,点连通度k(G),

边割集,割边(桥),边连通度λ(G)

结点间的距离,图的直径

有向图的连通性:可达性,强连通,单侧连通,弱连通三.图的矩阵

邻接矩阵A:结点与结点之间的邻接关系矩阵.根据邻接矩阵判断:各结点的度,有向图结点出,入度.由Ak可以求一个结点到另一个结点长度为k的路条数.

可达矩阵P:结点u到结点v的可达性的矩阵.用P可以判定:各结点的度.有向图的强分图.

关联矩阵M:是结点与边的关联关系矩阵.用M判定:各结点的度四.树与生成树树的定义:6个定义*,其中最主要的是连通无回路,e=v-1

分支结点,叶结点会求最小生成树五.根树

m叉树,完全m叉树,(m-1)i=t-1m叉树变成二叉树

会画最优树,会设计前缀码六.欧拉图与汉密尔顿图(会判定)欧拉路,欧拉回路,欧拉图.判定:有欧拉路的充要条件:无或有两个奇数度的结点.有欧拉回路的充要条件:所有结点度数均为偶数.汉密尔顿路,汉密尔顿回路,汉密尔顿图汉密尔顿图的判定:

必要条件:V的任何非空子集S,有W(G-S)≤|S|

充分条件:每对结点的度数和≥|V|=n七.二部图作为一般了解,掌握匹配问题和K3.3八.平面图平面图的定义,平面的边界,欧拉公式:v-e+r=2

判定:必要条件:e≤3v-6

充要条件:G不含与K5或K3,3在2度结点内同构子图.九.对偶图与着色会画对偶图,会对图正常着色.习题课

证明任何有向简单完全图中,所有结点的入度平方之和等于所有结点出度平方之和.(设图有n个结点)证明:因有向简单完全图中每个结点v:

degi(v)=dego(v)=n-1故,所有结点的入度平方之和等于所有结点出度平方之和.或者∑(degi(v))2-∑(dego(v))2=∑[(degi(v))2-(dego(v))2]=∑{[(degi(v))+(dego(v))][(degi(v))-(dego(v))]}=n2(n-1)∑{[(degi(v))-(dego(v))]}=2n(n-1){∑degi(v)-∑dego(v)}=2n(n-1)0=0所以∑(degi(v))2=∑(dego(v))2

(2)画出右图的补图.(4)证明下面两个图是同构的.再验证边之间的对应关系.

a

fb

e

h

i

c

dg

j

abcejfhgdiV1V1fabcdefa

b

c

d

e

f

ghijg

h

i

j

(5)一个图与它的补图同构,称为自补图.c).一个图是自补图,其对应的完全图的边数是偶数.证明:此命题显然成立,因为一个图与其补图同构,则它们的边数相等,于是它们对应完全图的边数为它们边数的和所以该完全图的边数是偶数.a).给出5个结点的自补图.b)是否有3个结点或6个结点的自补图.解:不存在.因为K3与K6的边数分别是3和15.

证明如果图G是不连通的,则它的补图是连通的.证明:任取u,v∈V(G),如果u与v不邻接,则在中有边(u,v)所以在中u与v是连通的.如果在G中u与v邻接,则u与v在G的同一个连通分支,由于G是不连通的,所以G必有另一个连通分支G(V1),设w∈V1(G),于是在中必有边(u,w),(w,v),于是在中必有路uwv,所以是连通的.G－G－G－G－G－G－

分析右图,求a)从A到F的所有通路.通路:路中结点不同.

ABCFABEFADEFABECFABCEFADECFADEBCFb)从A到F的所有迹.迹:路中边不同.

ABCFABEFADEFABECFABCEFADECFADEBCFADEBCEFc)A和F之间的距离.距离:就是最短的路长.

A和F之间的距离为3.DAFEBC

求右图的图G的强分图,单侧分图和弱分图.解:找强分图:在回路中的结点构成一个强分图,其余结点自己构成各自的强分图.强分图有:{1,2,3},{4},{5},{6}各自导出的子图.单侧分图:{1,2,3,4,5,6}导出的子图.弱分图:G本身.

求右图的邻接矩阵,可达矩阵和距离矩阵.解:

514

623v2

v5

v4v3

v10000010110100000010000000A=P=A∨A(2)∨A(3)∨A(4)∨A(5)距离矩阵D:

将各个Ai中非0元素取最小的;主对角线为0;主对角线以外的0变成∞.0000010100000001000000000A2=0000010110100000010000000A=0000010000000000000000000A3=0000000000000000000000000A4=0000010110100001010000000P=0∞∞∞∞1011∞1∞0∞∞1∞10∞∞∞∞∞0D=

判定下面图是否能一笔画.因为这两个图中,都只有两个奇数度的结点,有欧拉路,所以可以一笔画.

构造一个欧拉图,使得结点数v和边数e满足:

a)v,e奇偶性一样.b)v,e奇偶性相反.

a

b

1234567891011121314151617181921222324252627282930

n取何值时,完全图Kn是个欧拉图.解:因为Kn有n个结点,每个结点的度数是n-1,要使n-1为偶数,必使n=3,5,7,…等奇数.

a)画一个有一条欧拉回路和一条汉密尔顿回路的图.b画一个有一条欧拉回路但没有一条汉密尔顿回路的图.c)画一个没有一条欧拉回路但有一条汉密尔顿回路的图.

证明在有6个结点12条边的连通平面简单图G中,每个面由3条边围成.证明:因为G中所有面的边界长总和为边数的2倍.即∑deg(r)=2×12=24,由欧拉公式得;r=2-v+e=2-6+12=8而G中无环和平行边,24/8=3所以每个面由3条边围成.

证明:若G是每一个面至少由k(k≥3)条边围成的连通平面图,则,,这里v,e分别是G的结点数和边数.证明:设G中有r个面,因为G中所有面的边界长总和为边数的2倍.所以2e≥kr,所以r≤,代入欧拉公式得:

v-e+≥2

如果可能,把下面画成平面图,否则说明它包含一个与K5或K3,3在2度结点内同构子图.

证明a)对于K5中任何边e,K5-e是平面图.b).对于K3,3中任何边e,K3,3-e是平面图.

画出下面各图的对偶图.

351624

351624

用韦尔奇.鲍威尔法,对下面各图着色.求图的着色数.(a)图课堂已作.(b)结点按照度数降序排序:B,F,A,C,E,G,D,H

可见此图是4色的.

C

B

A

G

D

E

FH

a)一个完全图K6

的边涂上红色或者蓝色,证明对于任何一种随意涂边的方法,总有一个完全图K3

的所有边被涂上红色,或者涂上蓝色.证明:因为K6中任何结点都有5条边与之关联,这5条边图上红色或者蓝色,那么必有要么3边是红色,要么3边是蓝色,如图所示.我们假设3条边涂上红色,而这3条边的另一端的3个结点之间3条边构成一个三角形,下面考察这3条边涂的颜色,如果至少有一条边是涂红色,则与上边两条红色边构成一个红色的三角形.如果没有一条涂红色,那么这个下面的三角形就是全是蓝色的边.对于开始时3边都涂蓝色,类似证明结论成立.

证明6个人的人群中,或者有3个人相互认识,或者有3个人彼此陌生.证明:以6个人为结点画一个K6图,如果两个相互认识就把相应边涂上红色,如果彼此陌生就涂上蓝色.由a)的结论得必有三个人它们构成的三角形的三条边要么都涂上红色,要么都涂上蓝色.

一棵树T有n2个结点度数为2,n3个结点度数为3,…nk个结点度数为k,问它有多少个度数为1的结点?解:设有n1个度数为1的结点,又令T有v个结点,e条边.于是

v=n1+n2+…+nkT的所有结点度数总和=n1+2n2+…+knk=2e

因e=v-1∴n1+2n2+…+knk=2(n1+n2+…+nk-1)∴n1=n3+2n4+…+(k-2)nk+2

一棵树T有两个结点度数为2,一个结点度数为3,三个结点度数为4,问它有多少个度数为1的结点?解:设有n1个度数为1的结点,又令T有v个结点,e条边.于是

v=n1+2+1+3=n1+6T的所有结点度数总和=n1+2×2+1×3+3×4=n1+19=2e

因e=v-1∴n1+19=2(n1+6-1)∴n1=9

给定图G如图所示,用Kruskal算法,求G的一棵最小生成树.

1112222233342

12345678910

从简单有向图的邻接矩阵如何判定它是否为根树?如果是根树,如何判定树根和树叶.解:先看个例子:根:入度为0----列为0的结点叶:出度为0----行为0的结点(2)求出右图的二叉树.v1

v6v4

v2

v3

v5011000000110000001000000000000A=0000001

9

5

2

4

7

1110

6

8

12

13

3

141

2

45

612

8

9

710

14

13

3

11

证明完全二叉树T中,边的总数等于2(nt-1),其中nt是叶结点数.证明:由完全m叉树公式(m-1)i=t-1这里t=nt

,∴(2-1)i=nt-1,∴i=nt-1,∴T中总的结点数v为:

v=i+nt=(nt-1)+nt=2nt-1T的边数e=v-1=2nt-1-1=2nt-2=2(nt-1)

给定一组权:1,4,9,16,25,36,49,64,81,100a)构造一棵最优完全二叉树.b)构造一棵最优完全三