第一章 基本概念 1.1图的概念 世界上许多半物以及它们之间的联系都可以用图形直观地表示。这时人们往往用结 点表示车物.用边表示它们之间的联系。这种出结点和边构成的图形就是图论所研究的 对象。 (8) (b) (c) 图i.I 图1.2 例1.1.1A、B、C、D4个队进行循环赛。为了解当前各队的胜负情况，可以用结点 表示队，用有向边(u,)表示u队胜v队。例如图1.1表示A胜B、C、D:B胜C；D胜C, 而B和D之间还没有比赛， 例1.1.2两个直流电路如图1.2(a)(b)。基尔霍夫定律指出：电路特性只与电路网 络的拓扑性质有关，而与支路元件的特性无关。因此都可以将它们转化为图1.2（©）进行 研究。 例1.1.3人们常用框图的形式来 帮助编写或描述程序。当需要对程序进 行分析时，也往往用结点表示程序框，用 有向边表示它们之间的顺序关系，如图 1.3。 定义1.1.1二元组(V(G),E(G)) 称为图。其中V(G)是非空集合，称为结 舒 点集，E(G)是V(G)诸结点之间边的集 合。常用G=(V,E)表示图。 (b) 图可以分为有限图与无限图两类。 图1.3 本书只讨论有限图，即V和E都是有限 集。给定某个图G=(V,E),如果不加特殊说明，就认为V={,2,…,vn},E={e,e2,…, en},即结点数|v=n,边数|E引=m。 图G的边可以是有方向的，也可以是无方向的。它们分称为有向边（或弧）和无向边， 用e4=(,o,)表之。这时我们说与y,是相邻结点；e分别与：，v,相关联。如果e4是有 。1·
向边，称是4的始点，；是的终点；并称是巴，的直接前趋，，是：的直接后继。 如果：是无向边，则称，，是的两个端点。全部白有向边构成的图叫有向图；只由无 向边织成的图叫无向图：既有有向边又有无向边构成的图称为混合图。例如图1.4(a)是 有向图.()是无向图，()是混合图。在图G中，只与-一个结点相关联的边称为自环，在同 一对结点之间可以存在多条边，称之为重边。含有重边的图叫多重图。比如图1.4(a)(b) 中a1,e,分别是白环，a:a:和eer分别是重边， (a) (b) (c) 图1.4 定义1.1.2G一(V.E)的某结点v所关联的边数称为该结点的度，用d()表示。如 果v带有白环，则自环对d()的贡献为2。 例如图1.4(a)中，d()=5,d(2)=2,d(v3)=5,d(4)=4。(b)中，d(v)=5,d (2)=3,d(v)=5,d(v)=5。有向图中由于各边都是有向边，因此每个结点v还有其正 度(d()和负度(d(v)),d*(v)的值是以v为始点的边的数目，d(v)是以v为终点的 边的数目。显然有d·(v)十d()=d(u)。 定义1.1.3任意两结点间最多只有一条边，且不存在自环的无向图称为简单图。 以下所说的图在不加说明的情况下指的是无向图。 没有任何边的简单图叫空图，用N,表示：任何两结点间都有边的简单图称为完全 图，用K。表示。K.中每个结点的度都是n一1。 图(G具有以下基本性质。 性质【.1.1·设G-(V,E)有n个结点，m条边，则 >d()=2m。 -EV(G) 证明：血于每条边e=(u,)对结点和v度的贡献各为1，因此m条边对全部结点 度的总贡献就是2m。 性质1.1.2G中度为奇数的结点必为偶数个， 证明：G中任结点的度或为偶数或为奇数，设V,是度为偶的结点集，V。是度为奇 的结点集。于是有 d(e)÷≥d(o)=2m, 因此4®)为偶数.即V中含有阀数个结点. 性质1.1.3有向图G中正度之和等于负度之和。 这是因为每条边对结点的正、负度贡献各为1。 ·2
性质1.1.4K,的边数是号(m-) 明：K中每各结点的度都是(n一1)，由性质1,1.1即得、 性质1.1.5简单图(；中一定存在肢相同的结点， 证明：设G中不存在弧立结点，则对个结点的简 单图，每个结点度d()的取值范倒是1~(-…1)，由抽屉 原理，定存在两个度相同的结点。若存在孤立结点，亦 类似可证， 定义1.1.4如果图G=(V,E)的每条边e=(, ,)都赋以一个实数心：作为该边的权，则称G是赋权图。 特别地，如果这些权都是正实数，就称G是E权图。 图1.5就是一个正权图。权可以表示该边的长度.时 1.5 间，费用或容量等。 定义1.1.5给定G=(V,E),如果存在另-个图(G”=(,E),满足V'三V,三E, 则称G是（的-个子图。特别地，如果V=V,就称G是C的支撑子图或生成子图；如泉 '二V,且E包含了G在结点子集V之间的所有边，则称G是G的导出子图。 例如，图1.6中的G和G:分别是的支撑子图和导出子图，（是G的子图。按照 子图的定义，显然G也是它自身的子图，而且既是支撑子图，也是导出子图。空图也是G 的了图.而月是支撑子图.它们都称为平凡子图。 G 图1.6 定义1.1.6给定两个图G1=(V,E,),G一(V2,Ez)。令GUG=(V,E),其中V =VUV2,E=EUE,CG∩G2=(V,E),其中V=V:∩V2,E=E∩E2,G,①G2=(V. E),其中V=V1UV:,E=E,⊕E2,分别称为G和G2的并、交和对称差。 例如图1.？中G和G2的并、交，对称差分别是(a)、(b)和(c)。 在G中删去一个子图H,指删掉H中的各条边，记作G一H,特别地，对于简单图G, 称K.一G为G的补图，记作G。例如图1.7中G1的补图是(d)。从G中去某个结点v 及其关联的边所得到的图记作G一v。从G中删去某条特定的边e=(u,u),记作G-e,例 如图1.6中G一=(G2,G2一(，s)=G。显见G一是(G的导出子图，而G一e是G的支 撑子图。如果在G中增加某条边e,可记作G十e,例如G3十(v,u)=G2。 ▣3·
(a (b) (c) (d) 图1.7 如果G是无向图，则『(o)={u|(,)∈E}称为v的邻点集。 定义1.1.7设v是有向图G的-个结点，则 -(v)={ul(w,u)∈E; 称为的直接后继集亦称外邻集：相应地 下-(v)={ul(u,v)∈E; 称为的直接前趋集亦称内邻集。 例如图1.6(a)的()={：，2，a},(3）二i5};「(1)={1u},T(2）= {1}。图1.5中，(v)=i23:g,「(e)={1,,:i。 给定了结点数甘及它们之间的 相邻关系，使很容易画出图(G,不过 它的形状不是唯一的。这种形状 同但结构相问的图叫做同构。 定义1,1.8两个图G1=(V, E),G=(V,E2),如果V:和V 之间存在双射f,而且(u,v)∈E:, G 当且仅当(f(u),f(v)∈E,时，称 G2 图1,8 G和(G2同构。记作G,G2。 例1.1.4图1.8的G和(G2是同构的。因为设f(v:)=a,f(2)=z,f(v)=b,f (4)=y,f(o）=c,f(vs)=x时，对任意e=(w,)∈E1,都有e'=(f(),f(v))∈E2,反 之亦然，即 (12)∈E1(f(w1),f(2))=(a,x）∈E2, 。4
(1u4)∈E1→(f(,),f(2))=(a,y)∈E2, (1a)∈E:+(f(y),f(2))-(a,)∈， (,,)∈E:+(f(2),f(3))(x,b)∈E2, (t2.:)∈E,(f(2)、f(vs)=(x,c)∈E, (ts,1)∈E+(f(u3),f(:)-(b,y)∈2， (vs,Us)EE+(f(v:),f(vn))-(6,2)EE: (4,s)∈E,(f(v1),f())=(yc)∈E· (u:,)∈E+(f()、f(6)-=(c,z)∈Ee, 从定义可知，如若G,2(2,必须满足。 (1)V(G)=V(C)i,(G)1=iE(G)i. (2)(G,和G:结点度的非增序列相同。 (3)存在同构的导出子图。 .·其中(3)对判定两个图不同构有时十分有效，例如图1.9的(G不存在与C:结点集4，b, c,d,e,f}所成的导山子图同构的子图，因此G:与(2不同构。 1 0 Vi G G2 图1.9 1.2图的代数表示 在对图G进行描述或运算时，需要采用代数方法进行表示。常用的表示方法有 .1.2.1邻接矩阵 邻接矩阵表示了结点之间的邻接关系。 有向图的邻接矩阵A是-·个n阶方阵，其元素为。 1,()∈E。 a,10.其它 例如图1.10的邻接矩阵是 。5·
f01110 00101 A=0101 0 0 0000 l 0.011 1.10 邻接矩阵A第；行非零元的数目恰是的正度，第j列非零元的数目是，的负度。 邻接矩阵可以表示自环，但无法表示重边。 无向图的邻接矩阵是一个对称矩阵，例如图1.1]的邻接矩阵是 011117 0 01 1 A= 1101 0 0101 1011J 图1.11 1.2.2权矩阵 赋权图常用权矩阵A进行表示。其元素 w,(,）∈E。 a,= 0. 其它。 例如图1.5的权矩阵是 [0 3 62 41 3 0 4.20 A= 64.2 0 3 2 0 3 0 7 4 5 0 70 1.2.3 关联矩阵 关联矩阵表示结点与边之间的关联关系。 有向图G的关联矩阵B是n×m的矩阵，当给定结点和边的编号之后，其元素 1, e,r(4)∈E。 b=一1， e,=(ts,)∈E。 0 其它， 例如图1.12的关联矩阵是 6·
1 -1 1 0 0 0 0 0 0 ”…1 0 0 1 1 -1 0 0 0 1 0 -1 1 -1 0 B 0 0 0 0 0 0 1 0 0 -10 0 0 0 e P2 关联矩阵具有以下性质： 1.e 1.每列只有两个非零元：1和-1。 2.第i行非零元的数目恰是结点的度，其中1元的数门是d*(,)、一1元的数凡是 d(,)。 3.能够表示重边，但不能表示自环。 类似地，尤向图也有其关联矩阵B,但其中不含一1元素。 例如图1.13的关联矩阵是 V: 111100000 100011100 01000111 0 B= 001000011 000110001J e」e:e3e4 es eo e ea eg 当邻接矩阵和关联矩阵能够表示某个图G时，这种表示 图1.1 是唯一的，而且十分直规。但由于它们不能表示重边或自环，因此这种表示有其局限性。特 别在使用计算机对某个图G进行运算时，采用邻接矩阵或关联矩阵作为输入形式将占据 较大的存储空间并可能增加计算复杂度。因此，为克服这些缺陷，再介绍图的另外儿种常 用表示方法。 1.2.4边列表 边列表是对关联矩阵的列进行压缩的结果。它由两个维向量A和B组成，当对G 的结点和边分别编号之后，若=(，v,),则A()=i,B()=j,即A(k)存放第是条边 始点编号，B()存放其终点编号。如果G是赋权图，则再增加-个m维向量Z,若：的权 是U,则令Z(k)二w。例如图1.14的边列表示形式是 A:(4412224) B:(1]22433) 2 C: 4 Z:(5346724) 图1.11 ·7
类似地可以得到无向图的边列表，比如图1.15的边列表是 A:(111223) T B:(442434) Z:(534724) es 图1.1d 1.2.5正向表 正向表是对邻接矩阵的行进行压缩的结果。它的特点是将每个结点的直接后继集中 在起存放。有向图的正向表由一个(n+1)维向量A,一个m维向量B组成。当对G的 结点编号之后，A()表示结点，的第一个直接后继在B中的地址，B中存放这些后继结 点的编号，A(n+1)=m十1。如果G是赋权图，则再设晋一个m维向量Z,用以存放相应 的权值。例如图1.14的正向表是 A 12558 B2234311 z4627453 在正向表中存在下述关系： 1.d(u,)=A(i+1)-A(i) 2.A()= ) 1 3.从B(A())到B(A(i+1)-1)的任一个值，都是：的直接后继。· 由于无向图的边没有方向性，所以B中存放的是相应邻接点的编号，因而B和Z都 要扩充为2m维的向量。例如图1.15的正向表是 A147913 B442134241123 Z534427245374 1.2.6逆向表 与正向表相反，逆向表是对有向图邻接矩阵的列进行压缩的结果。它的特点是将每个 ·8
结点的直接前趋集在一起存放。例如图1.14的逆向表是、 A135?8 B 4412242 534624? 1.2.7邻接表 这是采用单链表结构表示一个图。对每个结点：用一个表结点表示。在这里表结点 的结构如下 。6c 它共分二：个域，邻接点域α中任放该结点的编号，数据域b中存放相应边的数值，链 域c中存放下一个表结点的地址指针，以图1.11为例.它的邻接表形式如下 24 -26白-3234T? 一34-15-13 其中Q()存放结点，的第一个直接后继表结点的地址指针。邻接表的特点是使用灵活， 比如要从图G中删去某杀边时，只要摘除对应的表结点就以实现；若要增加某条边，也 只需增加…个表结点，而不需要进行大的变动。 边列表、正向表和邻接表等都能表示重边，也能表示自环，也就是说，它们都能唯一表 示任意·个图。而且也都只占据较小的存储空何。邻接矩阵、关联矩阵、边列表、正向表、 逆向表之间都可以互相转换。为了直观起见，本书主要采用邻接矩阵和关联矩阵表示图 (,在描述某些算法时，有时也采用正向表等形式的数据结构。 习题 一 1.证明在9座丁厂之间，不可能每座工厂都只与其它3座工“有业务联系，也不可 能以有4座工与偶数个厂有业务联系。 2.简单图G中，如果m>号(a一1)(2)，证明G不有在孤立结点。 3.完全图的每边任给一个方向，称为有向完全图。证明在有向完全图中 d(,2=d（)2。 EV 4.三个量杯容量分别是8升、5升和3升，现8升的其杯装满了水，问怎样才能把水 分成2个4升，画出相应的图。 ·9·
5.6个人围成圆形就座，每个人恰好只与相邻者不认识，是否可以重新入座，使每个 人都与邻座认识？ 6.证明9个人中若非至少有4个人互相认识，则至少有3个人互相不认识。 7.判断1.7图是否同构？ (a) (b) 题图1.7 8.写出题1.7图(a)的邻接矩阵、关联矩阵，边列表及正向表。 9.试编写有向图G的邻接炬阵与关联矩阵，邻接矩阵与正向表，关联矩阵与边列表 之间互相转换的程序。 ·10·
