离散数学集合论图论chapter

第14讲图的基本概念2021/7/23《集合论与图论》第14讲11.预备知识,无向图,有向图,相邻,关联2.度,握手定理,度数列,可(简单)图化3.图同构4.图族图论参考书Graph

Theory,R.Diestel,Springer,1997,(O157.5/D566)(有只读电子版)现代图论(影印版),科学出版社-Springer,2001,(O157.5/B638m/2001)离散数学及其应用,机械工业出版社,2002,20042021/7/23《集合论与图论》第14讲2预备知识2021/7/23《集合论与图论》第14讲3有序积:

A·B={

<x,y>

|x˛

A y˛

B}有序对:<x,y>„<y,x>无序积:

A&B={

(x,y)

|x˛A y˛

B}无序对:(x,y)=(y,x)多重集:{a,a,a,b,b,c}„{a,b,c}重复度:a的重复度为3,b的为2,c的为1无向图(undirected

graph)无向图(graph):G=<V,E>,V„˘

,顶点,结点(vertex/node)多重集E˝V&V,边(edge/link)例:

G=<V,E>,V={a,b,c,d,e}, E={(a,a),(a,b),(a,b),(b,c),(c,d),(b,d)}.a

d

b

ceu

v2021/7/23《集合论与图论》第14讲4(u,v)有向图(directed

graph)有向图(digraph):D=<V,E>,V„˘

,顶点,结点(vertex/node)多重集E˝V·V,边(edge/link/arc)例:

D=<V,E>,V={a,b,c,d,e},

E={

<a,a>,<a,b>,<a,b>,<b,a>,<b,c>,<c,d>,(d,b)

}.a

db

ceu(起点)

v(终点)<u,v>2021/7/23《集合论与图论》第14讲5n阶图,零图,平凡图,空图若G=<V,E>,则V(G)=V,E(G)=E若D=<V,E>,则V(D)=V,E(D)=En阶图(order-n

graph):|V(G)|=n有限图(finite

graph):|V(G)|<¥零图(null

graph):E=˘

,Nn平凡图(trival

graph):1阶零图,N1空图(empty

graph):V=E=˘

,˘2021/7/23《集合论与图论》第14讲6标定图,非标定图,基图标定图(labeled

graph):顶点或边带标记非标定图(unlabeled

graph):顶点或边不带标记基图(底图):

有向图去掉边的方向后得到的无向图b

ca

d2021/7/23《集合论与图论》第14讲7相邻(adjacent),关联(incident)相邻(邻接)(adjacent):点与点,边与边邻接到,邻接于:u邻接到v,v邻接于u关联(incident):点与边关联次数:环(loop):只与一个顶点关联的边孤立点(isolated

vertex):平行边(parallel

edge):?1

1

+1

-1

2u

v2021/7/23《集合论与图论》第14讲8邻域(neighborhood)邻域:

NG(v)={u|u˛

V(G)

(u,v)˛

E(G)

u„v}闭(closed)邻域:-关联集:IG(v)

={e

|

e与v关联}后继:GD

(v)={u|u˛

V(D)

<v,u>˛

E(D)

u„v}+前驱:GD

(v)={u|u˛

V(D)

<u,v>˛

E(D)

u„v}NG

(v)

=

NG

(v)

¨

{v}邻域:

NG(v)=GD

(v)¨

GD

(v)+

-闭邻域:ND

(v)=ND

(v)¨

{v}2021/7/23《集合论与图论》第14讲9顶点的度数(degree/valence)-度dG(v):与v关联的边的次数之和出度dD

(v):

与v关联的出边的次数之和+入度dD

(v):与v关联的入边的次数之和度dD(v)

=dD

(v)

+

dD

(v)+

-33

040,01,2

(d+,d-)2,12,22021/7/23《集合论与图论》第14讲10最大(出/入)度,最小(出/入)度2021/7/23《集合论与图论》第14讲11-最大度:D(G)=max{dG(v)

|

v˛

V(G)}最小度:

d(G)

= min{

dG(v)

|

v˛

V(G)

}最大出度:

D+(D)

=

max{

dD

(v)|v˛

V(D)

}+最小出度:

