组合菲德勒理论的几何视角
《Linear Algebra and its Applications》:A Geometric View of Combinatorial Fiedler Theory
【字体:
大
中
小
】
时间:2026年09月19日
来源:Linear Algebra and its Applications 1.1
编辑推荐:
摘要 最近,Andrade和Dahl通过研究一个参数b(G)引入了组合Fiedler理论,该参数被定义为图G=(V,E)代数连通性的瑞利商最小化刻画的?1类比。在本文中,我们研究相应的最大化问题,它充当最大拉普拉斯特征值的?1类比的角色。我们表明,与该最大化问题相关联的新参数
摘要 最近,Andrade和Dahl通过研究一个参数b(G)引入了组合Fiedler理论,该参数被定义为图G=(V,E)代数连通性的瑞利商最小化刻画的?1类比。在本文中,我们研究相应的最大化问题,它充当最大拉普拉斯特征值的?1类比的角色。我们表明,与该最大化问题相关联的新参数B(G)具有一个简单的精确描述:它是G中两个最大顶点度数的平均值。首先,我们给出了最小化和最大化问题的统一组合处理。随后,两个优化问题在几何设置中被重新解释。可行集被识别为一个(n?2)维的菱形十二面体壳,其中n=|V|。为此多面体呈现了额外的结构,包括最大化解出现在其顶点上、最小化解出现在其面的中心这一事实。最后,我们分析了若干图族中b(G)和B(G)的最优向量数量。尽管B(G)的值由两个最大度数决定,但我们证明计算达到该值的向量数量实际上是#P-完全的。
引言 谱图理论通过自然关联于图的矩阵(如邻接矩阵和拉普拉斯矩阵)的特征值和特征向量来研究图。这一方法早期的一个核心例子是Fiedler的代数连通性a(G)[9],即第二小拉普拉斯特征值,它可以通过一个最小化问题的瑞利商刻画;更精确地说,设G=(V,E)是一个简单图,则
a(G)=min_{x∈R^V} {∑_{uv∈E}(x_u?x_v)^2 : ∑_{v∈V}x_v=0 ∧ ∑_{v∈V}x_v^2=1}
参见[4]进行系统性论述。最小化变量是向量x=(x_v)_{v∈V}∈R^V。全文中,我们使用相同的约定:粗体小写字母表示向量,对应的非粗体字母表示它们的坐标。相应的特征向量,现在称为Fiedler向量,为每个顶点分配一个实坐标,因此可以解释为图的一维表示。这种解释是它们在图划分和图绘制中应用的基础[13],[14]。
Andrade和Dahl的近期贡献[2]开创了他们所谓的组合Fiedler理论,将a(G)参数经典刻画中的?2范数替换为?1范数。他们引入了参数
b(G)=min_{x∈R^V} {∑_{uv∈E}|x_u?x_v| : ∑_{v∈V}x_v=0 ∧ ∑_{v∈V}|x_v|=1}
这可被视为代数连通性的?1类比。所得问题保留了经典理论的风味,但将其从主要以线性代数为基础的设置转变为离散组合设置,与最稀疏割密切相关。
本文的主要目的是通过研究其自然最大化对偶来扩展该理论。我们引入了参数
B(G)=max_{x∈R^V} {∑_{uv∈E}|x_u?x_v| : ∑_{v∈V}x_v=0 ∧ ∑_{v∈V}|x_v|=1}
两个参数都被定义为在相同可行域上的优化问题,具有相同的目标函数。从经典?2理论的角度看,它们可被视为两个极端拉普拉斯特征值λ_2和λ_n的?1类比。尽管最小化问题已经具有丰富的组合解释[2],[16],但最大化问题似乎此前未被系统研究。我们的主要结果之一表明B(G)具有一个简单的精确形式:如果d_1和d_2是G的两个最大顶点度数(可能d_1=d_2),则B(G)=?(d_1+d_2)。度数和表达式在研究极端拉普拉斯参数时并不陌生,例如在最大拉普拉斯特征值的上界研究中[1],[17]。然而在这里,度数平均值恰好等于B(G)。
作为第一步,我们扩展了Andrade和Dahl的部分结果,使其同时适用于最小化和最大化问题。特别是,两个极值都存在解,其正分量全部相等,负分量全部相等。因此,尽管可行域具有无限基数,两个优化问题都可以归结为R^V中一个有限结构化向量集G。该集合具有自然的组合解释:其元素与顶点集的有序拟二划分(P,N)之间存在一一对应,其中P记录正坐标,N记录负坐标,其余顶点的坐标为零。在该对应关系下,目标函数用相对割规模表示,给出了b(G)和B(G)的基于割的公式。对于最小化问题,这恢复了Andrade和Dahl的刻画[2];对于最大化问题,它导出了上述度数公式。
我们的工作的第二个主要贡献是从几何上重新解释这些优化问题。公共可行域可视为?1单位球的超平面截面的相对边界。这将问题置于一个与d维菱形十二面体[8]和根多面体[3]相关的自然多面体设置中。
与图划分相关的?1谱方法也在切格勒割的语境下得到了研究[6]。特别是,Chang、Shao和Zhang使用可行集的面元分解来处理图1-拉普拉斯切格勒问题,指出目标函数在每个面元上是凸的[5]。这在精神上与此处所采用的方法很接近:我们也将?1型可行域分解为适应目标函数的面元;在我们的设置中,这种细化使得目标函数在每个面元上是仿射的。我们将在3.4小节中,在引入相关几何对象之后,回到这一比较。
本文组织如下。第2节发展两个优化问题的有限组合形式化并证明B(G)的度数公式。第3节研究公共可行域的几何、其面元分解以及G上诱生的结构,以对部分主要结果给出替代的几何证明。第4节将研究结果应用于若干图族,并在这些例子中计算G相应的?1-Fiedler向量。第5节证明计算G中达到B(G)的向量数量的#P-完全性。
初步知识 注意,等式(1)和等式(2)中的两个优化问题都定义在相同的可行集F?R^V上,F={x∈R^V:∑_{v∈V}x_v=0 ∧ ∑_{v∈V}|x_v|=1},并且具有相同的目标函数f:R^V→R_{≥0},f(x)=∑_{uv∈E}|x_u?x_v|,因此我们可以将等式(1)和(2)改写为
b(G)=min_{x∈F} f(x), B(G)=max_{x∈F} f(x)
可行集可以理解为正分量之和为?且负分量之和为??的向量集。
引理1 Andrade和Dahl[2] F={x∈R^V:∑_{v∈V,x_v≥0}x_v=? ∧ ∑_{v∈V,x_v≤0}x_v=??}
组合Fiedler理论的几何 设H为R^V中包含原点且垂直于全一向量1的超平面,即H={x∈R^V:1^?x=0}={x∈R^V:∑_{v∈V}x_v=0}。设B为R^V中以原点为中心的?1单位球,即B={x∈R^V:‖x‖_1≤1}={x∈R^V:∑_{v∈V}|x_v|≤1}。集合B是{±e_v}_{v∈V}的凸包,其中e_v是R^V的标准基向量;它被称为十字多面体。现在,集合F?=H∩B={x∈R^V:∑_{v∈V}x_v=0 ∧ ∑_{v∈V}|x_v|≤1}不完全等于我们的可行集,但可以用地e_v向量在...中清晰地刻画。
实例 在本节中,我们在若干图族上说明前面各节的结论。对于每个例子,目标是描述实现定义b(G)和B(G)的优化问题的G中的点,并显式计算相应的?1-Fiedler向量。这也为下一节研究的计数问题提供了具体实例。此处仅考虑G中的?1-Fiedler向量,因为否则在许多情况下?1-Fiedler向量会有无限多个。
困难性结果 前一节的结论表明,对于若干自然的图族,G中的?1-Fiedler向量集可以显式描述并用封闭形式计算。这自然引出以下一般性问题:给定一个图,确定?1-Fiedler向量数量有多困难?值得强调的是,在最小化方面,Andrade和Dahl[2]已经表明,通过……计算b(G)和相应的?1-Fiedler向量是NP-难的。
José Fernández Goycoole | Andrea de las Heras-Parrilla | Luis H. Herrera | Clemens Huemer | Carlos Seara
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号