基于连通度优化的图的S-T重构

doi:10.6040/j.issn.1671-9352.0.2023.462

《山东大学学报(理学版)》 ›› 2025, Vol. 60 ›› Issue (12): 156-160.doi: 10.6040/j.issn.1671-9352.0.2023.462

基于连通度优化的图的S-T重构

吕臻,魏宗田^*

西安建筑科技大学理学院, 陕西西安 710055

发布日期:2025-12-10
通讯作者: 魏宗田(1964— ),男,教授,博士,研究方向为图论与组合优化. E-mail:ztwei@xauat.edu.cn
作者简介:吕臻(1993— ),男,硕士研究生,研究方向为图论与组合优化. E-mail:ryosyo.lv@foxmail.com*通信作者:魏宗田(1964— ),男,教授,博士,研究方向为图论与组合优化. E-mail:ztwei@xauat.edu.cn
基金资助:
国家自然科学基金资助项目(1661066)

S-T reconstruction of graph based on connectivity optimization

LYU Zhen, WEI Zongtian^*

Department of Mathematics, Xian University of Architecture and Technology, Xian 710055, Shaanxi, China

Published:2025-12-10

摘要/Abstract

摘要： 提出图的颠覆策略和S-T重构概念,讨论了基于连通度优化的图的S-T重构问题。构造出一类具有特殊结构的叠图,解决了由两个完全图构成的叠图的基于连通度优化的最优重构问题。

关键词: 颠覆策略, 叠图, 图重构, 连通度优化

Abstract: The concept of subversion strategy and the S-T reconstruction of graphs is proposed, the problem of S-T reconstruction of graph based on connectivity optimization is discussed. A class of overlap graph with special structure is constructed, the optimal reconstruction problem of the overlap of two complete graphs based on connectivity optimization is solved.

Key words: subversion strategy, overlap graph, graph reconstruction, connectivity optimization

中图分类号:

O157

吕臻,魏宗田. 基于连通度优化的图的S-T重构[J]. 《山东大学学报(理学版)》, 2025, 60(12): 156-160.

LYU Zhen, WEI Zongtian. S-T reconstruction of graph based on connectivity optimization[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(12): 156-160.

参考文献

[1] CASABLANCA R M, DANKELMANN P, GODDARD W, et al. The maximum average connectivity among all orientations of a graph[J]. Journal of Combinatorial Optimization, 2021, 43(3):1-28.
[2] HENNING A M, OELLERMANN R O. The average connectivity of a digraph[J]. Discrete Applied Mathematics, 2003, 140(1):143-153.
[3] KIM J, SUIL O. Average connectivity and average edge-connectivity in graphs[J]. Discrete Mathematics, 2013, 313(20):2232-2238.
[4] BEINEKE W L, OELLERMANN R O, PIPPERT R E. The average connectivity of a graph[J]. Discrete Mathematics, 2002, 252(1/2/3):31-45.
[5] SPINOZA H, WEST B D. Reconstruction from the deck of k-vertex induced subgraphs[J]. Journal of Graph Theory, 2019, 90(4):497-522.
[6] MONTEALEGRE P, PEREZ-SALAZAR S, RAPAPORT I, et al. Graph reconstruction in the congested clique[J]. Journal of Computer and System Sciences, 2020, 113:1-17.
[7] OLIVEIRA C I, THATTE D B. An algebraic formulation of the graph reconstruction conjecture[J]. Journal of Graph Theory, 2016, 81(4):351-363.
[8] BONDY J A, MURTY U S R. Graph theory[M]. London: Springer London, 2008.
[9] WHITNEY H. Non-separable and planar graphs[J]. Proceedings of the National Academy of Sciences of the United States of America, 1931, 17(2):125-127.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

本文评价

推荐阅读 10

[1]	庞观松,张黎莎,蒋盛益*,邝丽敏,吴美玲. 一种基于名词短语的检索结果多层聚类方法[J]. J4, 2010, 45(7): 39 -44 .
[2]	王俊新. 几则有限群可解的条件[J]. J4, 2009, 44(8): 35 -38 .
[3]	董新梅 . 函数δk(n)r次方误差项的阶及均值估计[J]. J4, 2006, 41(5): 91 -94 .
[4]	张亚东1,李新祥2，石东洋3. 强阻尼波动方程的非协调有限元超收敛分析[J]. 山东大学学报（理学版）, 2014, 49(05): 28 -35 .
[5]	陈亚娟1,2,尚新春1*. 受热黏弹性球体中空穴的动态生成和增长[J]. J4, 2013, 48(4): 72 -76 .
[6]	闫婷婷,刘仲奎. 余分解维数[J]. J4, 2013, 48(8): 5 -14 .
[7]	潘振宽,魏伟波,张海涛 . 基于梯度和拉普拉斯算子的图像扩散变分模型[J]. J4, 2008, 43(11): 11 -16 .
[8]	杨必成. 一个零齐次核的Hilbert型积分不等式[J]. J4, 2010, 45(2): 103 -106 .
[9]	慕德宇. 离体培养条件下12个白榆优良无性系氯化钠盐分抗性筛选的研究[J]. J4, 2013, 48(3): 19 -23 .
[10]	刘妮. Hilbert空间上算子的(P,Q)外广义逆[J]. 山东大学学报（理学版）, 2014, 49(05): 90 -94 .

基于连通度优化的图的S-T重构

S-T reconstruction of graph based on connectivity optimization

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

多维度评价

本文评价

推荐阅读 10

[1]	常乐,魏宗田. 基于邻域连通度优化的图的N[S]-T重构[J]. 《山东大学学报(理学版)》, 2023, 58(6): 40-45, 76.
[2]	苏贵福1, 徐兰2, 马蓓蓓1. 超双爪无关图的可折叠性[J]. J4, 2010, 45(4): 36-38.