d+(D)

= min{

dD

(v)

|

v˛

V(D)

}+最大入度:D-(D)=max{dD

(v)|

v˛

V(D)}-最小入度:

d-(D)= min{

dD

(v)

|

v˛

V(D)

}简记为D,d,D+,d+,D-,d-握手定理(图论基本定理)2021/7/23《集合论与图论》第14讲12定理1:设G=<V,E>是无向图,V={v1,v2,…,vn},|E|=m,

则d(v1)+d(v2)+…+d(vn)=2m.

#定理2:设D=<V,E>是有向图,V={v1,v2,…,vn},|E|=m,

则d+(v1)+d+(v2)+…+d+(vn)=

d-(v1)+d-(v2)

+…+d-(vn)

=

m.

#推论:任何图中,奇数度顶点的个数是偶数.#简单图(simple

graph),正则图简单图(simple

graph):无环,无平行边若G是简单图,则0£

D(G)£

n-1k-正则图(regular

graph):"v,d(v)”k2021/7/23《集合论与图论》第14讲13度数列v22021/7/23《集合论与图论》第14讲14v3v4v5度数列:设G=<V,E>,V={v1,v2,…,vn},称d

=

(

d(v1),d(v2),…,

d(vn)

)为G的度数列例:d

=(5,1,2,3,3)v1可图化,可简单图化可图化:设非负整数列d=(d1,d2,…,dn

),若存在图G,使得G的度数列是d,则称d为可图化的可简单图化:设非负整数列d=(d1,d2,…,

dn

),若存在简单图G,使得G的度数列是d,则称d为可简单图化的例:d

=(5,3,3,2,1)2021/7/23《集合论与图论》第14讲15定理3(可图化充要条件)定理3:非负整数列d=(d1,d2,…,dn)是可图化的,当且仅当d1+d2+…+dn=0(mod

2).证明:()握手定理( )奇数度点两两之间连一边,剩余度用环来实现.

#例2:(1)d=(5,4,4,3,3,2);(2)d=(5,3,3,2,1).5

33

153312021/7/23《集合论与图论》第14讲16Havel定理(可简单图化充要条件)2021/7/23《集合论与图论》第14讲17定理5(V.Havel,1955):设非负整数列d=(d1,d2,…,dn)满足:d1+d2+…+dn=0(mod

2),n-1‡d1‡d2‡…‡dn‡0,则d可简单图化当且仅当d’=(d2-1,d3-1,…,dd1+1-1,dd1+2,…,dn)可简单图化.例:d=(4,4,3,3,2,2),d’=(3,2,2,1,2)Havel定理(举例)2021/7/23《集合论与图论》第14讲18例4:判断下列非负整数列是否可简单图化.

(1)

(5,5,4,4,2,2)

(2)(4,4,3,3,2,2)解:(1)(5,5,4,4,2,2),(4,3,3,1,1),(2,2,0,0),(1,-1,0),不可简单图化.(2)

(4,4,3,3,2,2),

(3,2,2,1,2),

(3,2,2,2,1),(1,1,1,1),(0,1,1),(1,1),可简单图化.#Havel定理(证明示意)1v

v2v3vnG’2021/7/23《集合论与图论》第14讲19Gd

=(d1,d2,

d3,vd1+1

vd1+2dd1+1,

dd1+2,dn)v2

v3d’

=

(d2-1,

d3-1,vd1+1

vd1+2dd1+1-1,

dd1+2,vndn)……………………Havel定理(证明)2021/7/23《集合论与图论》第14讲20证明:

( )

设d’=(d2-1,d3-1,…,dd1+1-1,

dd1+2,

…,

dn)可简单图化为G’=<V’,E’>,

其中V’={v2,v3,…,vn},则令G=<V,E>,V=V’¨

{v1},E

=E’

¨

{(v1,v2),

(v1,v3),

…,

(v1,vd1+1)

},于是d可简单图化为G.Havel定理(证明,续)2021/7/23《集合论与图论》第14讲21证明:()设d可简单图化为G=<V,E>,其中V={v1,v2,…,vn},d(v1)‡d(v2)‡…‡d(vn).若NG(v1)={v2,v3,…,vd1+1},则令G’=<V’,E’>,

