图论及其应用

本文格式为Word版，下载可任意编辑——图论及其应用图和子图图

图G=(V,E)，其中V={

}V顶点集，?顶点数

边集，?边数

E={e1,e2,,e?}例。左图中，V={a,b,,f},E={p,q,ae,af,,ce,cf}注意，左图仅仅是图G的几何实现（代表），它们有无穷多个。真正的图G是上面所给出式子，它与顶点的位置、边的形状等无关。不过今后对两者将经常不加以区别。

称边ad与顶点a(及d)相关联。也称顶点b(及f)与边bf相关联。

称顶点a与e相邻。称有公共端点的一些边彼此相邻，例如p与af。

环（loop，selfloop）：如边l。棱（link）：如边ae。重边：如边p及边q。简单图：（simplegraph）无环，无重边平凡图：仅有一个顶点的图（可有多条环）。一条边的端点：它的两个顶点。

?(G)?E(G).。记号：?(G)?V(G),

习题

???1.1.1若G为简单图，则????。

?2?abcrpqdef

G=(V,E)1.1.2n(?4)个人中，若每4人中一定有一人认识其他3人，则一定有一人认识其他n-1人。

同构

在下图中，图G恒等于图H,记为G=H?VG)=V(H),E(G)=E(H)。图G同构于图F?V(G)与V(F),E(G)与E(F)之间各存在一一对应关系，且这二对应关系保持关联关系。记为G?F。

注往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否一致。

xadwcxdwca?x?d?w?c?babb?yezyezy?e?z?G=(V,E)

H=(V?,E?)F=(V??,E??)

1

注判定两个图是否同构是NP-hard问题。完全图(completegraph)Kn

空图（emptyg.）?E=?。

V?(?V)为独立集?V?中任二顶点都互不相邻。

二部图（偶图，bipartiteg.）G=(X,Y;E)?存V(G)的一个2-划分(X,Y),使X与Y都是独立集。

完全二部图Km,n?二部图G=(X,Y)，其中X和Y之间的每对顶点都相邻，且?X?=m,?Y?=n。

K1K2K3K4K5类似地可定义，完全三部图（例如Km,n,p），完全n-部图等。

例。用标号法判定二部图。习题

二部图

1.2.1G?H??(G)=?(H),?(G)=?(H)。并证明其逆命题不成立。1..2.2证明下面两个图不同构：

1.2.3证明下面两个图是同构的：

1.2.4证明两个简单图G和H同构?存在一一映射f:V(G)?V(H)，使得uv?E(G)当且仅当

f(u)f(v)?E(H)。

1.2.5证明：(a).?(Km,n)=mn;

(b).对简单二部图有???2/4.

1.2.6记Tm,n为这样的一个完全m-部图：其顶点数为n，每个部分的顶点数为[n/m]或{n/m}个。证明：

?n?k??k?1?(a).?(Tm,n)=???(m?1)??其中k=[n/m].

?2??2?K3,3K1,5K2,2,2(b).对任意的n顶点完全m-部图G，一定有?(G)??(Tm,n)，且仅当G?Tm,n时等式才成立。

1.2.7所谓k-方体是这样的图：其顶点是由0与1组成的有序k-元组，其二顶点相邻当且仅当它

k-1

们恰有一个坐标不同。证明k-方体有个顶点，k*2条边，且是一偶图。

1.2.8简单图G的补图Gc是指和G有一致顶点集V的一个简单图，在Gc中两个顶点相邻当且仅当它们在G不相邻。

(a).画出Kcn和Kcm,n。

(b).假使G?Gc则称简单图G为自补的。证明：若G是自补的，则??0,1(mod4)

2

*

关联矩阵M(G)与邻接矩阵A(G)

M(G)=[mi,j]???,

A(G)=[ai,j]???,其中mi,j=顶点vi与边ej的关联次数=0,1,2.ai,j=连接顶点vi与vj的边数。

例。

e1??M(G)?????1100e21100e30110e40011e51001e60002e71?v1?0v2?1?v3?0?v4v1e1e2e5e6v4e4G=(V,E)v3e7e3v2

v1??A(G)?????0211v22023v31101v41011?v1?v?2?v3??v4

子图

子图(subgraph)H?G?V(H)?V(G),E(H)?E(G)。真子图H?G。母图（supergraph）。

生成子图（spanningsubg.）?H?G且V(H)=V(G)。生成母图。

基础简单图（underlyingsimpleg.）。

