论文标题
边缘匹配的图形收缩及其交织特性
Edge-Matching Graph Contractions and their Interlacing Properties
论文作者
论文摘要
对于给定的图形$ \ MATHCAL {G} $，$ n $带有$ m $边缘，以及与图形关联的真实对称矩阵，$ m \ left（\ Mathcal {g} \ right）\ in \ Mathbb {r} $ \ MATHCAL {G} _ {r} $ r <n $的$ r <n $，使得$ m \ left的特征值（\ Mathcal {g} _ {r} _ {r} \ right）$ Interlellace $ m \ weft（\ mathcal {g} {g} \ right）$。顶点分区上的图形收缩被广泛用作组合绘制降低工具。在这项研究中，我们根据子空间映射和Minmax理论得出了一个绘制截面定理的图形。然后，我们定义一类边缘匹配的图形收缩，并显示两种类型的边缘匹配收缩如何提供拉普拉斯和归一化的拉普拉斯交织。提供了$ \ MATHCAL {O} \ left（Mn \右）$算法，用于查找标准化的Laplacian Interlacting收缩和$ \ Mathcal {o} \ left（n^{2}+nm \ right）$ algorithm $ algorithm $ algorithm是为了找到laplacian的相互作用。
For a given graph $\mathcal{G}$ of order $n$ with $m$ edges, and a real symmetric matrix associated to the graph, $M\left(\mathcal{G}\right)\in\mathbb{R}^{n\times n}$, the interlacing graph reduction problem is to find a graph $\mathcal{G}_{r}$ of order $r<n$ such that the eigenvalues of $M\left(\mathcal{G}_{r}\right)$ interlace the eigenvalues of $M\left(\mathcal{G}\right)$. Graph contractions over partitions of the vertices are widely used as a combinatorial graph reduction tool. In this study, we derive a graph reduction interlacing theorem based on subspace mappings and the minmax theory. We then define a class of edge-matching graph contractions and show how two types of edge-matching contractions provide Laplacian and normalized Laplacian interlacing. An $\mathcal{O}\left(mn\right)$ algorithm is provided for finding a normalized Laplacian interlacing contraction and an $\mathcal{O}\left(n^{2}+nm\right)$ algorithm is provided for finding a Laplacian interlacing contraction.
