在图论研究中,生成树作为极小连通无圈图,是研究复杂图结构的重要基础。KIRCHHOFF
[1]考虑电流线性分布问题时首次提出了“树”的概念,并探究了生成树的存在性和计数问题。此后,生成树的存在性和计数问题逐渐成为研究热点
[2-4]。特别地,边着色图中彩虹生成树的存在性和计数问题已被广泛研究
[5-8]。边着色图是指具有从边集到自然数集的固定映射的图,且彩虹图是指满足任意两条边的颜色均不相同的边着色图。此外,边着色图中彩虹生成树的存在性和计数问题在工程实践领域具有广泛应用。例如,在通信网络领域,彩虹生成树可为“连接所有节点且成本最优”的需求提供有效拓扑结构,并且其数目可作为评估通信网络稳健性的关键指标
[9];在化学图论中,将分子图中的原子和化学键分别看作顶点和边建立图模型后,彩虹生成树可用于分析分子结构的稳定性
[10];而且,彩虹生成树计数问题在模拟复杂网络与评估网络可靠性等领域也具有重要的应用价值
[11]。
图的子图分解是指将该图分解为若干个边不交子图,使得其顶点集的并集为该图顶点集且边集的并集为该图边集。事实上,图的子图分解与图的边着色之间存在着自然的对应关系。对于具有特定子图分解的图,其彩虹子图是指满足任意两条边均来自该子图分解中不同子图的图。近年来,关于完全图在特定子图分解下彩虹生成树的存在性已被关注。BRUALDI等
[12]通过划分完全图
的边集,构造了
个1-因子,并证明了
在该子图分解下存在边不交彩虹生成树。KRUSSEL等
[13]在文献[
12]的研究基础上改进了结果,并证明了完全图
在相同条件下存在三棵边不交彩虹生成树。ALON等
[14]针对完全图
给出了一种完全二部分解
,并证明了
在此分解下存在彩虹生成树。LIU等
[15]针对完全图
的最小完全二部分解
,引入了基于该分解的色度矩阵,并通过色度矩阵的性质给出了
在任意最小完全二部分解下彩虹生成树数目的下界。最小完全二部分解是指包含最少数目子图的完全二部分解。
本文借助拟阵理论和Rado定理,分别证明了完全图在特定圈分解下和完全图在特定路分解下包含彩虹生成树及边不交彩虹生成树。同时,通过引入基于特定子图分解的色度矩阵并结合柯西-比奈定理,建立了完全图在特定圈分解下和完全图在特定路分解下彩虹生成树数目的下界。研究结果进一步丰富了完全图在特定子图分解下彩虹子图存在性的理论体系,并为彩虹子图在相关工程技术领域的应用提供了理论支撑。
1 基本概念及引理
首先,介绍一些基本定义与符号,对于文中出现但未定义的图论术语和符号,可参考文献[
16]。本文只考虑简单图,即无环或重边的图。用
表示顶点集
和边集
的图,并用
表示图
的边数。给定图
的边定向是指对
的每条边指定一个方向,从而得到对应有向图
,其中,
且
是由
中每条边定向后得到的弧集。图
的生成子图是指顶点集
且边集为
的图,记作
。边集
在
中的导出子图是指边集为
且顶点集为
中所有边的端点构成集合的图,记作
。完全图是指图中每对不同顶点都有一条边相连,并用
表示
个顶点的完全图。二部图是指顶点集可以划分为两个子集
和
且图中每条边的两个顶点分别属于
和
的图,并称
和
为该二部图的两个部集。对于部集分别为
和
的二部图,若
中每个顶点都与
中每个顶点相连,则称该二部图为完全二部图,并用
表示部集顶点数分别为
和
的完全二部图。图中的路是指该图中顶点和边互不相同的点边交替序列;圈是指起点和终点重合的路。用
表示
个顶点,并用
表示
个顶点的圈。
图的边着色是指从边集到自然数集的映射。称具有固定边着色的图为边着色图。若边着色图中任意两条边的颜色均不相同,则称该图为彩虹图。图的子图分解是指将分解为个子图,使得,且对于满足。特别地,若图子图分解中的每个子图均为圈,则称该分解为的圈分解;若图子图分解中的每个子图均为路,则称该分解为的路分解。相应地,若具有子图分解的图的子图中任意两条边均来自的不同子图,则称是的彩虹子图。
拟阵是指有序对,其中,是有限集合,称为拟阵的基础集,是的子集族且满足以下条件:1);2)若,且,则;3)若且,则存在使得。称中的元素为拟阵的独立集。设为无向图,定义是由的子集构成的集族,使得当且仅当不包含图的圈,并称拟阵为图的圈拟阵。对于图边集的任意非空子集,定义为圈拟阵的秩函数。
引理1[17] (Rado定理) 设
是有限集合
上的拟阵,
且
是
的子集族。则对于满足
的整数
,存在基数为
且元素来自
中不同子集的独立集
,当且仅当对于任意子集
,秩函数
引理2[17] 设
是顶点数为
,边集为
的图,且
是
的圈拟阵。则对于任意子集
,拟阵
的秩函数为
,其中,
是
的分支数。
引理3 设是顶点数为的简单图,且。如果对于给定正整数,,那么的秩函数。
证明 设为的分支数,其中,。分别用表示各分支的顶点数,则。由于,根据不等式可得,因此,即。引理3得证。
引理4[18] 设
是整数,且
是顶点数为
的完全图。则
存在路分解
,其中,对于
,
是长度为
的路。
接下来,在完全图上定义基于二部子图分解的色度矩阵。
设是完全图的二部子图分解,其中,对于,是以和为部集的二部图。规定:如果顶点,那么在中度的符号记作“”;如果顶点,那么在中度的符号记作“”。在这种情形下,的色度矩阵定义为,其中,如果,那么表示顶点在子图中的度;如果,那么。
令表示矩阵删除第行后的子矩阵。由色度矩阵的定义可知,矩阵满足每一列元素之和为零。对添加列和不为零的一列元素构成阶矩阵。考虑阶矩阵对应的行列式,对其进行初等行变换,将各行元素加到指定行后按该行展开。由于此阶行列式值的绝对值为定值,且该定值等于新增列元素之和与矩阵删除指定行后对应阶行列式乘积的绝对值,因此原矩阵任意删除一行对应的行列式值仅符号存在不同,即满足
不难发现,基于二部子图分解所定义的色度矩阵并不唯一。由于顶点(子图)可以任意重新标记,因此导致矩阵的行(列)重新排列。此外,顶点在子图中度的符号可任意定义使得每一列均可独立乘以。这些改变仅会使任意子矩阵的行列式改变一个因子。因此,是二部子图分解的不变量,记为。
对于图的二部子图分解,按照从一个部集到另一个部集的方向对中的边定向,由此得到图在下的有向图,记作。根据有向图,定义顶点-弧关联矩阵,其中,
进一步,定义弧-子图关联矩阵,其中,
对于无向图,可以采用同样的方式定义边-子图关联矩阵。
引理5 设是顶点数为且具有二部子图分解的图,是图基于二部子图分解的色度矩阵,是顶点-弧关联矩阵,且是弧-子图关联矩阵。则满足。
证明 根据矩阵乘法运算法则可知,需证明矩阵中元素等于矩阵的第行子矩阵与矩阵的第列子矩阵的乘积,其中,乘积表示子图中与顶点关联的边数。由于子图的边定向,从而矩阵和中与边相关的元素符号一致,因此这些元素的和等于顶点在子图中的度。根据色度矩阵的定义,矩阵中元素等于矩阵的第行子矩阵与矩阵的第列子矩阵的乘积。引理5得证。
引理6[19] (柯西-比奈定理) 设
是
矩阵,且
是
矩阵。假设子集
且满足
,
为
中列指标取对应
的
子矩阵,且
为
中行指标取对应
的
子矩阵。则有
。
引理7[20] 设
是图
的顶点-边关联矩阵。若
不包含圈,当且仅当
的列向量组线性无关。设
是图
的边-子图关联矩阵。若集合
中的边构成彩虹子图,当且仅当
关于集合
的行向量组线性相关。
2 主要结果
定理1 设是整数,且是顶点数为的完全图。如果存在满足且对于,的圈分解,那么在该分解下包含彩虹生成树。
证明 设是完全图的圈分解,其中,且对于,。考虑完全图的圈拟阵。设且是边集的子集族。根据引理1可知,存在基数为且元素来自中不同子集的独立集,当且仅当对于任意子集,秩函数
情形1。
根据引理2可知,秩函数。因为的分支数,所以秩函数。又因为,所以秩函数成立。
情形2。
情形2.1。
因为,所以。此时。根据引理3可知,秩函数
情形2.2。
因为,所以。此时。根据引理3可知,秩函数
情形2.3。
考虑与之间的关系,因此存在
由于且,因此。又因为,所以。因此,从而成立。根据引理3可知,秩函数
综上所述,对于任意子集,都有秩函数成立。根据引理1可知,对于的圈拟阵,存在基数为且元素来自中不同子集的独立集。由于该独立集是不包含圈的边集,且包含个顶点和条边,因此构成的图是连通的,即形成彩虹生成树。定理1得证。
推论1 设是整数,且是顶点数为的完全图。则在满足且对于,的圈分解下包含不同构于的彩虹生成树。
证明 设是完全图的圈分解,其中,且对于,。由定理1可知,完全图在该圈分解下包含彩虹生成树,记作。若不同构于,则该推论得证。接下来,假定同构于。设,其中,对于,边。
当时。由于每个圈至少包含3条边,因此对于任意指定的圈,可通过从中选取一条未出现在的边替换中来自的边,得到新的彩虹生成树,即。
当时。由于彩虹生成树的构造仅需从个子图中选取条来自不同子图的边,因此在该圈分解中,除被选取的个子图外,仍存在至少一个未被使用任何边的子图,记作。假设边。此时,边必连接两个非中心顶点与。由于圈至少包含3条边,因此对于任意指定的圈,可以通过从中选取未出现在的边替换中来自的边,得到新的彩虹生成树,即。
综上所述,在该分解下包含不同构于的彩虹生成树。推论1得证。
定理2 设是整数,且是顶点数为的完全图。假设是在满足且对于,的给定圈分解下不同构于的彩虹生成树。则在该圈分解下包含与边不交的彩虹生成树。
证明 设是在满足且对于,的给定圈分解下不同构于的彩虹生成树。令。对于,记,其中,且边。不难发现,子图包含一条路或一个圈。记是的子图分解。因此,为证明在圈分解下存在边不交彩虹生成树,需证明在子图分解下存在彩虹生成树。
对于图,考虑其圈拟阵。设,且是的子集族,其中,。根据引理1可知,存在基数为且元素来自中不同子集的独立集,当且仅当对于任意子集,有秩函数。接下来,根据的大小分两种情形讨论。
情形1。
由于是不同构于的彩虹生成树,因此是连通的。根据引理2可知,秩函数。又因为,所以秩函数成立。
情形2。
考虑与之间的关系,因此存在
情形2.1。
此时。因此成立。根据引理3可知,秩函数。
情形2.2。
因为,所以。此时。根据引理3可知,秩函数
综上所述,对于任意子集,都有秩函数成立。根据引理1可知,对于图的圈拟阵,存在基数为且元素来自中不同子集的独立集。因为该独立集是不包含圈的边集,且包含个顶点和条边,所以构成的图是连通的,即形成彩虹生成树。因此在该圈分解下包含与边不交的彩虹生成树。定理2得证。
注1 在定理2中,如果是在给定圈分解下同构于的彩虹生成树,那么与边不交的彩虹树将无法包含与的中心点关联的边,即无法构成彩虹生成树。
定理3 设是整数,且是顶点数为的完全图。则存在路分解,使得在该分解下包含彩虹生成树。
证明 由引理4可知,完全图存在由长度为的路组成的路分解。设是的路分解,其中,是长度为的路。对于完全图,考虑其圈拟阵。设且是的子集族。根据引理1可知,存在基数为且元素来自中不同子集的独立集,当且仅当对于任意子集,秩函数。接下来,根据的大小分三种情形讨论。
情形1。
此时,空集生成子图是空图,其分支数。根据引理2可知,秩函数。因为,所以秩函数
情形2。
情形2.1。
此时。因此成立。根据引理3可知,秩函数。
情形2.2。
此时。因此成立。根据引理3可知,秩函数
情形2.3。
考虑与之间的关系,因此存在
又因为,所以。因此,从而成立。根据引理3可知,秩函数
情形3。
此时的分支数。根据引理2可知,秩函数。因为,所以秩函数
综上所述,对于任意子集,都有秩函数成立。根据引理1可知,对于图的圈拟阵,存在基数为且元素都来自中不同子集的独立集。由于该独立集是不包含圈的边集,且包含个顶点和条边,因此构成的图是连通的,即形成彩虹生成树。定理3得证。
推论2 设是整数,且是顶点数为的完全图。则在由长度为的路组成的路分解下包含不同构于的彩虹生成树。
证明 由定理3可知,在由长度为的路组成的路分解下包含彩虹生成树,记作。如果不同构于,那么该推论得证。接下来,假定同构于。设,其中,对于,边。由于每条路包含条边,因此对于任意指定的路,可通过从中选取一条未出现在的边替换中来自的边,得到新的彩虹生成树,即。不难检验新的彩虹生成树不同构于。
综上所述,完全图在该路分解下包含不同构于的彩虹生成树。推论2得证。
定理4 设是整数,且是顶点数为的完全图。假设是在由长度为的路组成的给定路分解下不同构于的彩虹生成树。则在该分解下包含与边不交的彩虹生成树。
证明 设是在给定路分解下不同构于的彩虹生成树。令。对于,记,其中,且边。不难发现,子图至多包含两条边不交路。记是的子图分解。因此,为证明在该路分解下存在与边不交的彩虹生成树,需证明在子图分解下存在彩虹生成树。
对于图,考虑其圈拟阵。设且是边集的子集族。根据引理1可知,存在基数为且元素来自中不同子集的独立集,当且仅当对于任意子集,秩函数。接下来,根据的大小分两种情形讨论。
情形1。
由于是不同构于的彩虹生成树,因此是连通的。根据引理2可知,秩函数。因为,所以秩函数成立。
情形2。
考虑与之间的关系,因此存在
因为,所以。因此,从而成立。根据引理3可知,秩函数。
综上所述,对于任意子集,都有秩函数成立。根据引理1可知,对于的圈拟阵,存在基数为且元素来自中不同子集的独立集。因为该独立集是不包含圈的边集,且包含个顶点和条边,所以构成的图是连通的,即形成彩虹生成树。因此在该路分解下存在与边不交的彩虹生成树。定理4得证。
注2 在定理4中,如果是在给定路分解下同构于的彩虹生成树,那么与边不交的彩虹树将无法包含与的中心点关联的边,即无法构成彩虹生成树。
下面用表示完全图在子图分解下的彩虹生成树数目。
定理5 设是整数,且是顶点数为并具有路分解的完全图。则在该分解下,。
证明 设为完全图的路分解。值得注意的是中路是二部图。设是对中的每个路进行从一个部集到另一个部集的任意定向形成的有向图。设为的顶点-弧关联矩阵,且为的弧-路关联矩阵。进一步设为在路分解下的色度矩阵。根据引理5可知,。令表示矩阵删除第行后形成的子矩阵。由可得。根据的定义可知
。进一步可得
。
根据引理6可知
,
其中,∑是对由条边组成的所有子集求和,是保留对应的列得到的矩阵,且是保留所对应的行得到的矩阵。
根据引理7可知,若集合的边导出子图是的生成树,则;否则,。进一步由引理7及弧-路关联矩阵的定义可知,若集合的边导出子图是彩虹的,则;否则,。因此集合的边导出子图是在分解下的彩虹生成树,当且仅当。进一步有在分解下的彩虹生成树数目
定理5得证。
注3 定理5中完全图的路分解不必满足是长度为的路,只需确保该分解恰包含条路。用定理5的证明思路同样可以得到完全图在由长度为大于等于4的偶数的圈组成的圈分解下彩虹生成树数目的下界。
3 结束语
本文证实了完全图在特定的圈分解下和在特定路分解下均能够包含彩虹生成树和边不交彩虹生成树,并证明了存在与对应分解相关的不变量作为在特定圈分解下和在特定路分解下彩虹生成树数目的下界。研究结果为进一步考虑更一般图在特定子图分解下不同结构彩虹子图的存在性及确定相应彩虹子图数目下界提供了理论支撑。后续值得进一步考虑完全图在哪些圈分解下和在哪些路分解下能够包含更多边不交彩虹生成树,以及探究目前无法用定理5的证明方法确定的,在圈的个数大于的偶圈分解和包含奇圈的圈分解下及在路的个数大于的路分解下,彩虹生成树数目的下界问题。
国家自然科学基金项目(12301456)
国家自然科学基金项目(12471334)
陕西高校优秀青年人才支持计划项目(202120009)
延安大学研究生科研创新计划项目(YKY2025030)
延安大学创新创业训练项目(D2024117)