导出子图（inducedsubg.）G[V?],(非空V??V)?以V?为顶点集，以G中两端都在V?上的边全体为边集构成的G的子图。边导出子图G[E?]非空E??E?以E?为边集，以E?中所有边的端点为顶点集的的子图。例。

ueydxcfghwG[{u,w,x,y}]G[{u,w,x}]avbG[{f,c]}G[{c,d,e}]

以上两种子图，其实，对应于取子图的两种基本运算。下面是取子图的另两种基本运算：G-V’?去掉V?及与V?相关联的一切边所得的剩余子图。

G=(V,E)

3

?即G[V\\V?]

G-E’?从中去掉E?后所得的生成子图

例。G-{b,d,g},(=G[E\\{b,d,g}])G-{b,c,d,g},(?G[E\\{b,c,d,g}])G-{a,e,f,g}.(?G[E\\{a,e,f,g}])

注意G[E\\E?]与G-E?虽有一致的边集，但两者不一定相等：后者一定是生成子图，而前者则不然。

上述四种运算是最基本取子图运算，今后老要遇到，一定要认真把握好。关于子图的一些定义还有：G+E??往G上加新边集E?所得的（G的母）图。为简单计，今后将G?{e}简计为G?e；G-{v}简计为G-v。设G1,G2?G，称G1与G2为不相交的（disjiont）?V(G1)?V(G2)=?(?E(G1)?E(G2)=?)

边不相交（edge-distjiont）?E(G1)?E(G2)=?。(但这时G1与G2仍可能为相交的）。并图G1?G2,当不相交时可简记为G1+G2.交图G1?G2.

习题

1.4.1证明：完全图的每个导出子图是完全图；偶图的每个导出子图是偶图。

1.4.2设G为一完全图，1?n??-1。证明：若??4，且G中每个n顶点的导出子图均有一致

c

的边数，则G?K?或K?。

顶点的度

顶点v的度dG(v)=G中与顶点v相关联边数。（每一环记为2）最大、最小度?，?。（?(G),?(G))定理1.1(handshakinglemma)任一图中，?d(v)?2?.

v?V系1.1任一图中，度为奇数顶点的个数为偶数。

例。任一多面体中，边数为奇数的外表面的数目为偶数。证明。作一图，使其顶点对应于多面体的面，并使其中二顶点相邻当且仅当对应的两个面相邻。?

k-正则图（k-regularg.)?d(v)=k,?v?V.习题

0-正则图1-正则图2-正则图3-正则图1.5.1证明：??2?/???。

1.5.2若k-正则偶图(k>0)的2-划分为(X,Y),则

?X?=?Y?。

1.5.3在人数>1的人群中，总有二人在该人群中有一致的朋友数。

1.5.4设V(G)={v1,v2,,v?}，则称(d(v1),d(v2),,d(v?))为G的度序列。证明：非负

4

n整数序列(d1,d2,,dn)为某一图的度序列?

?di?1i是偶数。

1.5.5证明：任一无环图G都包含一偶生成子图H，使得dH(v)?dG(v)/2对所有v?V成立。

*

1.5.6设平面上有n个点，其中任二点间的距离?1，证明：最多有3n对点的距离=1。

路和连通性

途径（walk)例如（u，x）-途径W=ueyfvgyhwbvgydxdydx(有限非空序列）=uyvywvyxyx(简写法当不引起混淆时）起点（origin）u。终点（terminus）x。u内部顶点（internalvertex）y,v,w,x。

ea（注意，中间出现的x也叫内部顶点。）

yfv长?边数（重复计算）。

g节（段，section）。例如W的(y,w)-节=yvw。

dhbW-1

（逆途径）,WW’（两条途径W与W?相衔接）。迹(trail)?边各不一致的途径。例如，yvwyx。xcw路(path)?顶点各不一致的途径。（可当作一个图或子

图)。例如，yvwx。

d(u,v)=u与v之间最短路的长。例。（命题）G中存在(u,v)-途径?G中存在(u,v)-路。

G中顶点u与v为连通的(connected)?G中存在(u,v)-路

(?G中存在(u,v)-途径。)

V上的连通性是V上的等价关系，它将V划分为（等图G价类）：

V1,,V?

使每个Vi中的任二顶点u及v都连通（即存在(u,v)-路）。称每个G[Vi]i=1,2,?

为G的一个分支（component）;称?(G）为G的分支数。G为连通图??(G)=1

?G中任两点间都有一条路相连。G为非连通图??(G)?1。

记号对任一非

S?V，令S=V\