下载:
-
随着计算机科学的飞速发展，图论中一些复杂问题得以解决，同时图论的应用也拓展到了复杂网络、大数据和生物基因工程等领域.图论在化学中也有着重要应用.在量子化学中，共轭分子以离域的π-键为特征，具有极其特殊的物理化学性质.图论化学家们发现，π-电子的总能量Eπ用HMO法与其图的邻接特征根的绝对值之和一致，即E(G)=
$\sum\limits_{i=1}^n$ |λi|，Eπ是共轭分子热力学稳定的重要衡量指标[1].目前，在该领域中，图的能量方面已经取得了很多成果.文献[2]研究得到了总π-电子能量的上下界.文献[3]给出了图谱理论在化学方面的应用范围.文献[4]研究了两棵Π-型树同谱的求解算法.文献[5]用计算机实现了对扩展网格图能量的精确计算.文献[6]提出了极小能量图的猜想，该猜想在文献[7]中得到了部分验证.文献[8]证明了六角形晶体(Hexagonal lattices)的能量界限.文献[9]给出了一些图的能量及能量的上下界.六角系统是一个2-连通的平面图，且其内部面是由单位长度为1的正六边形结合而成.文献[10-11]给出了几类六角系统图的特征多项式及其应用，文献[12]研究了T-型六角系统的染色问题.本文主要研究一类特殊的六角系统图的能量相等问题.此类六角系统图是在一个正六边形的基础上，对正上方、右上方、右下方动态增加正六边形个数，形成新的该类型的六角系统图.算法生成该类六角系统图的邻接矩阵，并求出等能量图.实验结果表明，对于一组参数总和相等的异构六角系统图，是存在能量相等的图形的.
全文HTML
-
1) 根据参数总和相同，且排除图形对称这些条件，生成该类型的所有非同构的六角系统图对应的邻接矩阵.
2) 求每个邻接矩阵对应的图谱，并求其绝对值之和，作为该六角系统图的能量.
3) 对一类六角系统图的能量进行比较，如果相等则输出结果.
参数L1，L2，L3分别表示在基础六边形的正上方、右上方、右下方增加的正六边形的个数. L1，L2，L3∈{0，1，2，…，sum：L1+L2+L3=sum}，3个方向的参数确定之后就唯一确定了一个六角系统图，记n为图的总顶点个数.
-
算法分为3部分来解决该类型的六角系统图问题，以下对其进行详细描述.
算法1 分解参数总和sum.
算法中出现的参数说明：
T：三元组集合，T={ti：i=1，2，…，r}，其中ti为集合T中第i个三元组{x，y，z：x，y，z∈
$\mathbb N$ }.输入：参数总和sum.
输出：一个包含3个扩展分支的参数的三元组T.
算法执行步骤如下：
1) 设置一个三元组ti(x，y，z)，通过循环变量控制x，y，z的值，使得x+y+z=sum；
2) 控制三元组中变量y的值，使得y的值从0开始增长，x和y不能同时为0，并且控制x≤y，得到待排除同构图的三元组；
3) 当三元组中的第一个元素x=0时，在三元组中查找其它三元组的z和y与该三元组中y和z分别相等的三元组，然后删除该三元组，最终得到不含有同构图的三元组；
4) 将所有满足条件的三元组加入到集合T中，返回集合T.
图 1给出了不同三元组形成的同构图H(L1，L2，L3)，参数分别为L1，L2，L3的六角系统图，下文如同.
算法1生成的集合T中的三元组中的每个元素表示后续生成的六角系统图的3个参数，通过算法1中的步骤可以保证生成的六角系统图中没有同构图.
算法2 生成六角系统图的邻接矩阵.
算法中出现的参数说明：
M：矩阵集合，M={Mi：i=1，2，…，s}，Mi为集合M中第i个n阶矩阵.
输入：L1，L2，L3.
输出：M[n][n].
算法执行步骤如下：
1) 从集合T中依次取出三元组，作为算法2的输入，如果集合为空，则终止运算；
2) 根据输入的参数，按照规则1判断六角系统图的形状，计算n的值；
3) 根据得到的n值，新建二维数组M[n][n]来存储六角系统图的邻接矩阵；
4) 根据输入的参数，按照规则2和规则3对图中各顶点进行标号，根据规则生成邻接矩阵M[n][n]，若(i，j)∈EH(图H的边集)，则有M[i][j]=1，M[j][i]=1；
5) 将邻接矩阵M加入到邻接矩阵M1中，并输出该矩阵，返回步骤1)，直到三元组全部取完，算法终止.
算法2-规则1——n值计算：
1) 如果L2=0或L1，L3=0，则n=(L1+L2+L3)+6；
2) 当3个参数不满足步骤1)时，如果L1，L2，L3≠0，则n=(L1+L2+L3)+4；
3) 当3个参数不满足以上规则时，n=(L1+L2+L3)+5.
算法2-规则2——建立顶点的点集数组：
1) 用L1行4列、L2行4列和L3行4列的二维数组来分别存储基础六边形的3个分支上的顶点，用一个全局变量count来记录六边形的顶点个数；
2) 对L1方向上的顶点建立点集数组，二维数组大小为L1行4列，共有L1*4个顶点，每一行的4个元素代表一个扩展六边形顶部需要扩展的4个顶点，当每次对一个新的顶点标号时，则全局变量count+1，并将count的值赋值给二维数组中顶点的位置；
3) 对L2方向上的顶点建立点集数组，二维数组的大小为L2行4列，共有L2*4个顶点，第一行的第一个顶点标号是L1方向上的二维数组中第一行第四列的元素，对其它顶点标号时，每对一个顶点标号，则count+1，并将count对应的值赋值给二维数组中顶点的位置；
4) 对L3方向上的顶点建立点集数组，二维数组的大小为L3行4列，共有L3个顶点，第一行的第一个顶点的标号是L2方向上的二维数组中第一行第四列的元素，对其它顶点标号时，每对一个顶点标号，则全局变量count+1，并将count对应的值赋值给二维数组中顶点的位置；
5) 得到3个存储了3个分支上的顶点标号的数组.
算法2-规则3——连接相关联顶点：
1) 将L1分支的二维数组中的第一行第一列的元素与L1分支的第一个顶点连接(即在邻接矩阵中将两个顶点对应的位置元素置为1，并将其对称位置处的元素置为1)，将第一行第四列的顶点编号与L1分支的第二个顶点连接，再将二维数组第一行内的顶点依次连接，以此形成第一个扩展六边形；
2) 如果L1＞1，则将二维数组第二行第一列的顶点与第一行第二列的顶点连接，将二维数组第二行第四列的顶点与第一行第三列的顶点连接，再将第二行内的顶点依次连接；
3) 依次连接L1内的顶点，直到二维数组的第L1行第一分支连接完毕；
4) L2，L3分支的连接与L1相同.
标号示例(图 2)，以参数(2，3，2)，(2，0，1)示例H(2，3，2)，H(2，0，1).
算法3 求六角系统图能量.
输入：矩阵特征值R[n].
输出：六角系统图能量E(H).
算法执行步骤如下：
1) 算法3执行完毕会生成矩阵特征值集合EV，依次从集合中取出元素作为算法4的输入，若集合为空，则算法终止；
2) 对特征值取绝对值，求和，作为该图的能量EH，将能量值加入能量集合E中；
3) 重复执行步骤1)，直到特征值集合EV元素全部取完，算法终止.
1.1. 算法的基本思想
1.2. 算法的描述
-
影响算法时间复杂度的因素主要有以下3个方面：
(a) 生成参数总和为sum的邻接矩阵集合，T1=o(n2)；
(b) 求矩阵集合中每个矩阵的特征值，T2=o(n2)；
(c) 比较两个图的能量是否相等，T3=o(n*log2n).
-
本算法计算矩阵特征值时精度设为10-9，因此在比较两个图的能量过程中，能量分别记为E1，E2，当能量差|E1-E2|≤10-9*n时，就可以认为这两个图是等能量的.
本文选取参数总和为sum∈[0, 38]的所有该类型的六角系统图进行算法测试，可以得出，当sum≥29时，有等能量图出现.以sum=29为例，H5，11，13与H5，13，11，H3，13，13与H3，14，12等能量，具体步骤如下：
1) 输入29，得到三元组集合，三元组中的3个元素分别为该类型六角系统图的3个参数，该集合中无同构图.部分集合如下：
{0，0，29}，{1，0，28}，{2，0，27}，{3，0，26}，{4，0，25}，{5，0，24}，{6，0，23}，{7，0，22}，{8，0，21}，{9，0，20}，{10，0，19}，{11，0，18}，{12，0，17}，{13，0，16}，{14，0，15}，{0，1，28}，{1，1，27}，{2，1，26}，{3，1，25}，{4，1，24}，{5，1，23}，{6，1，22}，{7，1，21}，{8，1，20}，{9，1，19}，{10，1，18}，{11，1，17}，{12，1，16}，{13，1，15}，{14，1，14}，{0，2，27}，{1，2，26}，{2，2，25}，{3，2，24}…
2) 当sum=29时，图的顶点个数有3种情况，分别为：120，121，122，对应的邻接矩阵的阶数分别为120，121，122.分别比较在阶数相同时的能量值.由于数据量较大，故不列出矩阵.
3) 比较3种情况下的能量值，只有当n=120时，H(5，11，13)与H(5，13，11)，H(3，13，13)与H(3，14，12)能量相等，且能量值分别为：E(H(5，11，13))=E(H(5，13，11))=168.956 429 6，E(H(3，13，13))=E(H(3，14，12))=168.941 396 6，由于数据量较大，故只列出其中一个等能量图的数据.图H(5，11，13)，H(5，13，11)的邻接矩阵对应的特征值如表 1和表 2所示.
表 3-表 11分别为sum∈[30, 38]范围内的等能量图，由于数据量较大，故在此只列出此范围内的等能量图.其中每个表中的第一列为组数，代表在当前点数下所确定的该类六角系统图中有多少组等能量六角系统图，第二列为对应确定的某一个图，第三列为该图的能量值.由于邻接矩阵及特征值数据量较大，故在此列出图的能量值.
-
综上可知，当参数总和sum≥29时，有等能量图出现.利用该算法通过大量数据实验分析，可以得出，在该类六角系统图中等能量的图逐渐增加，并且在能量值相等的情况下，等能量的图越来越多.随着参数的增大，生成的六角系统图的邻接矩阵的阶数随之增加，其特征值的求解以及等能量的判定会耗费更多时间，以后将给予相应的改进.