V’=V-{v1},E’=E-{

(v1,v2),

(v1,v3),

…,

(v1,vd1+1)},于是d’可简单图化为G’.若$i$j(

i<j

viˇNG(v1) vj˛NG(v1)

),Havel定理(证明示意)1v

v2vivd1+1vnGd

=(d1,

d2,

d3,dd1+1,

dd1+2,dn)……vk

vj……12021/7/23《集合论与图论》第14讲22v

v2vivd1+1vnG1d

=(d1,d2,

d3,dd1+1,

dd1+2,dn)……vk

vj……v1ˇNG(vi)

v1˛NG(vj) di‡dj

$vk(vk˛

NG(vi)

vkˇNG(vj)Havel定理(证明,续)2021/7/23《集合论与图论》第14讲23证明:()(2)若$i$j(1£i<j£n

viˇNG(v1)

vj˛NG(v1)),则由di‡dj可得$k(1£k£n

vkˇNG(vj)

vk˛NG(vi)),令G1=<V,E¨

{(v1,vi),(vk,vj)}-{(v1,vj),(vk,vi)}>,则G1与G的度数列都还是d,重复这个步骤,直到化为(1)中情形为止.

#Havel定理(证明中包含的思想)2021/7/23《集合论与图论》第14讲24构造性证明:给出具体构造方法先处理“简单,好的”情形,再把“复杂,坏的”情形化为前者来处理定理4(可简单图化充要条件)2021/7/23《集合论与图论》第14讲25定理4(P.Erdös,T.Gallai,1960):设非负整数列d=(d1,d2,…,dn)满足:n-1‡d1‡d2‡…‡dn‡0,则d可简单图化当且仅当d1+d2+…+dn=0(mod

2)并且对r=1,2,…,n-1有d1+d2+…+dr

£

r(r-1)+min{r,dr+1}+min{r,dr+2}+…+min{r,dn}.

#定理4’(等价形式)2021/7/23《集合论与图论》第14讲26定理4’(P.Erdös,T.Gallai,1960):非负整数列d=(d1,d2,…,dn)可简单图化当且仅当d1+d2+…+dn=0(mod

2)并且对r=1,2,…,n有d1+d2+…+dr

£

r(r-1)+min{r,dr+1}+min{r,dr+2}+…+min{r,dn}.

#说明:n-1‡d1‡d2‡…‡dn‡0

d1+d2+…+dn

£

n(n-1).定理4(举例)2021/7/23《集合论与图论》第14讲27例3:判断下列非负整数列是否可简单图化.

(1)

(5,4,3,2,2,1)

(2)(5,4,4,3,2)(3)

(3,3,3,1)

(4)(6,6,5,4,3,3,1)(5)

(5,5,3,3,2,2,2)(6)

(d1,d2,…,dn),

d1>d2>…>dn‡1,解:(1)

5+4+3+2+2+1=17„0(mod

2).不可(简单)图化.定理4(举例)2021/7/23《集合论与图论》第14讲28例3:判断下列非负整数列是否可简单图化.

(2)(5,4,4,3,2)解:

(2) 5+4+4+3+2=18=0(mod

2).但是d1=5>n-1=4,不满足n-1‡d1,不可简单图化.(或者:但是r=1时,d1=5>1(1-1)+min{1,4}+min{1,4}+min{1,3}+min{1,2}=4,不可简单图化.)定理4(举例)2021/7/23《集合论与图论》第14讲29例3:判断下列非负整数列是否可简单图化.(3)(3,3,3,1)解:

(3) 3+3+3+1=10=0(mod

2).d1=3=n-1,满足n-1‡d1,但是r=2时,d1+d2=6>2(2-1)+min{2,3}+min{2,1}=5,不可简单图化.定理4(举例)例3:判断下列非负整数列是否可简单图化.(4)(6,6,5,4,3,3,1)解:

