第一章图的基本概念 (b) 图1-8 1adj)时就把u和v连接起来所得到的图G称为G1和G2的积图，记 为G=G×G2,其中出adju,表示u:和v,邻接，如图1-9中所示. 收” (14)(，)(w G,×G 图1-9 定义4设G=(V,E),G2=(V2,E2),对点集V=V×V2中的任 意两个点u=(山，山)和v=(,欧)，当(adj)或（出=和adjh) 时就把u和v连接起来所得到的图G称为G:与G,的合成图，记为G= G[G2]. 对于图1-9中的两个图G和G2,两种合成图G[G,]和G,[G]都 画在图1-10中，它们显然不同构. 若G的点数和边数为m,m1,G2的点数和边数为2，m2,则经上述4 种图的运算，图的点数和边数列在表1-1中
§1,2子图与图的运算 G[G] G[G] 图1-10 表1~1图的二元运算 运算 点的数目 边的数目 并GUG 十应 1十m2 联GVG 用十应 m十m十州 积GXG2 h 指m十m 合成G[G】 m十m 一族特别重要的图称为方体，它用积来定义最为自然.n方体Q.递 推地定义为Q1=K2,Q,=K:×Q-1.于是Q有2个点，它的点可以用 a1a2.an来标定，其中a:是0或者1.如果Q的两个点的二进制表示式 中只有一处不同，则它们邻接.图1-11中画出了已经经过适当标定的2 方体与3方体 100 10 C2=K,×K2 2,=K2×KXK2 图1-11 将G的一个任意点与G2的一个任意点等同起来只产生惟一的图 (同构图视为同一图)，将这个图记为G·G2.例如，在图1-12中的H, H2就是这样运算来的
10 第一章图的基本概念 H=K'K H=KK 图1-12 §1.3路与图的连通性 G的一条途径（或通道或通路）是指一个有限非空序列w= 2"evs,它的项交替地为顶点和边，使得对1≤k,&的端点是-1和 称w是从到4的一条途径，或一条(，4)途径.顶点和4分别称 为w的起点和终点，而，M-称为它的内部顶点.整数k称为w的 长.在简单图中，途径可简单地由其顶点序列来表示，即w=60边. 若途径w的边e1,e2,.,ek互不相同，则w称为迹；这时w的长恰好 是边数.又若途径心的顶点v。,.,4也互不相同，则心称为路。 G的两个顶点u和v称为连通的，如果在G中存在(u,v)路.规定u 和u是连通的.如果对G中每一对顶点u,v都有一条(u,)路，则称G为 连通图，否则称为非连通图.连通是顶点集V上的一个等价关系，于是可 将V划分为一些等价类.设V的所有不同的等价类为V1,V2,.,V,这 样，两个顶点u和口是连通的当且仅当它们属于同一子集V,称子图 GV],G[V],.,GV]为G的连通分支，简称分支或支.记G的分支 个数为w(G).于是G是连通图当且仅当w(G)=1. 定理7若图G是不连通的，则G是连通图. 证明设u,v是G的任意两个顶点.若u和v在G中不邻接，则在 G中它们邻接.若u和v在G中邻接，它们属于G的同一分支.在另一个 分支中有一点w,在C冲u和v均与w邻接，即uu心是一条通道. 称一条途径是闭的，如果它有正的长且起点和终点相同.闭迹也称 为回路。若一条闭迹的起点和内部顶点互不相同，则称它为圈。长为k的 圈称为k圈；按k是奇数还是偶数，称k圈是奇圈和偶圈.3圈常称为三 角形.联结u和v中长度最短的途径的长度，称为4与v的距离，记为 d(u,v).称d(G)=max{d(u,)lu,o∈V)为G的直径.利用圈的概念， 可以给出偶图的一个特征。 定理8一个图是偶图当且仅当它不包含奇圈。 证明设G是具有二分类(X,Y)的偶图，并且C=w功.4vo是G
§1.4最短路及其算法 11 的一个圈.不失一般性，可假定6∈X.一般说来，2：∈X,且2+1∈Y. 又因为%∈X,所以u∈Y.由此即得C是偶圈. 显然仅对连通图证明其逆命题就够了.设G是不包含奇圈的连通 图.任选一个顶点u且定义V的一个分类(X,Y)如下： X={xd(u,x)是偶数，x∈V(G)}, Y={yd(u,y)是奇数，y∈V(G). 现在证明(X,Y)是G的一个二分类.假设v和w是X的两个顶点，P是 最短的(u,)路，Q是最短的(u,w)路，以记P和Q的最后一个公共顶 点.因P和Q是最短路，P和Q二者的(u,山)节也是最短的(u,)路， 故长相同.现因P和Q的长都是偶数，所以P的（山，v)节P和Q的 (w1w)节Q必有相同的奇偶性.由此推出(v,w)路PQ长为偶数. 若v和w相连，则PQw就是一个奇圈，与假设矛盾，故X中任意两 个顶点均不相邻；类似地，Y中任意两个顶点也不相邻. 0 §1.4最短路及其算法 对G的每一条边e,可赋以一个实数w(e),称为e的权.G连同它边 上的权称为赋权图.赋权图通常出现在图论的应用中.例如在友谊图中， 权可以表示友谊的深度；在通讯网中，权可以表示各种通讯线路的建设或 维修费用. 若H是赋权图的一个子图，则H的权W(H)=∑(e).赋权图 EE武HD 中路P的长定义为W(P),距离d(u,)仍定义为最短(u,)路的长.许 多最优化问题都可转化为要在一个赋权图中找出某类具有最小（或最大） 权的子图，其中之一就是最短路问题：给出一个连接各城镇的铁路网络， 在这个网络的两个指定城镇之间试确定一条最短路线。这就是要在一个 赋权图的两个指定顶点a和b之间找出一条最短(a,b)路。 下面所叙述的算法是Dantjig发现的，称为标号法.这个算法不仅找 到了最短的(a,b)路，而且给出了从a到G的所有其他顶点的最短路.算 法中l(e)表示边e的权，其基本步骤如下： 算法1 步骤1记a=a1,t(a1)=0,A={a1,T=财； 步骤2若已得到A,={a1,a2,.,ai},且对1≤n≤i,已知t(an),对 每一个an∈A,求一点 b∈N(an)-A:=B
々 第一章图的基本概念 使 (ab)=minl(av), 其中N(am)是与a.邻接的所有的点的集合，又称为点an的邻域或邻集； 步骤3设有m,1≤m,≤i,而b使t(am)十l(amb0)取最小值，令 b=am,t(a:t1)=t(am)+l(amamt),Tit=T;U(amait}; 步骤4若a+1=b,停止.否则，记A+1=A:U{a+1}回到步骤2. 不难证明，任一T,导出的子图是树（一个没有圈的连通图，具体定义 参看第二章)，从而其中有惟一的路联结a与a,其长度就是t(a,).若 b=a,则t(a)就是T。导出的子图中惟一联结a与b的路的长度，为了 说明t(a:)就是赋权图G中a到ak的最短路，我们来证明下列结果. 定理9算法1中的函数t(a,)给出了a与a:的距离. 证明对i用数学归纳法.=1时显然成立.若对所有j,1≤<i, t(a)=d(a,a,)(表a到aj的距离).令P=hh.va,6=a,u=a是 联结a与a:的一条最短路，从而d=d(a,a,),令n是P中第一个不在 A,-1中的点.由于aA-1,故这样的点.存在.又因h∈A-1知n>1, 设u,-1=a4,则有≤i-l.记P中由a到vn的一段的长度为l,a到v-l 的一段的长度为l4.由归纳法假设，有l≥t(ae),且 d(a,ai)=d=l=h+l(v-1,v)>t(a)+l(a:,b-D) t(am-)+l(am-a:)=t(a:), 其中am-由算法1的第三步得到，l≤m-1≤i-1.又由于存在一条长度 为t(a:)联结的a与a:的路，可知 t(ai)d(a,a). 联合此两个不等式，即得 t(a;)=d(a,a;). 按归纳法原理，知定理成立 例求图1-13中a到b的最 短路。 解下面解法中①，②，③表示 算法1中的步骤1,2,3. (1)①A={a},t(a)=0, T1=0; (2)②b=； (3)③m=1,a2=,t()= t(a)+l(a)=l(最小)