图嵌入部分对偶的介绍开题报告

1. 研究目的与意义、国内外研究现状（文献综述）

背景：

在数学上，一个图是表示物体之间关系的抽象结构。图是由一个顶点集合和连接这些顶点的直线或者曲线组成的。图是一种自然的结构，在许多科学领域扮演非常重要的角色，例如，有限元分析、海量数据点网格分析。图也常常用来对许多工程问题建模。比如对社会关系网进行建模、网络交换机之间的路由和通信建模、无线网格节点建模、高层计算机视觉对象间关系、城市间的航空线路等。图这种结构广泛存在于各个领域，因此将图的抽象结构可视化将有助于更好地理解对象间的关系。图的曲面嵌入根据亏格的不同可以给出图在球面、欧氏和双曲空间中无边交叉的实现，对于亏格为0的图，可以将其嵌入到球面空间;对于亏格为1的图，可以将其嵌入到圆环面;对于亏格大于1的图，我们将其覆盖空间嵌入到双曲圆盘中。这种对图的量化，也是对于抽象关系的一种量化，有着非常广的应用价值。图的嵌入问题在计算机科学领域有着非常根本的重要性。众所周知，计算图的一个最小亏格的嵌入曲面是np-hard问题。受到代数拓扑的启发，我们发明了一个算法，可以高效单调的减少图嵌入曲面的亏格，并可寻找到称为拟平面图的拓扑曲面。此外，通过使用最前沿的几何工具，比如里奇曲率流（用来证明庞加莱猜想的数学工具），我们可以将普通的图嵌入到正则黎曼度量的曲面上。这种方法是现今解决图的嵌入这一难点问题最好的方法之一。

目的及意义：

2. 研究的基本内容和问题

研究内容：

拓扑图论是20世纪发展迅速而又应用广泛的一门新兴学科,作为图论与拓扑的交叉学科,其核心内容是对图嵌入曲面问题的研究。chmutov引入的部分对偶是对经典的庞凯莱对偶的推广。给定一个嵌入图g，对图g的边集a进行部分对偶g[a],通常g[a]的亏格与g的亏格不一样。本文主要介绍研究介绍，对曲面嵌入的部分对偶进行介绍，了解其相关基本性质等.最后 对曲面嵌入的部分对偶进行编程实现，即考虑g的所有可能的边子集a，计算它的亏格问题。

预期目标：

3. 研究的方法与方案

研究方法：

文献分析法

4. 研究创新点

[1] I. Moffatt. A characterization of partially dual graphs, Journal of Graph Theory, 67(3), (2010),198-217.[2] J. Ellis-Monaghan and I.Moffatt, Graphs on Surfaces: Dualities, Polynomials, and Knots.Springer, (2013).[3] J. L. Gross, T. Mansour and T. W.Tucker,. Partial duality for ribbon graphs, I: Distributions,Euro. J. Combin. 292(4) (2020), 760–776.[4] J. L. Gross, T. Mansour and T. W. Tucker, Partial duality for ribbon graphs, II: Partial-twuality polynomials and monodromy computations, Manuscript, 2020.[5] J. L. Gross, T. Mansour and T. W. Tucker, Partial duality for ribbon graphs, III: A Graycode algorithm for enumeration, J. Alg. Combin., to appear.[6] S. Chmutov, Generalized duality for graphs on surfaces and the signed Bollobás-Riordanpolynomial, J. Combin. Theory Ser. B 99 (2009), 617-638.

5. 研究计划与进展

1. 2020年12月9日-2021年2月24，确定选题，收集整理文献资料；2. 2021年2月24日~2021年3月1日，指导老师下达毕业论文任务书，向学生布置论文工作要求；学生根据任务书要求初步理解毕业论文的目的、要求和任务，准备相关的参考资料；3. 2月24日 ~ 3月8日，完成开题报告，开题报告应按学校规定要求填写。

开题报告应包括研究的背景、目的与意义，研究的内容和预期目标、研究方法及步骤，主要参考文献、进度安排等内容；4. 3月9日 ~ 5月31日，论文写作阶段。

在这期间，每周应向指导老师至少汇报、交流一次论文进展情况；其中 4月13日 ~ 4月26日，毕业论文中期检查，学生重点向指导老师汇报论文进展情况和遇到的困难；5月17日之前，完成论文的初稿；5月18日 ~ 5月31日，毕业论文定稿打印；5. 5月25日 ~ 6月7日，指导老师和评阅老师审阅论文;6. 6月1日 ~ 6月14日，论文答辩。