四度图的异构类快速算法（I）：A型域与简单B型域的情形

四度图的异构类快速算法（I）：A型域与简单B型域的情形 四度图的异构类快速算法(I):A型域与简 单B型域的情形 第20卷第2期佛山科学技术学院学报(自然科学版)Vo1.20No.2 2002年6月JournalofFoshanUniversity(NaturalScienceEdition)Jun.2002 文章编号:1008一O171(2002)02-0006—04 四度图的异构类快速算法(I): 型域与简单B型域的情形 伍启期 (佛山科学技术学院数学系,广东佛山528000) 摘要:根据四度图G(4)的顶点数a(i)的偏导数规律.得到快速写出G(4)的全部异构类的算法.解 决了型域和简单的B型域的情形. 关键词:四度图;异构类;偏导数;算法;等差数列 中图分类号:Ol57文献标识码:A 文献[1,2]给出了四度图及其分布域,异构类等一系列的定义,而且文献[2]指出了异构 类在图论上和在碳氢化合物结构上的意义.当分布域比较大,则异构类也跟着比较多,逐个 依格点计数是很麻烦的,必须寻找简便快速的算法.本文正是要解决这一问题. 1原理及算法 根据下述公式.: (2)一”+2v一2—3,l一2f2, (1)一2tl+t2+2—2v, 其中,f一(4)?1表示4度点的个数,t一(3)?0表示3度点的个数. 与(2)得偏导数 f一一3,(t!lJtl每增加1,(2)减少3)atI1 „……一 I一2o(t!lJtl每增加1,(1)增加2)ati1 …… 若t固定,则由式(1)与(2)得下述偏导数 一一2,(即f.每增加1,6(2)减少2) 一 1.(即f.每增加1,(1)也增加1) (1) (2) 若t.固定,由式(1) 收稿日期:200卜()9一l7 作者简介:伍启期(1939一),男,广东台山人.佛山科学技术学院教授.主要从事组合数学和图论研究 (3) (4) (5) (6) 2—21—2穗 ,???J,???,,?,?? l 第2期伍启期:四度图的异构类快速算法(I):A型域与简单B型域的情形7 因为t为横轴,t为纵轴,如图1所示,结合式(3), (6)及其对应的意义,得到快速写出全体异构类的算法. 算法1对V=0,1,2适用,即对型分布域适用: l0 8 1)取R上的B(1,0)为基点.由式(1)与(2)算得 (2),(1),得到格点B(1,0)所对应的异构类(1,0,(2),6 (1)).这是填写异构类表的出发点;. 2)由式(3),根据偏导数的意义,易知在水平向右的一? 列异构类中,诸(2)构成了公差为一3的等差数列.因. (2)?0,故此数列应写至最小非负的一项停止; 2,6,1.J 2.S..1 2.4.5.J 2,,7, 2.2,9. 2.J.11. 2.(J.1. (4., (4.2. (4.1. fL1.【1. 1 2)(,2,(J.14) 1)(.1I2.1) (1】fS.(1.4.12)f0,(1,1,J41 3JE;型区域的算法 当?3.,】?2一3,对应的分布区域就是B型区域,如图2所示的多边形 AMNCDE,两条斜线分别为,!.此时,B型区域的求异构类的算法,与型的算法大同小 }l ? , } n2,.}l „„,? ? ? S42?? ,,,?? i{{ …l三 8了6S49一? } 8佛山科学技术学院学报(自然科学版)第2O卷 异.分析如下:在RtAMBN上的而又位于MN下方的格点被割去,不难证明对应的(1)< o,从而四元有序对((4),(3),(2),(1))中的(1)<o,组合不合理,~u,-f的有序对不是 异构类,舍去.下面补充证明(1)<O. 13 图2B型区域示意图图3B型区域买例 证明已知B一(1,O),N一(一1,O),:2t+,:一2z一2:.对Vf?[1,一2],由,方 程有纵坐标 t2—2v一2—2t1.(7) 由式(7)容易求出MN下方任一格点(f.,f.),其中1?f.?一2,tt2~t.--Ill,1?n?f..用此 格点代入式(2) (1)一2tl+t2+2—2v一2t1+f2—7n+2—2v一一7n<0.(8) 其余易知(4)?1,(3)?O,(2)?O,但上面已证明(1)<O,故此时的四元有序对不 合理,舍去.小结上述分析得算法2. 算法2关于B型区域求异构类的算法(亦称B型区域的格点负值弃去法):以B(1,O) 点为出发点,依照型区域的算法1),6)的各步骤逐一完成,最后将含有(1)<O的四元 组合弃去,余下的即为所求的全部的异构类. 4B型区域算例 设”一20,一4.由已知公式_1j,可得 1?tl?8,0?t2?11,3fl+2f2?26,2fl+f2?6. 作得对应的B型分布区域R(4,20),如图3所示的多边形AMNCDE.在R上有5O个格点, 即有50个异构类.如果担心观察有误(因为上述格点包括斜边上的格点),还可以用公式验 算之.由文献[3]的定理2有 ,(,7)一P(,+2v一2,3)一(一1)(一2).(9) 将一20.73=4代入式(9)得异构类数 ,(4,2O)一P(26,3)一3×2—56—6—50.(查文献L3]表1) 可见I(4,20)与图3所示一致,无误.但不能逐一去求出具体的异构类,这样做法太麻 1963 第2期伍启期:四度图的异构类快速算法(I):A型域与简单B型域的情形 烦了.采用算法2,简述如下:由B(1,O)求出对应的组合(1,0,23,一4),逐一完成各步骤,例 如,由23得水平数列23,2O,17,14,ll,8,5,2;由一4得水平数列一4,一2,0,2,4,6,8,10 等.这样,就得出图3上对应于BC线段上各格点的四元有序对,即:(1,0,23,一4)(2,0,20, 一 2)(3,0,17,0)(4,0,14,2)(5,0,l1,4)(6,0,8,6)(7,0,5,8)(8,0,2,10). 再由(1,0,23,一4)的23竖直向上写出数列23,21,19,17,15,13,11,9,7,5,3,1;由一4 向上写出数列一4,一3,一2,一1,0,1,2,3,4,5,6,7...?逐一完成各等差数列,就得到如表2, 将左下角的6个有负值的组合弃去((1)<0),余者即为所求的全部异构类,共50个. 表2当一20一4时B型的异构类表 1.11.1.7) 1,lO.0,6)(2, 1.9.5.5)(2, 1.8.7.4)(2. 1.7.9.3)(2. 1.6.11.2)(2. 1.5.13.1)(2, 1.4.15.o)(2. 1.017.一1)(2, 1.2.19.一2)(2, 1.1.2l,一3)(2, i.o.2:3,一4)(2, 参考文献 lO,o, 9,2. 8.1. 7. 6.8. 5.1o. 4.12. 3,14. 2.16. 1.18. ).20. 8 0 0 3 3 3 3 :3 3 8, 7. 6. :】? 4. :{. ?一? 1. o. 1, 3. :)? i? 9, 11. 13. 15. 17. 8) 7) 5) 5) 4) 3) 2) 1) o) 4 4 4 4 4 4 4 4 7.o.f)) 6.2.8) .4.7)(5. _】.(;.6)(5. :j.8.5)(5. 2.1o.1)(5. 1,12.:{)(5. (J.14.2)(5, (7.2.i.1o) (7.1.3,f))(8.1.o,11 (7.o.5.8)(8,o.2.1o [1]伍启期.?(G)=4的平面连通图的存在性及其分布区域[J].华中理工大学学 报?1990?(2):161—166? [2]wUQi(1i.TheNumberofIsomericTypesofG(4)rJ].CombinatoricsandGraphTheory?95,1995, (1):407—413. [3]伍启期.关于G(4)的异构类数的新公式[J].佛山科学技术学院学报(自然科学 版)?1998?16(4):15? Thequickarithmeticfortheisomeric typesofthegraphsindegreefour(1) forthecasesofformAnd~pieformBAandsimpletorm WUqi—qi (DepartmentofMathematics.FoshanUniversity.Foshan528000?China) Abstract:Inthispaper,weobtainthequickarithmeticofwritingoutalltheisomerictypes ofthegraphsindegreefouronthebasicofthelawsofthepartialderivativesofthe vertices(i)inG(4),thegraphsindegreefour.Atfirst,wewouldsolvethecas , 3570儿 “„二 8765432l09