第二章图中的树 表示不大于x的最大整数和「x为不小于x的最小整数.分别 称它们为下整数(或地板)和上整数(或天板) 因为可以验证这个嵌入是可定向的并且只有一个面 acaBedal8bae-1y8-c-b-lx-1B-ld (213) 由 Euler示性数,它确是亏格为p=|(G)/2」的可定向曲面 P上的一个嵌入·其对偶为 ae-d, a-lcb-1 c-a6,a^ad-,-e?) §22确向树与确向上树 对于图G上的一个树,或者说对于G的一个支撑树T 如果存在对G的边的定向使得任一基本圈上的边均有相同的 走向或者说为有向圈,或回路,则称η为一个准确向树.若 个上树T*使G的边有一种定向具有性质:每一个基本上圈在 T中的边全走向相同而与它在T上的那条边走向不同,也称 之为有向上圈,则称之为准确向上树.当然,既不是所有的树 皆准确向树,也不是所有上树皆准确向上树、凡提及准确向树 或准确向上树均指它们与所在的图已确定了边的方向 定理221在图G=(VE)上的一个树T为准确向树 当且仅当与它相应的上树T为准确向上树 证由于T为G上的一个准确向树,存在G上的边的定 向使得所有的基本圈均为有向圈设C是由e∈E(m)与T形 成的那个基本上圈和A,B为T-e中的那二个连通片使边e的 方向为从A到B.则由引理213,在C中的所有上树边皆从 B到A.从而,T是一个准确向上树.反之,设C==ee2…e…
§22确向树与确向上树 33 e=(t,v),e4=(v;-1,v;),1≤i≤8,t=to,=t,为由e∈E(T*) 与T形成的那个基本圈.由引理214,所有上圈C*,1≤i≤8, 均含e.由于T*为准确向上树,在Ct,中e的方向与e的 方向不伺.或者说e1=<v,v1x当e=t,vx.同样理由, e2=<U1,v2x,…,es=<v3-1,ux,从而,在基本圈上所有的边 皆同向.这就是说是一个准确向树 这个定理使我们总可以只讨论准确向树.如果一个节点v 在准确向树上没有进入的边,则v称为T的源反之,若一个 节点只有进入的边,则称它为汇,一个准确向树可以有两个以 上的源.若一个准确向树只有一个源,则称它为确向树.一个 上树,若它所确定的树是确向树,则称之为确向上树 引理221一个准确向树T在图G上是一个确向树, 当且仅当它有v-1个节点使得每个均只有一条进入的边 证由21中的T3,必要性是显然的.反之,由21中 的T1,那个仅有的例外节点是T的唯一的源.这就得到了充 分性 引理2.22若T是图G上的一个确向树,则对于任何 H≤G,T=T∩H是H上的一个确向树当且仅当Th是H上 的一个树 证由于确向树本身是树,必要性显然,反之,由于H 中对于Th的基本圈也为G对T的基本圈和Th是一个树,即 可得充分性 引|理223确向树T的一个节点是汇当且仅当是一人 显节点仅当源为显节点时对于充分性例外 证因为确向树T只有一个源,由21中的T.3,任何
34 第二章图中的树 节点有且仅有一条有向路由源指向它.故,每一个显节点(除 源也为显节点外)均必为汇.这就是充分性.反之,若有一个 节点v,它是T的汇但不是显节点则由T有唯一的源,必有 两条有向路从源指向v.与921中的T3矛盾.从而,只能必 要性成立 如果将一个准确向树T的所有边皆反向,则所得的有向 树称为T的反向形.相仿地,可知一个准确向上树的反向形的 意义 定理222个准确向树T的反向形是准确向树和它 是一个确向树当且仅当T只有一个汇.一个确向树T的反向 形是确向槓当且仅当T本身是一条 Hamilton路. 证由于有向图的反向形仍是有向圈,第一个说法的前 半部是对的.由于在T的反向形中,一个节点是源当且仅当 它在T中是汇.其后半部亦真因为路本身也是树,则有第二 个说法的充分性,由引理223,此确向树T只有二个显节点 由21中的Tr.3,即得必要性 为了在一个图上求确向树,我们要引进反射规则和调整 §21中的旅行规则 反射规则每当第一次沿一条边达到一个已访问过的节 点,就沿此边返回并将此边标为反射的 调旅规则即§21中的旅行规则,只要每到一个节点在 此节点的旋中不计反射边 对于一个图G=(VE),如果旋以(G)已经给定,则可以根 据上面的两条规则用如下的过程沿G的边旅行
§22确向树与确向上树 35 确向过程选择节点v作为始点,与v关联的一条边 eo作为始边、只要达到一个节点v,先用反射规则(如可 能)再用调旅规则 令Dr为在图G上用确向过程所得的字.在这个字中,每 一个字母表示G的条边.一个字母的幂为1(总是略之)或 1分别表示第一次或第二次通过这个字母所代表的边.D是 由Dr中的所有非反射边组成的集合 引理22.4在Dr中的所有非反射边形成G上尔一个 树 证由于注意到每当必需反射时,就在G中发现一个含 有这个反射边的圈.那个由所有Dr中非反射边在G中所导 出的子图必连通且无圈.从而,由82.1中1,G(D)是一个 树 引理2.25Dr是一个多面形且Dr~E!P 证当在Dr中无反射边时,由引理224和定理21.1, 引理为真假若a是一个反射边,则Dr具有形式:Aa-1B. 然,由紅I5中的E1.0,Dr~BAB和由归纳假设,AB~FP 即得引理 定理223个图G=(VE)有一个确向树,当且仅当 G是连通的 证由于确向树本身是G的支撑树,必要性显然.反之, 由引理224和注意到在每个节点处,只要依确向过程通过与 它关联的一边则与它关联的每一边都必通过二次,从G的连 通性即得所有非反射边的导出子图就是G上的一个确向树
36 第二章图中的树 这就是充分性 由引理224-5和定理2.2.3,我们可以记Tod=G(D)为G 的确向树和Tod*为由Tod所确定的确向上树,令Or和Om分 别为确向过程在G上所得的所有反射边和所有非反射边的集 合·则E(Tod)=Om和E(Tod“)=Or.以后,我们不区别边和 代表它的字母.多面形D被称为G的确向码.由引理213-4, Tod“的度为=B(G)=e-+1和Tod的度为a=a(G)=v-1 这就允许我们记Or={,γ,,"}和On={b1,b2…,b}对 于∈Or,可记 Dr= AoabaryB6-a-Ap 其中,a,,b,γ∈E,v∈V.令 PPa, (Dr)= AoabAYB-1rb -a- Ao (221) 称这种运算为在v处的反射约化,在第十二章中我们将会看到 它实际上是一种叉帽容易验证,它是不可交换的.在合成运 算中要考虑到次序.进而,令 I 9y, Dr, i=1, 2, (222) 在Dr中,与反射边关联的显节点被称为Dr的反射节点 引理228在(222)中确定的Dr,i=0,1,2,……,月,是 个多边形,它有一个面,E-1+1个节点和∈条边 证当i=0时,由引理225,已经知道Dr~EP.因 此,有一个面,6+1个节点和c条边.进而,由于反射约化保 持面数和边数不变而且每次减少一个反射节点,即可得引理