非平凡简单连通无向图G =（V,E）的原子键连通性（ABC）指数定义为（?）,其中V={V₀,V₁,…,V_n-1},d（v_i）为G中v_i的度.由于该拓扑指数在化学中有着广泛的应用,受到了众多学者的关注.然而其中两个最基本的问题亟待解决:问题A:刻画n阶极小ABC指数树;问题B:刻画给定叶子数k的极小ABC指数树（k-optimal树）.在这两个问题的研究中,人们采用了重复“搜索—猜想—证明”过程的研究路线,计算机搜索发挥了不容忽视的辅助作用.对于问题A:Furtula等人设计了一个暴力搜索算法搜索至n = 31,Dimitrov实现了基于度序列的搜索算法搜索至n = 300,之后Lin等人改进Dimitrov的算法并搜索至n = 400.现有的搜索结果都支持Dimitrov修正后的“模7猜想”.然而对于充分大的n,该猜想被Ahmadi等人完全否证.为了猜想高阶极小ABC指数树的结构,迫切需要一个效率更高的搜索算法或实现.对于问题B:Magnant等人断言k≥19时,平衡双星是唯一的k-optimal树,然而该断言被Goubko等人至k = 53的搜索结果所否证.对问题B的后续研究同样有必要借助更高效的计算机搜索.本文研究n阶极小ABC指数树和k-optimal树的搜索与刻画,主要结果有:1.n阶极小ABC指数树的搜索与刻画提高基于度序列搜索算法效率的关键在于发掘极小ABC指数树的度序列（最优度序列）的特征.令非增序列π =(△ =d₀,d₁,…,d₁₊₁,…,d_n-1)为一最优度序列(d_t≥3,d₁₊₁≤2),nk表示{d₁,d₂,…,d_t}中k的个数,（?）bk表示度序列为π的贪心树中B_k^-或B_k^-分支的数目.本文将最优度序列的特征改进为:（1）n₁=「（n-t-1）/2」,n₂=「（n-t-1）/2」,n₃=b2≤11,n₄≥b₃≥（2t-49）/3.且当n>18,n-t-1为奇数时有n3=b₂≤2,n₄ ≥b₃≥（4t-23）/6.（2）（n-11）/7≤t≤（n + 13）/5.（3）当n≥40时有4≤△≤t,△≤n/7 + 3.（4）2A+5t≤n+21.（5）4-77/（n-11）≤d≤5.基于最优度序列的上述特征,我们利用OpenMP实现基于度序列的搜索程序.该程序在8核单机上搜索300≤n≤1010仅需38.7小时.2.k-optimal树的搜索与刻画（1）令π=（d₀,d₁ …,d_t,1^k）（d_t≥2）为一k-optimal树的度序列.本文证明:当k≥19时有d_t≥ 6且1≤t≤「（k-6）/4」.（2）依据（1）设计了基于度序列的k-optimal树搜索算法,其OpenMP实现在8核单机搜索19≤k≤210仅需64小时.（3）在Gao等人的研究基础上,利用图的变换将（1）改进为:1≤t≤「k/5」,t≤d0≤k-4t,d1=…=dts=「d」≥ 6,其中d=（k-d0）/t +2,ε d-「d」.从而证明k-optimal树将由其参数d₀和t唯一确定.（4）依据（3）改进Gao等人的搜索算法,其串行实现在单机搜索至k= 20000仅需2.5小时.本文研究ABC指数极图刻画的两个基本问题,给出了n阶极小ABC指数树和k-optimal树的度序列的若干特征,实现了迄今最为高效的搜索程序.理论和搜索结果为后续研究指明了方向,为这两个问题的最终解决奠定了基础.