08图论离散数学讲义海南大学共十一讲.docx

08图论离散数学讲义海南大学共十一讲.docx

《08图论离散数学讲义海南大学共十一讲.docx》由会员分享，可在线阅读，更多相关《08图论离散数学讲义海南大学共十一讲.docx（21页珍藏版）》请在冰点文库上搜索。

08图论离散数学讲义海南大学共十一讲

8.图论TopicsinGraphTheory

§8.1图Graphs

G=

V={v1,v2,······,vn}顶点vertex集。

E={e|e=（vi,vj）,vi,vj∈V,vi≠vj}无向边edge集。

γ（e）={vi,vj},e的端点endpoints集。

简写为G＝（V，E）。

TD（vi）顶点vi的度数degree：

连接到vi的边的条数。

连接一个顶点的圈loop算两度。

孤立点isolatedvertex：

度数为0的点。

两个顶点相邻adjacent：

有一边相连。

定理1.（握手定理）TD＝TD（vi）=2m.

推论.任意图的奇数度顶点必有偶数多个。

完全图completegraph：

任意两点都相邻简单图。

定理2.n个顶点的完全图有n（n-1）/2条边。

正则图regulargraph：

每个顶点都有相同的度数。

E={|vi,vj∈V}有向边集有向图

有向边，

vi起点弧尾，vj终点弧头

TD（vi）:

顶点的度degree:

以vi为端点的边的数目。

OD（vi）:

出度,以vi为起点的边的数目。

ID（vi）:

入度，以vi为终点的边的数目。

TD（vi）=OD（vi）+ID（vi）

OD=ID,TD=2|E|，E|=1/2*TD

TDODID为整个图的总度,出度,入度数。

路径path：

vi······vj，以vi为起点vj为终点的顶点序列，相邻顶点相邻。

路径的长length:

路径上边的数目，

简单路径simplepath:

点都不重复的路径，

回路circuit:

首尾相接的路径，

简单回路simplecircuit:

除起点和终点以外都不重复的路径，

vivj连通connected:

有路径vi······vj相连。

连通图:

任意两点都连通的图。

例

左图a,c,d,g是简单路径

右图a,d,b,c,e是简单路径。

f,e,a,d,b,a,f是简单回路。

f,e,d,c,e,f不是简单回路。

有向图

vivj强连通vivj连通vjvi也连通，

强连通图任意两点都强连通。

子图和商图SubgraphandQuotientGraph

G=（V,E）,G’=（V’,E’）

如果V’V,E’E,就称G’是G的子图subgraph。

G’的补图：

＝（V,E\E’）,G的边集中去掉E’的边。

Ge＝（V，E’）,E’=E\{e}.

连通分量connectedcomponents:

一个图的极大连通子图。

一个图可以划分成几个不相交的连通分量。

强连通分量strongconnectedcomponents:

一个有向图的极大强连通子图。

商图quotientgraph

R是V上等价关系，

V/R={[v]|v∈V}

E/R={（[v],[w]）|[v],[w]中有相邻的顶点}

GR＝G/R=（V/R,E/R）,称为G模R的商图。

把R相关的顶点粘合成一点，相关的边粘合成一边，就得到商图。

连通图的生成树spanningtree:

含有所有顶点的极小连通图.

n个顶点连通图至少有n-1条边。

m条边的连通图去掉m－n＋1条边可以得到生成树。

从连通图中如有回路，去掉回路中的一条边，继续直至没有回路，就得到生成树。

从m条边的连通图中得到生成树，要去掉m－n＋1条边

T是连通图G的生成树，G的每一条不属于T的边e，叫弦。

m条边的连通图共有m－n＋1条弦。

基本回路：

每条弦加到T中得到一个回路，叫基本回路。

m条边的连通图共有m－n＋1个基本回路。

割集：

G的边集，去掉后G不连通。

一条边组成的割集叫桥bridge。

树的每条边都是桥。

基本割集：

生成树T中每一条边，和G中对应于T的所有的弦，组成一个割集，叫基本割集。

最小生成树：

权重最小的生成树。

带权的边：

带边长的边。

带权的图：

每边都带权。

Prim算法：

设G=,

1.令U={v0},T={}.

2.对任意u∈U,v∈V-U,（u,v）∈E,

找到权最小的边（u1,v1）,

令U=U∪{v1},T=T∪{（u1,v1）}

3.重复2，直至U=V.

得到T就是最小生成树。

