§21树与上树 令G=(VE)是一个图.对于v∈V,En={e(v),e(v),… e(()},即与v关联的边的集合·在v处的旋定义为o()= (e1(v),e2(),…,ep(v}()所确定的循环序·进而,图G的旋, 即g(G)={g()!vv∈V}.如果将每一边任意安排一个方向和 在每一节点处给定一个旋并且不同的边用不同的字母表示,则 在一个树T上可依如下方式确定一个旅行规则 旅行规则每当从E(T)中的一条边a达到节点v就在 T上沿着依此节点处的旋紧接着a的尚未离v向前旅行 过的边继续往前走, 如果选定节点v为起点,与e关联的…条边e0为始边、 按照旅行规则在事先给定的旋之下能走就走若将所通过的边 的代表字母记录下来并且根据走向与边的选定之方向相同或 相反分别赋与这个字母以1或-1作为幂,则旅行结束可得到 一个字,我们称之为T的一个码 引理211凡树的码皆多面形.且,这个多面形只有 个面 证令Tr是树T的一个码,首先,我们证Tr是T上 的一个迂.若不然,设终点为v1不等于.由定理1.32,进入 U1的次数比离开n1的次数多1.由旅行规则,v1不可能是终 点.然后,证每个字母恰在Tr中出现二次,因为T的每条边 皆割边和Tr是一个迁,故Tr每边必恰出现二次.最后,由 于导出子图T{E(r的连通性,Tr是一个仅有一个面的多面 形 引理21,2一个对T的码的基准图是T本身
第二章图中的树 设T是T的码Tr的基准图且T"≠T.由T的连通 性,有一边a∈E(m)\E(r")且在T上与节点t∈V(")关联 然,由旅行规则,第一条进入v的边也是最后离开v的边·这 就是说E(T")=E().与假设矛盾 令T为所有树的集合对于一个树T∈T,令Tr(红)为T 的所有码的集合 定理211ⅥT∈T,ⅥTr∈Tr(T),T(Tr)cP. 由上面二个引理,只要证T~BP即足,由于任何 树皆无圈,必有一个显节点v设a是那条与v1关联的边 则,有形式Tr=Aaa-1B~EAB.由T4,AB的基准圈仍为 树.由归纳假设,AB~BP.固然,当T的边数很小时,容 易验证,从而,即得定理. 定理2.1.2ⅥT∈T,S∈S,(S≠f)A(T∝S) 证由T1,对于T在曲面上的任一嵌入,它只能有一个 面.从而,它是T的一个码.且,这个码在等价~E的意义下 与T的旋的选择无关,由定理2I1,即得定理 如果T是图G=(VE)的一个支撑树,或者说G上的一 个树,则G的支撑子图T=(V,E\E(1)被称为G上的一个 上树.如果G本身是树,则它的上树只能是G的一个支撑孤 立子图 定理213在任何连通图上,总有一个树,从而,也有 个上树 如连通图G没有圈,由T.1,它本身就是一个树.否 则,我们可任选择一个圈,从G中去掉这个圈上的一条边得一
§21树与上树 29 个新图,如果它不再有圈,则再由T1,它就是一个树.如若 不然,用这个新图代替G,继续上述过程.由G的有限性,总 可求得G上的一个树 引理213令T是图G=(V,E)上的一个树,T*相应 T的上树、则对于T*上的任一条边,在T+e=(v,E(T)+e) 上恰有一个圈 证设e≈{u,).由T3,在T上恰有一条路P(x,v).从 而,P(u,)+e恰形成一个圈·即为引理 对于图G=(Vv,E),若X≌V, Ex={(t,y)a∈X,v∈x,(u,U)∈E}, 则,C”=C“(X)=GEx!被称为G的一个上循环圈当X=0 或X=V时,C"(X)称为空的,也记为的.如果一个上循环没 有非空真子图仍是上循环,则称为上圈.自然,任何上循环都 含有灬个上圈. 引理21.4令T是G上的一个树,T*为相应T的上 树,則,对于T的任何一边e,在T*+e=(VE(r“)+e)中恰 有一个上圈 证设e=(u,v).因为任何一个上圈都有T中的一条 边.故,在T中不含任何一个上圈.又由于T的每一条边均 为T的割边,则T-e至少有二个连通片.令A是含的连通 片的节点集.容易看出,C(A)包含在T*+e中.如果还有 个上循环C*(B)在T*+e之中,则C(B)定包含.然,这时 C(AUB\A∩B包含T中的一个上圈.因T上无上圈,故 只能C“(A)=C(B)
30 第二章图中的树 由引理21.3,我们可以称由上树的一边与相应的树所确定 的圈为基本圈.相仿地,由引理2.1.4,那些由一条树上的边与 上树所确定的上圈为基本上圈.进而,还可以看出,不管怎样 取图上的树,基本圈的数目均为E-v+1,即上树的度,或称基 圈数,也称Bett数,记为(C).相仿地,基本上圈的数目为上 基圈数,记为a(G).事实上,a(G)=-1,即G上之树的度 定理2,14连通图G的基本群为 丌1(G)={a1,a2;…,aB (211) 证由定理2.13,令T是G上的一个树.由定理212 知,凡树均可收缩到一个点.由引理214,收缩T而得到的图 仅由B(G)个环组成,记它们为a1,a2,…,a8,因此,任何迂(或 者在拓扑学中称为闭路)均可由它们所生成这就是定理的结 论 从§1.4中关于曲面的基本群的讨论,也许人们会想到图 在曲面上的可嵌入性假若一个图可以看作是一个树与一个圈 合成的。其中的树已嵌入到平面上了且伴随一个码,这个圈可 按照在码上出现之次序连接树的所有显节点.则称它为 Halin 图.这个圈被称为它的外边界.当然,所有 Halin图皆为平面 的·而且,还能证明任何Hain图都可嵌入到亏格为q=B(G 的不可定向曲面上,事实上,在图211中(a)所示的图(更确 切地, Halin图)有(b)所示的嵌入可以引伸到一般情形.这个 嵌入只有一个面,即 acyabaaBc-b-B 容易验证,它是不可定向的由Euer示性数断定为曲面Qq,q=
21树与上树 B(G,上的一个嵌入,这个嵌入的对偶是 aay, acb, bBa, c yP). (2.12) 下一节将进一步讨论 图21 b 图21.2 相仿地,也可以论证任何 Halin图均可嵌入到亏格为p LG(G)/2的可定向曲面P上,这里,也提供一个例子·在图 212中,(a)所示的图有(b)所示的嵌入·它也可引伸到一般 Halin图的情形,在全书中,对于任一个实数r,我们总用|x