(4) 6+6+5+4+3+3+1=28=0(mod

2).d1=6=n-1,满足n-1‡d1.r=1,2时,d1=6£1(1-1)+min{1,6}+min{1,5}+…=6,d1+d2=12>2(2-1)+min{2,5}+…=11,不可简单图化.或:6,6,*,*,*,*,1不可简单图化2021/7/23《集合论与图论》第14讲30定理4(举例)2021/7/23《集合论与图论》第14讲31例3:(5)(5,5,3,3,2,2,2)解:

(5) 5+5+3+3+2+2+2=22=0(mod

2).d1=5<n-1,满足n-1‡d1.r=1,2,…,7时,d1=5<1(1-1)+min{1,5}+min{1,5}+…=6,d1+d2=10<2(2-1)+min{2,3}+…=12,d1+d2+d3

=13<3(3-1)+min{3,3}+…=15,d1+d2+d3+d4

=16<4(4-1)+min{4,2}+…=18,定理4(举例)2021/7/23《集合论与图论》第14讲32例3:(5)(5,5,3,3,2,2,2)解:(5)d1+d2+d3+d4

=16<4(4-1)+min{4,2}+…=18,d1+d2+…+d5

=18<5(5-1)+min{5,2}+…=24,d1+d2+…+d6

=20<6(6-1)+min{6,2}=32,d1+d2+…+d7

=22<7(7-1)=42,可简单图化.定理4(举例)例3:(5)(5,5,3,3,2,2,2)解:(5)可简单图化.(5,5,3,3,2,2,2),

(4,2,2,1,1,2),

(4,2,2,2,1,1),(1,1,1,0,1),(1,1,1,1),

(0,1,1),(1,1)2021/7/23《集合论与图论》第14讲33定理4(举例)2021/7/23《集合论与图论》第14讲34例3:判断下列非负整数列是否可简单图化.

(6)(d1,d2,…,dn),

d1>d2>…>dn‡1,解:(6)d1>d2>…>dn‡1,dn-1‡2,dn-2‡3,…,d1‡n,不满足n-1‡d1,不可简单图化.#Paul

Erdös(1913-1996)保罗•爱尔特希,匈牙利人廿世纪数学界的传奇人物“Another

roof,

another

proof.”2021/7/23《集合论与图论》第14讲35PaulErdös(1913-1996)“My

mother

said,

‘Even

you,

Paul,

canbe

in

only

one

place

at

one

time.’Maybe

soon

I

will

be

relieved

of

this

disadvantage.Maybe,

once

I've

left,

I'll

be

able

to

be

in

many

places

at

the

same

time.Maybe

then

I'll

be

able

to

collaboratewith

Archimedes

and

Euclid.”2021/7/23《集合论与图论》第14讲36图同构(graph

isomorphism)2021/7/23《集合论与图论》第14讲37图同构:设(有向)图G1=<V1,E1>,G2=<V2,E2>,若存在双射f:V1fi

V2,满足

"u˛V1,"v˛V1,(u,v)˛

E1

«(

<u,v>˛

E1

«(f(u),f(v))˛

E2<f(u),f(v)>˛

E2

)则称G1与G2同构,记作G1@G2说明:同构的图,其图论性质完全一样算法：NAUTY图同构(举例)G1G3G2G1@G3,

G1@G22021/7/23《集合论与图论》第14讲38图同构(举例)G1G3G2G1@G3,

G1@G22021/7/23《集合论与图论》第14讲39图同构(举例)G1G2G3G1@G2@G32021/7/23《集合论与图论》第14讲40图同构(举例)D1D3D2D1@D2,

D2@D32021/7/23《集合论与图论》第14讲41图族(graph

class)2021/7/23《集合论与图论》第14讲42花束,两极完全图,有向完全图,竞赛图正则图,柏拉图图,彼德森图,库拉图斯基图r部图,二部图(偶图),完全r部图路径,圈,轮,超立方体树花束(bouquets)B12021/7/23《集合论与图论》第14讲43B2B3B4B5两极(dipoles)D12021/7/23《集合论与图论》第14讲44D2D3D4D5完全图(complete

graphs)K1K2K3K4K52021/7/23《集合论与图论》第14讲45有向完全图2021/7/23《集合论与图论》第14讲46竞赛图(tournament)2021/7/23《集合论与图论》第14讲47正则图(regular

graph)2021/7/23《集合