T中共有n-1条边

Kruskal克鲁斯卡尔算法

G=（V,E）连通图

令T=（V,{}）是G的所有顶点而无边的非连通图。

1.选择E中权值最小的边，

若该边连接T的两个连通分量，将它加入T,

这时T的连通分量减少1；

否则选下一条权值最小的边。

2.重复1n-1次直到T连通。

T就是最小生成树

§8.2欧拉路径和欧拉回路

哥尼斯堡七桥问题。

一笔画问题。

欧拉路径Eularpath：

通过图的所有边，每个边恰好一次的路径。

欧拉回路Eularcircuit：

构成回路的欧拉路径。

定理1.G有欧拉回路当且仅当G连通且没有奇数度顶点。

定理2.G有欧拉路径当且仅当G连通且至多有两个奇数度顶点。

§8.3Hamilton路径和Hamilton回路

周游世界问题：

每个城市访问一次只经过一次。

Hamilton公爵提出是否存在一条回路通过正二十边形每个顶点恰一次。

一个连通图G

Hamilton路径:

经过每个顶点恰一次的路径。

Hamilton回路：

经过每个顶点恰一次的回路。

Hamilton图：

有Hamilton回路的图。

完全图Kn，n>2，是Hamilton图。

归纳可证。

n个顶点的连通图G有Hamilton回路，G至少有n条边。

用p（G）表示图G的连通分量的个数。

定理1.G＝（V,E）是Hamilton图，则对任意V1ÍV,p（G-V1）≤|V1|.

证明：

设C是G的一个Hamilton回路，V1都在C上。

回路C中去掉V1中顶点，至多划分成|v1|段。

因此p（C-V1）≤|V1|.

例1.下图不是Hamilton图。

引理2.

n阶简单无向图G中，

l：

a……vivj……b，是一条有m个顶点的路径。

a，b只与l中顶点相邻，D（a）+D（b）≥m。

则l中所有顶点构成回路。

证明.

若a，b相邻，a……vivj……b是回路。

设a，b不相邻。

D（a）=s,D（b）=t.

s+t≥m。

t≥m－s。

l中存在相连顶点vi，vj，avj相邻，bvi相邻，

avj……bvi……a构成一个回路。

定理3.n阶简单无向图G中，n>2,任意两个不相邻顶点的度数之和大于等于n－1，则G有Hamilton路径。

证明.

取G中最长路径：

l：

a……vi……vj……b。

我们证明其长度为n－1，包含G的所有顶点，否则一定可以加长。

a，b不与l外的顶点相邻，否则l可以加长。

设l的长度≤n－2，l上共有顶点少于n－1个。

a,b度数和大于n－1，由引理1.l的所有顶点组成回路。

这时有一顶点c不在l上，c

c必与l中一点vi相邻。

我们得到含有顶点c，和l中所有顶点的路径，长度比l更长。

推论4.n阶简单无向图G中，n>2,任意两个不相邻顶点的度数之和大于等于n，则G有Hamilton回路。

证明.由定理3，G有Hamilton路径。

由引理2，这条路径可以构成一条Hamilton回路。

推论5.n阶简单无向图G中，n>2,任意顶点的度数大于等于n/2，则G有Hamilton回路。

定理6.G有n个顶点，m条边，如果

，则G是Hamilton图。

证明.

任取不相邻的两个顶点u，v∈G，

G中去掉u，v后导出子图G’,

G’有n－2个顶点，至多

条边。

u，v到G’的边数有

D（u）+D（v）≥n.

由推论4.G是Hamilton图。

§8.4运输网络TransportNetworks

§8.5匹配问题MatchingProblem

二部图、偶图BipartiteGraph：

无向图G＝（V,E）,

V=V1∪V2，V1∩V2＝。

V1中顶点互不相邻，V2中顶点互不相邻，任意边连接V1，V2中各一个顶点。

G=（V1,V2,E）.

完全二部图：

V1中每个顶点与V2中每个顶点都相邻。

|V1|=m,|V2|=n,完全二部图记做Km,n。

K2,3,K3,3.

定理1.二部图中没有奇数长的回路。

左边两图同构是K2,3，右边都是K3,3.

E*E.E*中的边互不相连，称E*为G的一个匹配。

边数最大的匹配叫最大匹配。

邻接V1或V2中所有顶点的匹配叫完全匹配。

|V1|=|V2|时，完全匹配也叫完美匹配。

