两个组合问题的介绍开题报告

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

研究背景：图论起源于18世纪东普鲁士的柯尼斯堡，距今已有200多年的历史。虽然图论的大多数问题是围绕游戏出现的，但如今不仅应用于自然科学，也应用于社会科学。例如其连通性理论广泛应用于电信网络、开关理论、计算机程序设计、印刷电路板设计图论中图的连通性探究的问题比较广泛，例如利用对图的关联矩阵来研究探讨有向图的连通回路；图的研究中还有一个著名的四色问题，通过对地图着色的定理的研究，又引出了对图的嵌入的研究，20世纪80年代到90年代，由物理学家们发展起来的二维量子引力的所谓的“随机矩阵”方法，“随机矩阵法”始于1974年诺贝尔奖获得者Gerardt'Hooft's从强核相互作用的研究中发现，矩阵积分与绘制在表面上的图自然相关，并根据其拓扑进行加权。1978年，物理学家Brezin，Itzykson，Parisi和Zuber把Gerardt'Hooft's的第一个例子变成了列举地图的一般范例。通过他们的方法，他们恢复了加拿大数学家威廉·塔特(William Tutte)在20世纪60年代早期得出的一些关于计算球面上三角形或四边形的数量的结果。多年来，人们知道如何从平面到平面到一个不可思议的美丽几何数量，现在仍然在继续。“拓扑递归”方法于2004年被发现，并于2007年被推广为几何不变量的数学理论，它以某种方式将平面块粘合成更高的拓扑曲面。研究目的：此课题主要是总结介绍组合一：利用图的关联矩阵来探讨有向图中的连通图的性质与应用、计算有向图中连通图回路及独立回路数量的一些问题研究和证明；组合二：总结距离举例地图映射的几种定义，总结介绍用于计数地图的几个函数，重新推导图特方程以达到对地图和离散曲面知识规整清晰和理解。

研究意义：组合一：利用关联矩阵来研究连通图的性质与应用，不仅在理论上便于利用代数知识研究图的性质，构造算法;而且也便于计算机处理；在一些实际问题中也需要用到有向图的关联矩阵来表述它的回路、寻找“独立”回路，在图论的应用中具有极其重要的意义；组合二：在Brezin、Itzykson、Parisi和Zuber之后，物理文献中从来没有明确地给出一个形式矩阵积分的精确定义，但它总是隐含地假设;事实上，在费曼之后的物理学中，所有的积分都被视为形式积分，它深深浸透在物理学家的文化中，以至于大多数物理学文章都不在意提及它，这当然是令人困惑的，有时会导致误解和错误的陈述。

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

研究内容：

(1)探讨证明有向图的关联矩阵a的秩r(a)、核n（a）、值域 r(a)、上核n（a^t）和上值域 r（a^t）的维数与有向图g的连通性的关系。

（2）利用关联矩阵a^t的列向量的整系数线性组合来寻找表示连通图的回路。并从连通图的所有回路中找出“独立”的回路并加以证明。

3. 研究的方法与方案

研究方法：

（1）文献研究法。

（2）归纳总结法。

4. 研究创新点

[1] bollobas b.gragh theory:an introductory course[m].graduate texts in mathematics,vol.63,spring-verlag,new york,1993.

[2] c.berge,the theory of graphs(dover,newyork,2003.

[3] w.t. tutte, a census of planar maps. can. j.math.15, 249–271 (1963)

5. 研究计划与进展

1.2020.11.15—2021.01.04 确定选题，收集资料

2.2021.01.05—2021.02.28 资料索引，阅读资料

3.2021.03.01—2021.03.18 完成开题报告