详情

图同构问题和图的广义谱刻画

申报人:徐岩睿 申报日期:2024-11-28

基本情况

2025年度大学生创新创业训练计划
图同构问题和图的广义谱刻画 学生选题
创新训练项目
理学
数学类
教师科研项目选题
一年半期
本项目旨在通过计算机辅助等手段研究图同构问题和图的广义图谱刻画问题

指导教师 主持 上海市启明星项目24YF2709000 酉群和多变量多项式结合方案上的设计

参与 面上项目 12471324 凯莱图的强正则性和距离正则性研究

发表论文

[1] Eiichi Bannai, Yoshifumi Nakata, Takayuki Okuda, Da Zhao, Explicit construction of exact unitary designs, Advances in Mathematics, 2022, 405, 108457.
[2] Eiichi Bannai, Hirotake Kurihara, Da Zhao, Yan Zhu, Bivariate Q-polynomial structures for the nonbinary Johnson scheme and the association scheme obtained from attenuated spaces, Journal of Algebra, 2024, 657, 421-455.
[3] Eiichi Bannai, Manabu Oura, Da Zhao, The Complex Conjugate Invariants of Clifford Groups, Designs, Codes and Cryptography, 2021, 89(2), 341–350.
[4] Da Zhao, Classification of Partially Metric Q-Polynomial Association Schemes with m1 = 4, Graphs and Combinatorics, 2021, 37(1), 183–197.
[5] Eiichi Bannai, Da Zhao, Spherical Embeddings of Symmetric Association Schemes in 3-Dimensional Euclidean Space, Graphs and Combinatorics, 2020, 36(2), 245–250.
[6] Zongchen Chen, Da Zhao, On Symmetric BIBDs with the Same 3-Concurrence, Designs, Codes and Cryptography, 2017, 85(3), 425–436.
[7] Hiroshi Miki, Satoshi Tsujimoto, Da Zhao, Quantum walks on simplexes and multiple perfect state transfer, Journal of Physics A: Mathematical and Theoretical, 2023, 56(46), 465201.
[8] Yaokun Wu, Da Zhao, Three conjectures of Ostrander on digraph Laplacian eigenvectors, The Art of Discrete and Applied Mathematics, 2021, 4(2), P2-08.
[9] Sergey Goryainov, Elena V. Konstantinova, Honghai Li, Da Zhao, Integral Graphs Obtained by Dual Seidel Switching, Linear Algebra and Its Applications, 2020, 604, 476–489.
[10] Eiichi Bannai, Mikio Nakahara, Da Zhao, Yan Zhu, On the Explicit Constructions of Certain Unitary t-Designs, Journal of Physics A: Mathematical and Theoretical, 2019, 52(49), 495301.
[11] Eiichi Bannai, Da Zhao, Lin Zhu, Yan Zhu, Yinfeng Zhu, Half of an Antipodal Spherical Design. Archiv Der Mathematik, 2018, 110(5), 459– 466.

参与 NSFC 面上项目 No. 12471324 凯莱图的强正则性和距离正则性研究
给予文献、计算软件、编程、资金等方面的协助。
校级

项目成员

序号 学生 所属学院 专业 年级 项目中的分工 成员类型
徐岩睿 数学学院 数学与应用数学 2023 阅读论文,讨论研究,撰写论文
陈海彪 数学学院 数学与应用数学 2023 阅读论文,讨论研究,撰写论文
李奕霏 数学学院 数学与应用数学 2023 阅读论文,讨论研究,撰写论文
陈律廷 数学学院 数学与应用数学 2023 阅读论文,讨论研究,撰写论文

指导教师

序号 教师姓名 教师账号 所属学院 是否企业导师 教师类型
赵达 09325 数学学院

立项依据

图同构问题是图论的基本问题,也是算法领域未定复杂度的典型问题。

通过研究图同构问题和广义谱刻画问题,可以进一步发展图同构判定算法。

两个图同构是指存在两个图顶点集之间的双射,其保持邻接关系。

两个图同谱是指两个图的邻接矩阵同谱。

图的广义谱是指包含图的邻接矩阵的凝集构型代数的谱同构。

图的广义谱刻画是指一个图被其广义谱所唯一确定。

图同构问题的经典理论算法是k-Weisfeiler Lehman算法。

Babai证明了几乎所有图被图染色算法确定。

Haemers猜想几乎所有图被其谱所刻画。

王卫等人给出了广义谱刻画的一些判别标准。

本项目提出了广义谱的概念,扩展了谱的定义,用更多的信息刻画了图。

该方法结合了图论,算法理论,复杂度理论和多项式理论,提出了谱刻画的新研究方向。

通过研究图邻接矩阵的凝集构型代数的谱,我们寻找图的不变量。

利用Smith标准型的信息,我们度量一个图距离被其广义谱刻画的程度。

主要解决的问题是广义谱的计算,广义路矩阵的计算。

预期的成果是图的广义谱刻画判别标准,以论文形式发表。

第一阶段阅读文献,理解研究现状。

第二阶段编程计算,证明广义谱的性质。

第三阶段撰写论文,发表并报告。

指导教师对图论、凝聚构型、结合方案等领域有深入的研究,在《Advances in Mathematics》,《Journal of Algebra》等杂志上发表SCI论文11篇。

指导教师主持上海市启明星项目24YF2709000 酉群和多变量多项式结合方案上的设计。对该项目已有初步的研究,正在撰写论文。


已整理相关文献,拥有相关计算软件。

缺少大型计算资源。

计划租用工作站进行计算。

经费预算

开支科目 预算经费(元) 主要用途 阶段下达经费计划(元)
前半阶段 后半阶段
预算经费总额 10000.00 6000.00 4000.00
1. 业务费 10000.00 6000.00 4000.00
(1)计算、分析、测试费 5000.00 租用工作站或者云计算平台资源 3000.00 2000.00
(2)能源动力费 0.00 0.00 0.00
(3)会议、差旅费 5000.00 请教专家、发表成果 3000.00 2000.00
(4)文献检索费 0.00 0.00 0.00
(5)论文出版费 0.00 0.00 0.00
2. 仪器设备购置费 0.00 0.00 0.00
3. 实验装置试制费 0.00 0.00 0.00
4. 材料费 0.00 0.00 0.00

项目附件

结束