定理2.（Hall定理）

设G=（V1,V2,E）,|V1|≤|V2|.

G中有完全匹配iffV1中任意k个顶点至少与V2中任意k个顶点相邻，即，任意XV1，|X|≤|R（X）|，R（X）为与X中顶点相邻的顶点的集合。

证明.是显然的。

对V1中顶点个数归纳：

|V1|=1是显然的。

设|V1|=k时定理成立。

|V1|=k＋1：

1）如果V1中任意k个顶点都至少与V2中k＋1个顶点相邻，从G中去掉一条边，V1中任意k个顶点都至少与V2中k个顶点相邻，存在完美匹配。

2）如果V1中存在k个顶点只与V2中k个顶点相邻，例如{a1,a2,……，ak}V1，

{b1,b2,……，bk}V2，

{a1,a2,……，ak}只与{b1,b2,……，bk}相邻。

则V1－{a1,a2,……，ak}任意s个顶点，都与V2－{b1,b2,……，bk}中s个顶点相连。

两部分都有完美匹配。

推论3.二部图G＝（V1,V2,E）中如果

（1）V1中每个顶点至少与V2中t条边相邻。

（2）V2中每个顶点至多与V1中t条边相邻。

则G有完美匹配。

证明.

V1中任意k个顶点的总度数≥kt。

V2中任意k个顶点的总度数≤kt。

V1中任意k个顶点至少与V2中k条边相邻。

由Hall定理，G有完美匹配。

推论4.正则二部图必有完美匹配。

§8.6染色图ColoringGraphs

平面图planargraph

agraphcanbedrawninaplanesothatnoedgescrossexceptatvertices

K5,K3,3不是平面图

平面图的面：

内部面，外部面，

有限面，无限面。

面的边界：

包围这个面的回路（不一定是简单回路）。

面的次数次数deg（R）=边界的长度。

非连通平面图有一个公共外面，边界由k个回路组成，k＝p（G）.

平面图每条边都是两个面的交线。

一条边处于一个内部面中或一个外部面中，面的次数要计算两次。

定理1.

平面图的所有面的次数之和等于边数的两倍：

极大平面图：

简单平面图，增加一边就不是平面图。

极小非平面图：

简单非平面图，减少一边就是平面图。

定理2.n阶极大平面图的性质：

（1）连通。

（2）n≥3时，每个面Ri，deg（Ri）=3.

（3）n≥4时，每个顶点v：

D（v）≥3。

定理3.欧拉定理：

满足n－m＋r＝2，

任意连通平面图G，满足n－m＋r＝2，

即，顶点数－边数＋面数＝2。

证明.对边数归纳：

m＝0，1，2，3显然。

增加一边：

增加一个顶点，不增加面。

不增加顶点，增加一面。

推论4.任意连通度为k的平面图G，满足n－m＋r＝k＋1。

不满足欧拉公式的简单图不是平面图。

请验证K5，K3,3，不是欧拉图。

定理5.设G是连通平面图，每个面的次数至少l，（l≥3），则m≤

。

证明.2m≥lr，

n－m＋r＝2，

ln－lm＋2m≥ln－lm＋lr＝2l，

lm－2m≤ln－2l

m≤

。

定理6.简单连通平面图G中至少有一点v，D（v）≤5.

证明.

假设任意顶点v，D（v）≥6.

6n≤2m，3r≤2m

3n≤m

n－m＋r＝2

6＝3n－3m＋3r≤m－3m＋2m＝0

这不可能。

定理7.（库拉图斯基定理）

一个图G是平面图当且仅当G没有可以收缩到K5或K3,3的子图。

每个凸多面体都可以映射到平面图。

定理8.正多面体只有正4，6，8，12，20面体五种。

证明.

设G是一个正多面体，n个顶点，m条边，r个面，每个顶点d度，每个面l次。

由定理6，3≤d≤5。

l≥3。

dn＝2m，lr=2m＝dn.

n－m＋r=2，

2ln－2lm＋2lr=4l，

2ln－dln＋2dn=4l，

n=4l/（2l－dl＋2d），

1）d＝3.

n=4l/（6－l）

l=3,n=4,m=6,r=4.

正四面体

l＝4，n＝8，m=12,r=6,

正六面体.

l＝5，n＝20，m=30,r=12,

正12面体

2）d＝4.

n=2l/（4－l）.

l=3,n=6,m=12,r=8,

正八面体。

3）d＝5.

