（应用数学专业论文）用8长圈c8最大填充和最小覆盖完全二部图kmn.pdf

器交换机和复用器等电子设备的处理速度造成的瓶颈，波长带宽与一个典型业务连接之 间的巨大差距也开始成为一个新的热点流量疏导技术的出现为解决这些问题提供了一 种有效途径流量疏导研究的是如何将不犀速率不同类型的低速照务打包成高速数据流， 复用到一个波长上，用来实现某种设计目的的过程在由s o n e t ，w d m 构成的网络中，每 一波长霹通过时分复用疆d 艇) 方式承载很多低速业务流。由于上鼹或下路一个低速韭务 只能在该业务的两个终端节点上的分插复用器( a d m ) 中完成，且对每一个在节点处匕下 路的波长都需要在该节点放置一个a d m 对攘应的业务进行处理。若每一波长都在每个 节点处下路，则需要大量的a d m 为减少网络节点的信息处理量及a d m 的用量，可以厢 波长上下路复用器( w 加m ) 有选择地下路一些波长，而将未携带与该节点业务有关的波 长进行光学直逶。流量疏导的目的之一就是确定每个波长所携带的低速监务流，以减少波 长和a d m 的用量 业务疏导国a 懋eg r o o m n 珐邵通过有效的复用、解复糟及交换处理，将低速率酌监务 流汇聚到高容量的光路，以提高网络的资源利用率【5 - 1 0 | 根据网络的型有很多变量需要 考虑，如嫠蔫的容量襄最优讫的参数，这些参数孳| 起了很多有趣的设计闻题( 如匿分怨x 假设用一个具有n 个点有向图g ( 在大多数情况下是一个对称有向图) 来表示一个光 澍络，铡如文表拳一个单离塔或嚷表示一个双良环绘定一个业务矩阵，它是用多重 有向图，来表示连通要求族c 从点i 到点歹的要求数确定了从点t 到点歹的弧) 当从点t 到点j 恰好存在一个要求时，那么j j 。满题从每个点t 到每个点j ；的要求是由g 中 分配个波长的路径组成。若一个要求在一个波长上只能使用宽带的l e 通过它的路径， 则此c 称为疏导率或者说，对于g 中每一条弧e 和每一个波长叫，至多存在c 个具有波 长甾包含弧e 的有向路。 在9 0 年代，人们研究了如何降低网络中的波长数的问题与此同日寸，每个波长的带宽 ( 王og b i 魄) ，每个纤维波长数( 王0 耪每个电缆纾维数( 王o o ) 已经分熊因此将一个 波长网的操作花费转变为最终的设备的花费：纤维，光交叉连接器，插入，合并多路复用器 ( a d m ) 。例如，在一个光鼹络的节点处安装一个a d 艳使用这整波长传送一个在这 个节点被插入或合并的要求现在的目标是降低网络中的a d m 总数，这是一个具有挑战 性的问题 对于给定的疏导率c ，利用图论和组合设计理论已经得到了最优的构造【5 】特别地， 对于c l 时，每个子图都是l 条边，没有降低成本的可能当c = 2 时，每个子图至多包 含2 条邈由于线图是欧拉图，在每个欧拉圈上用连续的点可以降低成本，因此，最 低成本是f 掣 【6 】对于疏导率c 一3 m ，c 一4 8 一，c 一5 1 0 | ，c 一6 【6 】，c 曼业 8 】的 环上的渡务疏导阕遂，已：经解决在上述基础上，我在本部分中主要研究了无辩w d 醚环 2 且由定理2 7 的情形一知岛可以分解吨n 尬因此，。的一个最大瓯- 填充有 余边图l = m 1u ，f = m ，填充数p = 竿可得s = 6 ，覆盖数c = 型等世 情形二：当m 三7 ( m o d8 ) ，n 三l ( m o d8 ) 时，可得南= 0 现在考虑，n = ( ，n 尬) u ( 吨。m 2 ) u 尬u ，其中心，。尬的二部集足 1 1 ，2 l ，几1 ) 和，舰是 。的一个完美匹配，一。，n 的二部集是 ( n + 1 ) l ，( n + 2 ) l ，m 1 ) 和k ， 如定理2 7 的情形三所述足吨。的一个m 一礼条边集由引理2 8 知，n 蛳可以被 分解成g ，且由定理2 7 的情形三知g 可以分解喝。因此，n 的一个最大 g 填充有余边图l = 舰u 尬，f = m ，填充数p = 宁可得s = o ，覆盖数c = 型产 情形三：当m 三5 ( m o d8 ) ，礼三1 ( m o d8 ) 时，可得七= 0 现在考虑，n = ( ，n 舰) u ( 吨。) u 舰u ，其中，。尬的二部集是 1 1 ，2 l ，一，礼1 ) 和，舰 足。的一个完美匹配，一。一的二部集是【m + 1 ) 1 ，( n + 2 ) 1 ，m 1 ) 和， 如定理2 7 的情形一所述是一。，。的一个m 一咒条边集由引理2 8 知g 可以分解 ，n 尬，且由定理2 7 的情形一知g 可以分解一 因此，n 的一个最大g _ 填充有余边图l = mu 尬，c = m ，填充数p = 平可得s = 2 ，覆盖数c = 型专啦 情形四：当仇三3 ( m o d8 ) ，n 兰1 ( m o d8 ) 时，可得尼= o 下面分二类来构造 第一类：当m = n + 2 且礼= 9 时，构造k 1 1 ，9 的8 长圈集：“n ，i 2 ，( i + 2 ) l ，( i + 4 ) 2 ， 0 + 3 ) l ，( i + 7 ) 2 ，( i + 8 ) l ，( i + 5 ) 2 】， 0 + 4 ) l ，u + 4 ) 2 ，o + 6 ) l ，0 + 8 ) 2 ，( 歹+ 7 ) 1 ，0 + 2 ) 2 ， 0 + 9 ) 1 ，歹2 ， 2 1 ，8 2 ，8 l ，4 2 ，3 1 ，6 2 ，1 1 1 ，3 2 】，【4 l 3 2 ，6 1 ，9 2 ，1 1 1 ，5 2 ，8 1 ，7 2 】， 1 1 4 2 ，2 1 ，5 2 ，9 1 ，9 2 ，3 1 ， 7 2 】，【7 1 ，4 2 ，5 1 ，8 2 ，1 0 1 ，6 2 ，2 1 ，1 2 li = 1 ，2 ，3 ，4 ；歹= 1 ，2 ，3 ) ，其余边图l ，e ( l ) = ( 1 1 ，8 2 ) ，( 2 1 ， 9 2 ) ，( 3 1 ，2 2 ) ，( 4 1 ，1 2 ) ，( 5 1 ，2 2 ) ，( 6 1 ，5 2 ) ，( 7 1 ，6 2 ) ，( 8 1 ，2 2 ) ，( 9 1 ，3 2 ) ，( 1 0 l ，4 2 ) ，( 1 1 1 ，7 2 ) 】，且f = 1 1 ， 填充数p = 1 1 可得s = 2 ，覆盖数c = 1 4 ，构造e ( l ) u e ( r ) 的8 长圈集： 1 1 ，9 2 ，2 l ，4 2 ，3 1 ， 2 2 ，5 l ，8 2 】， 4 1 5 2 ，6 l ，6 2 ，7 1 ，2 2 ，8 1 ，1 2 】，【9 1 ，4 2 ，1 0 1 ，7 2 ，1 1 1 ，1 2 ，1 1 ，3 2 】- ，其中e ( r ) = ( 1 1 ，9 2 ) ， ( 2 1 ，4 2 ) ，( 3 1 ，4 2 ) ，( 4 1 ，5 2 ) ，( 5 1 ，8 2 ) ，( 6 l ，6 2 ) ，( 7 1 ，2 2 ) ，( 9 1 ，4 2 ) ，( 1 0 1 ，7 2 ) ，( 1 1 l ，1 2 ) ，( 1 1 ，3 2 ) ， ( 1 1 ，1 2 ) ，( 8 l ，1 2 ) ) 当m = n + 2 且死 9 日寸，下面考虑，n = ( 一1 0 ，。一8 尬) u ( 硒o ，n 一8 ) u ( - 1 0 8 坞) u 甄o ，8 u 尬u 尬u 尬，其中- l o ，棚尬的二部集是 1 1 l ，1 2 ，m 1 ) 和【9 2 ，1 0 2 ，佗2 ) ，尬是一l o ，。一8 的一个完美匹配，e ( 尬) = ( ( 3 + i ) 1 ，( i 一2 ) 2 ) l i = 1 1 ，1 2 ，m 一3 ) u ( n l ，( n 一2 ) 2 ) ，( 1 2 1 ，( n 一1 ) 2 ) ，( 1 3 l ，礼2 ) 】，k l o ，。一8 的二部集是 1 1 ，2 l ，1 0 1 ) 和 9 2 ，1 0 2 ，礼2 ，尥如定理2 7 的情形三所述是尬o ，n 一8 的一个1 0 条 边集，e ( ) = ( 1 1 ，1 1 2 ) ，( 2 l ，1 3 2 ) ，( 3 l ，1 0 2 ) ，( 4 1 ，1 3 2 ) ，( 5 1 ，1 1 2 ) ，( 6 l ，1 0 2 ) ，( 7 l ，1 2 2 ) ，( 8 1 ，1 2 2 ) ， ( 9 l ，1 0 2 ) ，( 1 0 l ，1 0 2 ) 】，一l o ，8 的二部集足【1 1 l ，1 2 1 ，m 1 ) 和 1 2 ，2 2 ，8 2 ，如 定理2 7 的情形一所述是一l o 8 的一个8 条边集，e ( ) = ( 1 4 l ，1 2 ) ，( 1 4 1 ，2 2 ) ，( 1 2 1 ，3 2 ) ， 1 3 ( 1 2 l ，4 2 ) ，( 1 4 1 ，5 2 ) ，( 1 4 1 ，6 2 ) ，( 1 2 1 ，7 2 ) ，( 1 2 l ，8 2 ) ) ，硒o ，8 的二部集是( 1 1 ，2 l ，1 0 1 ) 和【1 2 ， 2 2 ，8 2 ) 由引理2 8 知国可以分解一l o 。8 尬，由定理2 7 的情形三和情形一 知g 可以分解k 1 0 ，。一8 如和k 。一l o ，8 慨下面构造k l o ，8um jum j 的8 长圈集： 7 1 ，2 2 ，4 1 ，4 2 ，5 l ，6 2 ，1 0 l ，1 2 】，【1 l ，8 2 ，3 1 ，3 2 ，8 1 ，4 2 ，2 l ，5 2 ，【1 1 ，3 2 ，4 l ，6 2 ，9 l ，7 2 ，6 l ，2 2 】， 5 l ，5 2 ， 7 1 ，4 2 ，1 0 l ，2 2 ，9 l ，1 2 】， 2 1 ，2 2 ，3 1 ，4 2 ，6 1 ，8 2 ，8 l ，7 2 】， 1 1 ，1 2 ，2 l ，3 2 ，5 l ，7 2 ，7 1 ，6 2 】， 3 l ，1 2 ，4 1 ，8 2 ，1 0 1 ， 1 0 2 ，9 1 ，5 2 】， 6 1 ，3 2 ，7 1 ，1 2 2 ，8 l ，2 2 ，1 4 1 ，6 2 】， 3 1 ，1 0 2 ，6 1 ，1 2 ，1 4 1 ，5 2 ，8 1 ，6 2 】， 2 l ，1 3 2 ，4 l ，7 2 ，1 2 1 ，4 2 ， 9 1 ，8 2 ，【1 1 ，1 1 2 ，5 l ，8 2 ，1 2 1 ，3 2 ，1 0 1 ，7 2 】) ，其余边图l l 的边集足e ( l 1 ) = ( 1 l ，4 2 ) ，( 2 1 ，6 2 ) ，( 3 l ， 7 2 ) ，( 4 l ，5 2 ) ，( 5 1 ，2 2 ) ，( 6 1 ，5 2 ) ，( 7 l ，8 2 ) ，( 8 1 1 2 ) ，( 9 1 ，3 2 ) ，( 1 0 l ，5 2 ) ) 因此，n 的一个最大 g 填充有余边图l = 舰ul l ，其中f = m ，填充数p = 旦2 弓产可得s = 4 ，覆盖数 c = 幽乎垒，构造e ( l ) ue ( r ) 的8 长圈集：“( 4 歹+ 1 4 ) 1 ，( 句+ 1 0 ) 2 ，( 勺+ 1 5 ) 1 ，( 锄+ 1 1 ) 2 ， ( 句+ 1 6 ) 1 ，( 句+ 1 2 ) 2 ，( 句+ 1 7 ) 1 ，( 句+ 9 ) 2 】| 歹= o ，l ，2 t 一4 ) u “( m 一1 ) l ，( 亿一3 ) 2 ， 仇l ，( 佗一2 ) 2 ，1 1 1 ，( 竹一1 ) 2 ，1 2 l ，( n 一4 ) 2 ， 1 3 1 ，4 2 ，1 1 ，6 2 ，2 l ，7 2 ，3 l ，礼2 】，【4 1 ，2 2 ，5 1 ，8 2 ，7 l ，4 2 ，6 l ， 5 2 ， 8 1 ，3 2 ，9 1 ，5 2 ，1 0 l ，2 2 ，1 1 1 ，1 2 】- ，其中e ( r ) = ( ( 4 歹+ i + 1 4 ) 1 ，( 句+ i + 1 0 ) 2 ) ，( ( 句+ 1 7 ) 1 ， ( 句+ 9 ) 2 ) ii = 0 ，1 ，2 ；歹= o ，1 ，2 t 一4 ) u 【( ( m 一1 ) 1 ，( n 一3 ) 2 ) ，( m 1 ，( n 一2 ) 2 ) ，( 1 1 1 ， ( n 一1 ) 2 ) ，( 1 2 1 ，( 礼一4 ) 2 ) ，( 1 3 1 ，4 2 ) ，( 1 l ，6 2 ) ，( 2 1 ，7 2 ) ，( 3 1 ，n 2 ) ，( 4 1 ，2 2 ) ，( 5 l ，8 2 ) ，( 7 l ，4 2 ) ，( 6 l ，4 2 ) ， ( 8 l ，3 2 ) ，( 9 1 ，5 2 ) ，( 1 0 l ，2 2 ) ，( 1 1 1 ，2 2 ) ，( 1 1 1 ，1 2 ) ) 第二类：当仇 他+ 2 时，考虑，。= ( ，。尬) u ( 吨。) u 尬u ，其中 ，。尬的二部集是 1 l ，2 1 ，钆1 】和k ，舰是，。的一个完美匹配，一n ，n 的 二部集是 ( 他+ 1 ) 1 ，( n + 2 ) l ，m 1 ) 和k ，如定理2 7 的情形三所述是一n ，n 的一 个m 一礼条边集由引理2 8 知g 可以分解，。尬，且由定理2 7 的情形三知魄可以 分解k 。一” 毛因此，。的一个最大酝- 填充有余边图l = mu 乞，2 = m ，填充 数p = 竿可得s = 4 ，覆盖数c = 业专出 情形五：当m 三7 ( m o d8 ) ，n 三7 ( m o d8 ) 日寸可得后= 2 现在考虑，n = ( k ，n 尬) u ( 叱。) u 尬u ，其中，n 尬的二部集是 l l ，2 l ，一，n 1 ) 和k ，舰 如引理2 9 的情形一所述是，。的一个他+ 2 条边集，j 岛一叩 如的二部集是 ( n + 1 ) 1 ，( n + 2 ) 1 ，仇1 ) 和k ，如定理2 7 的情形二所述是 一n ，n 的一个m 一亿条边 集由引理2 9 的情形一知g 可以分解。n 舰，且由定理2 7 的情形二知岛可以分解 西n n ，n 如因此，。的一个最大g 一填充有余边图l = l 矗u 肘j ，f = m + 2 ，填充 数p = 婴铲可得s = o ，覆盖数c = 芈 情形六：当m 兰5 ( m o d8 ) ，n 三7 ( m o d8 ) 时，可得后= 6 现在考虑k n 。n = ( ，n 尬) u ( 吨n 尬) u 尬u ，其中，。尬的二部集是 1 1 ，2 1 i 一，n 1 和k ，舰如 引理2 9 的情形一所述是，n 的个n + 2 条边集，一n ，n 尬的二部集是( m + 1 ) 1 ， 1 4 + 2 ) 1 ，m 1 】，和，如定理2 7 的情形四所述足一。，。的一个m 一_ n + 4 条边 集由引理2 9 的情形一知g 可以分解。尬，且由定理2 7 的情形四知g 可以分解 一n 。n 尬因此，。的一个最大g - 填充有余边图l = 舰u 尬，f = m + 6 ，填充数 p = 型号业可得s = 6 ，覆盖数c = 幽警业 情形七：当m 三3 ( m o d8 ) ，礼三7 ( m o d8 ) 时，可得惫= 2 现在考虑，。= ( ，。蝇) u ( 吨。) u 尬u ，其中，。尬的二部集足 1 1 ，2 1 7 ，n l 】和k ，尬如引 理2 9 的情形一所述是。的一个几+ 2 条边集，吨n 的二部集足 ( n + 1 ) 1 ， + 2 ) 1 ，m 1 】- 和k ，尬如定理2 7 的情形二所述是 一。，。的一个m 一几条边集 由引理2 9 的情形一知g 可以分解，。舰，且由定理2 7 的情形二知g 可以分解 一。，n 尬因此，。的一个最大g - 填充有余边图l = 尬u 尬，f = m + 2 ，填充数 p = 型号遭可得s = 4 ，覆盖数c = 幽：警出 情形八：当m 三1 ( m o d8 ) ，几三7 ( m o d8 ) 时，可得后= 6 下面分二类来构造 第一类：当m = n + 2 且n = 7 时，构造，7 的8 长圈集：“i l ，i 2 ，0 + 2 ) 1 ，( i + 3 ) 2 ， ( i + 5 ) 1 ，( i + 6 ) 2 ，( i + 7 ) l ，( i + 2 ) 2 ，【2 1 ，3 2 ，4 1 ，1 2 ，6 l ，5 2 ，9 1 ，7 2 】，【2 1 ，1 2 ，8 1 ，4 2 ，4 l ，7 2 ，5 1 ，5 2 】，【1 l ，4 2 ， 5 1 ，2 2 ，7 l ，3 2 ，9 1 ，6 2 】ii = 1 ，2 ，3 ，其余边图l 的边集足e ( l ) = ( 1 1 ，7 2 ) ，( 2 1 ，6 2 ) ，( 3 1 ，2 2 ) ，( 3 1 ， 6 2 ) ，( 3 1 ，7 2 ) ，( 4 1 ，6 2 ) ，( 5 1 ，1 2 ) ，( 6 l ，2 2 ) ，( 6 1 ，3 2 ) ，( 6 1 ，6 2 ) ，( 7 1 ，4 2 ) ，( 7 l ，6 2 ) ，( 7 1 ，7 2 ) ，( 8 l ，5 2 ) ，( 9 1 ， 2 2 ) ，且z = 1 5 ，填充数p = 6 可得s = 0 ，覆盖数c = 8 ，构造e ( l ) ue ( 兄) 的8 长圈 集： 【1 1 ，7 2 ，3 1 ，2 2 ，6 1 ，6 2 ，7 l ，4 2 】， 3 l ，3 2 ，6 l ，7 2 ，7 1 ，5 2 ，2 1 ，6 2 ， 4 1 ，1 2 ，5 1 ，5 2 ，8 1 ，2 2 ，9 1 ，6 2 ) ，其中 e ( 冗) = ( 1 1 ，4 2 ) ，( 2 1 ，5 2 ) ，( 3 1 ，3 2 ) ，( 4 l ，1 2 ) ，( 5 1 ，5 2 ) ，( 6 1 ，7 2 ) ，( 7 1 ，5 2 ) ，( 8 1 ，2 2 ) ，( 9 1 ，6 2 ) ) 当m = 佗+ 2 且佗 7 时，考虑，n = ( _ 6 州尬) u ( 蚝扩4 ) u ( 一6 ，4 慨) u 甄，4umu 尬u 脑，其中一6 4 尬的二部集是【7 l ，8 l i 一，m l 】_ 和 5 2 ，6 2 ，仃2 】， 尬如引理2 9 的情形三所述足k 。- 6 。一4 的一个m 条边集，凰，。一4 的二部集是 【1 1 ，2 1 ，6 1 ) 和 5 2 ，6 2 ，n 2 ) ，m 2 如定理2 7 的情形四所述是慨，。一4 的一个l o 条边 集，e ( ) = ( 1 1 ，9 2 ) ，( 2 1 ，7 2 ) ，( 3 1 ，1 1 2 ) ，( 4 l ，9 2 ) ，( 5 l ，7 2 ) ，( 5 1 ，5 2 ) ，( 5 l ，9 2 ) ，( 6 1 ，5 2 ) ，( 6 l ，9 2 ) ， ( 6 l ，1 1 2 ) ) ，一6 ，4 的二部集是 7 l ，8 1 ，。一，m 1 】，和_ 【1 2 ，2 2 ，3 2 ，4 2 ，m 3 如定理2 7 的 情形二所述是_ 6 ，4 的一个4 条边集，e ( ) = ( 1 3 1 ，1 2 ) ，( 1 3 1 ，2 2 ) ，( 8 l ，3 2 ) ，( 8 l ，4 2 ) 】， 甄4 的二部集是 1 l ，2 1 1 - 一，6 1 ) 和 1 2 ，2 2 ，3 2 ，4 2 ) 由引理2 9 的情形三知g 可以分解 一6 ，n 一4 尬，由定理2 7 的情形四和情形二知g 可以分解甄，。一4 尬和一6 ，4 下面构造玩，4 u 必u 坞的8 长圈集： 5 l ，4 2 ，8 1 ，3 2 ，6 1 ，1 2 ，1 3 1 ，2 2 】， 2 l ，1 2 ，3 1 ，1 1 2 ，6 1 ，9 2 ，5 1 ， 7 2 ，【1 1 ，9 2 ，4 1 ，3 2 ，5 1 ，5 2 ，6 l ，4 2 ，【1 1 ，2 2 ，2 l ， e ( l 1 ) = ( 1 1 ，3 2 ) ，( 2 l ，4 2 ) ，( 3 l ，2 2 ) ，( 4 l ，2 2 ) ，( 5 1 ， 填充有余边图l = 尬ul 1 ，其中f = 仇+ 6 ， 3 2 ，3 1 ，4 2 ，4 l ，1 2 】) ，其余边图l 1 的边集是 1 2 ) ，( 6 1 ，2 2 ) 】因此，。的一个最大g 一 填充数p = 竺翌寻堂可得s = 2 ，覆盖数 1 5 c = 学 第二类：当m n + 2 时，考虑，。= ( ，n m ) u ( 1 。) u 尬u ，其 中，。m 的二部集足 1 l ，2 l ，n 1 和k ，舰如引理2 9 的情形一所述是，n 的一 个几十2 条边集，一 的二部集足_ m + 1 ) 1 ，( 佗+ 2 ) 1 ，m 1 ) 和k ，如定理 2 7 的情形四所述是必。一m 的一个m 一礼+ 4 条边集由引理2 9 的情形一知g 可以分 解，。尬，且由定理2 7 的情形四知g 可以分解k n 一。，。l 毛因此，k n 。的一个最 大岛- 填充有余边图l = 尬u 坞，z = m + 6 ，填充数p = 婴警堂可得s = 2 ，覆盖数 c = 学 情形九：当m 三5 ( m o d8 ) ，几兰5 ( m o d8 ) 时，可得后= 4 现在考虑，竹= ( ，。尬) u ( 吨竹尬) u 尬u 尬，其中，。尬的二部集是 1 l ，2 l 一，礼1 ) 和，m 如引 理2 9 的情形二所述是，。的一个佗+ 4 条边集，吨。的二部集足 ( n + 1 ) l ， ( n + 2 ) l ，m 1 ) 和k ， 龟如定理2 7 的情形一所述是瞄n 吨。的一个仇一礼条边集 由引理2 9 的情形二知g 可以分解，n 尬，且由定理2 7 的情形一知g 可以分解 一m 尬因此，。的一个最大岛填充有 x 3 1 预备知识 3 当疏导率c 一8 时，环上的业务疏导问题 在本部分中，我们用k 。( 也记为m ，n ) 表示每部的基数是他的完全t 部图，其中 箨，为委整数。 业务疏导问题的数学模型：给定一个具有n 个点的环型拓扑网和一个疏导率c 将 中的边划分成一些纸的子图毛，l 柳拶，令磐= 纛，是，研 ，使得| 嚣( 岛) l e 并且墨1 y ( l ) i 最小这个最小值记为a ( c ，n ) 在纸中的边划分的予图族8 中选择图厶，使得嘏烈最优是非常重要的如果 用肪瓣( c ) 表示至多具有c 条边的所有图中边数与顶点数的最大比值在文献【9 】中，j - c b e 咖o n d 等得到如下结果：a ( c ，几) 若i 兰端 j c 转e 髓o n 莲等秘还得到下面的结论： ( 1 ) p m a z ( c ) 的已知值为： ( 2 ) 已知一些小阶数的a ( 8 ，n ) ： 定义3 1 设g 是k ，的子图集合，若k ，的边能分拆成与g 中子图同构的边不交子图 族召，称拶为甄的g 分解，( 记为g d ( 秽，g ) 或g | 甄) 。 定义3 2 设g 是t 的子图集合，若t 的边能分拆成与g 中子图同构的边不交予 图族召，称8 为t