|
|
k树的完美消除序列
|
Abstract:
弦图的完美消除序列可应用于用高斯消去法求解稀疏正定线性方程组的研究，并且弦图的完美消除序列在多个学科均有应用。本文主要研究弦图的子类——k树的完美消除序列，首先证明了k树的完美消除序列可以通过k度点来刻画。其次证明了k树Tk(n)的节点按照完美消除序列排序后满足：1) ![\"\"](\"Edit_8302a779-7deb-4859-833f-b9ae03d402f2.png\")
；2) ![\"\"](\"Edit_ab1cacc3-c0a6-48f0-b4a0-3fde69462d5e.png\")
。最后证明了k树完美消除序列与k树构造过程之间以互逆的方式一一对应。此外，本文也将前述证明应用于k树的识别，给出了相应的算法。
The perfect elimination orderings of chordal graphs can be applied to the study of solving sparse positive definite systems of linear equations by Gaussian elimination method, and the perfect elim-ination orderings of chordal graphs is applied in many disciplines. In this paper, we mainly study the perfect elimination orderings of k-trees, a subclass of chordal graphs. First, we prove that the perfect elimination orderings of k-trees can be characterized by vertices with k degrees. Secondly, it is proved that the vertices of k-trees which are sorted according to the perfect elimination orderings satisfy: 1) ![\"\"](\"Edit_86565b03-e600-4629-ad62-ff76921a31c3.png\")
; 2) ![\"\"](\"Edit_69fffea4-fdd7-4ca4-8f9d-9c8ba6346d3f.png\")
. Finally, this paper proves that the perfect elimination orderings of k-trees corresponds to the construction process of k-trees in a reciprocal way. In addition, this paper also applies the above proofs to the recognition of k-trees and gives the corresponding algorithm.
| [1] | Parter, S. (1961) The Use of Linear Graphs in Gauss Elimination. SIAM Review, 3, 119-130.
https://doi.org/10.1137/1003021 |
| [2] | Rose, D.J. (1970) Triangulated Graphs and the Elimination Process. Journal of Mathematical Analysis and Applications, 32, 597-609. https://doi.org/10.1016/0022-247X(70)90282-9 |
| [3] | Koller, D. and Friedman, N. (2009) Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambrigde. |
| [4] | Rouzbahani, M.M., Saeedi, M.S. and Kiani, D. (2021) Regularity of Binomial Edge Ideals of Chordal Graphs. Collectanea Mathematica, 72, 411-422. https://doi.org/10.1007/s13348-020-00293-3 |
| [5] | Arvind, V., Nedela, R., Ponomarenko, I., et al. (2022) Testing Isomorphism of Chordal Graphs of Bounded Leafage Is Fixed-Parameter Tractable. In: Bekos, M.A. and Kaufmann, M., Eds., International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, Cham, 29-42. https://doi.org/10.1007/978-3-031-15914-5_3 |
| [6] | Liu, C.H. and Chang, G.J. (2013) Roman Domination on Strongly Chordal Graphs. Journal of Combinatorial Optimization, 26, 608-619. https://doi.org/10.1007/s10878-012-9482-y |
| [7] | Uehara, R., Toda, S. and Nagoya, T. (2005) Graph Isomorphism Completeness for Chordal Bipartite Graphs and Strongly Chordal Graphs. Discrete Applied Mathematics, 145, 479-482. https://doi.org/10.1016/j.dam.2004.06.008 |
| [8] | Munro, J.I. and Wu, K. (2018) Succinct Data Structures for Chordal Graphs. In: Hsu, W.-L., Lee, D.-T. and Liao, C.-S., Eds., 29th International Symposium on Algorithms and Computation (ISAAC 2018), Dagstuhl Publishing, Wadern, Article No. 67. |
| [9] | Telle, J.A. and Proskurowski, A. (1997) Algorithms for Vertex Partitioning Problems on Partial k-Trees. SIAM Journal on Discrete Mathematics, 10, 529-550. https://doi.org/10.1137/S0895480194275825 |
| [10] | Rose, D.J. (1974) On Simple Characterizations of k-Trees. Dis-crete Mathematics, 7, 317-322.
https://doi.org/10.1016/0012-365X(74)90042-9 |
| [11] | Berry, A., Blair, J.R.S. and Heggernes, P. (2002) Maximum Cardinality Search for Computing Minimal Triangulations. In: Goos, G., et al., Eds., International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, Berlin, 1-12. https://doi.org/10.1007/3-540-36379-3_1 |