n=4l/（10－3l）.

l＝3，n＝12，m＝30，r＝20

正20面体。

对偶图：

设G＝（T,V）是平面图，

（1）G的每个面Ri中取一点vi*，

V*={v1*，v2*，……，vr*}

（2）若两个面Ri，Rj有公共边界ek，连接vi*，vj*，得到边ek*，

E*={e1*，e2*，……，em*}

则得到G*=（V*,E*）称为G的对偶图。

G和G*边数相同，m*＝m;

G的面数等于G*的顶点数，n*=r;

G连通，则G的顶点数等于G*的面数,r*=n.

G不连通，则G的顶点数等于G*的面数,r*=n－p（G）＋1.

G和G*不同构，同构图的对偶图不一定同构。

G**不一定同构于G。

不连通图的对偶图连通，连通图的对偶图连通。

若GG*，就称G是自对偶的图。

染色图colouringGraph

一个图用彩色将每个顶点着色，相邻顶点染不同颜色。

一个平面图用彩色将每个面着色，相邻面染不同颜色。

只要换成其对偶图即可。

平面图G最少用k种颜色染色，就称为k色图。

k称为chromaticnumberofG.记做χ（G）

四色定理：

任何一个平面图都是四色图。

染色多项式chromaticpolynomial

用n种颜色染一个图，有多少不同的方法,记做PG（n）.

PG是一个多项式函数，称为chromaticpolynomialofG.

例4.设L4是4个顶点的一条线。

用x种颜色，第一点，x种方法着色，第二点x－1种方法着色。

第三第四点都是x－1。

PL4（x）=x（x-1）3.χ（L4）＝2。

例5．PKn（x）＝x（x-1）（x-2）……（x-n+1）=[x]n.

χ（Kn）＝n。

定理1.设G1，G2，……，Gm是G的连通分量，则PG（x）=PG1（x）PG2（x）……PGm（x）。

χ（G）＝max{χ（G1）,χ（G2）,……，χ（Gm）}

例6.G是两个不相连三角形，PG（x）=x2（x-1）2（x-2）2.

例7.G是n个不相连顶点，PG（x）=xn。

Ge是G去掉e导出的子图，Ge是将e的两端点粘合得到的图。

定理2.PG（x）＝PGe（x）－PGe（x）

证明.

设e的端点为a，b。

G着色必须将ab着不同色。

Ge着色必须将ab着同色。

Ge着色a，b可着同色，可着不同色。

PGe（x）＝PG（x）+PGe（x）.

例G如下图。

PGe（x）=x2（x-1）2（x-2）2,

PGe（x）=x（x-1）2（x-2）2,

PG（x）=PGe（x）－PGe（x）

=x2（x-1）2（x-2）2－x（x-1）2（x-2）2

＝x（x-1）3（x-2）2,

χ（G）=3,G是3色图。

引理3.

设G是简单图，G已染色，相邻顶点颜色不同。

G中染色αβ两种颜色的顶点导出子图为Gαβ.交换Gαβ中一个连通分量中染色α和β，G仍然保持相邻顶点不同颜色。

证明.G中任意相邻两点a，b.

bGαβ，或a，b∈Gαβ，或a∈Gαβ且bGαβ，a，b染色仍然不同。

定理4（五色定理）

G是任意一个平面图,则χ（G）≤5。

证明.对G的顶点个数归纳。

G中至少有一点a，D（a）≤5。

归纳假设去掉a，导出的子图G’可以用5重颜色着色。

如果a只与G’中4个点相邻，a可以用第五种颜色着色。

如果a与G’中5个点相邻，但5点中有重复颜色，a可以用第五种颜色着色。

假设a与G’中5个点相邻，5点着色各不相同，5点分别是b1，b2，……，b5。

设b1着色α，b2着色β，而b1，b2，不在Gαβ的同一个连通分量中。

由引理3，交换b3所在分量中颜色α和β，可以使b1，b3着色相同。

这时a可着色。

设b1着色α，b3着色β，而b1，b3在Gαβ的同一个连通分量中。

这时b1到b2有一条着色αβ相间的链。

与a形成一条回路，组成一个面。

b2在这个面的内部或在外部。

如果同样b2，b4；b3，b5；b3，b5；b2，b5；b1，b4都有一个这样的链，相互交叉。

这时a，b1，b2，b3，b4，b5组成一个K5。

与G是平面图矛盾。

这是不可能的。