图论中对称分离问题的研究

论文总字数：19330字

\documentclass[bachelor,nocolorlinks, printoneside]{seuthesis}

\newtheorem{theorem}{定理}

\newtheorem{proposition}{命题}

\newtheorem{lemma}{引理}

\newtheorem{remark}{Remark}

\newtheorem{corollary}{推论}

\newtheorem{defi}{定义}

\newcommand{\be}{\begin{equation}}

\newcommand{\ee}{\end{equation}}

\usepackage{CJK,CJKnumb}

\usepackage{amsmath,amssymb}

\usepackage{amsfonts}

\usepackage{bm}

\usepackage{algorithm}

\usepackage{algorithmicx}

\usepackage{algpseudocode}

\usepackage{subfigure}

\usepackage{appendix}

\usepackage{pythonhighlight}

\definecolor{dkgreen}{rgb}{0,0.6,0}

\definecolor{gray}{rgb}{0.5,0.5,0.5}

\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{frame=tb,

language=Python,

aboveskip=3mm,

belowskip=3mm,

showstringspaces=false,

columns=flexible,

basicstyle={\small\ttfamily},

numbers=none,

numberstyle=\tiny\color{gray},

keywordstyle=\color{blue},

commentstyle=\color{dkgreen},

stringstyle=\color{mauve},

breaklines=true,

breakatwhitespace=true,

tabsize=3

}

\floatname{algorithm}{算法}

\renewcommand{\algorithmicrequire}{\textbf{输入:}}

\renewcommand{\algorithmicensure}{\textbf{输出:}}

\begin{document}

\categorynumber{000}

\UDC{000}

\secretlevel{公开}

\studentid{07115116}

\title{图论中对称分离问题的研究}{}{Research on Symmetric Separation in Graph Theory}{subtitle}

\author{周煜}{Zhou Yu}

\advisor{沈斌}{教授}{Shen Bin}{Prof.}

\major[12em]{数学与应用数学}

\defenddate{答辩日期}

\authorizedate{学位授予日期}

\department{数学}{department name}

\duration{2019年1月1日——2019年5月30日}

\address{东南大学数学学院}

\maketitle

\begin{abstract}{图论，对称，拉姆塞数，奇偶划分，拉姆塞指标}

Ramsey问题是离散数学、组合数学、图论、算法领域的著名难题。Ramsey 理论在各数学分支上均有着举足轻重的地位，而求解或估计Ramsey数更是其中的热门课题。

本文着眼于对角线Ramsey数，通过Ramsey指标这一概念对Ramsey数做下界估计。分类讨论，探讨其在解决Ramsey问题中的作用。\\

\indent 本文通过从对称分离角度研究完全图的分离问题，从而讨论对角线Ramsey数。针对各完全图做归纳讨论，探讨这一方法在解决Ramsey问题中的作用。首先，介绍Ramsey理论相关的背景，然后引出Ramsey 指标的定义。然后，详细研究一阶Ramsey指标及证明相应结论。最后，研究出现的奇异整数值并引入二阶Ramsey指标，完善不足之处。

\end{abstract}

\begin{englishabstract}{Graph Theory, Symmetry, Ramsay number, parity division, Ramsay index}

Ramsey problem is a well-known problem in the fields of discrete mathematics, combinatorial mathematics, graph theory and algorithm. Ramsey theory plays an important role in various branches of mathematics, and solving or estimating Ramsey number is a hot topic among them.This paper focuses on the diagonal Ramsey number and estimates the lower bound of Ramsey number by the concept of Ramsey index. Discuss the role of Ramsey in solving Ramsey problem.\\

\indent In this paper, we discuss the diagonal Ramsey number by studying the separation of complete graphs from the perspective of symmetric separation. In this paper, we summarize and discuss each complete graph, and discuss the role of this method in solving Ramsey problem. Firstly, the background of Ramsey theory is introduced, and then the definition of Ramsey index is introduced. Then, the first-order Ramsey index is studied in detail and the corresponding conclusions are proved. Finally, the singular integer values are studied and the second-order Ramsey index is introduced to improve the shortcomings.

\end{englishabstract}

\tableofcontents

\begin{Main}

\chapter{绪论}

\section{引言}

图论中有一个有趣的问题：世界上任意6个人中，总有三个人相互认识，或者相互不认识。这就是著名的R(3,3)=6。它由英国逻辑数学家Frank Plumpton Ramsey在1930年提出并解决的。\\

\indent 事实上，用6个点代表6 个人，他们是$\upsilon_1, \upsilon_2, \upsilon_3, \upsilon_4, \upsilon_5, \upsilon_6$，两人相互认识时，在两者之间连一条绿色边，否则连一条红边。由鸽笼原理，与$\upsilon_1$相连的五条边之中，必有三条边是同色的，不妨设$\upsilon_1\upsilon_2, \upsilon_1\upsilon_3, \upsilon_1\upsilon_4$是三条绿色边，考虑$\delta\upsilon_2\upsilon_3\upsilon_4$。如果这个三角形上有一条绿边，则此绿边与$\upsilon_1$连接的两条绿边构成一个绿色三角形，于是有人彼此相识；

否则$\delta\upsilon_2\upsilon_3\upsilon_4$是红色三角形。于是又三人彼此不相识，可见$R(3,3)\le 6$。而五个人的人群，可能既无绿色三角形亦无红色三角形，故$R(3,3)gt;5$，所以R(3,3)=6。\\

\indent Ramsey数的计算是对人类智力的挑战。Erdos曾用如下比喻说明其困难程度：一伙外星人入侵地球，要求一年内求得R(5,5)，否则将灭绝人类！那么也许人类能集中所有计算机和专家来找出它以自保；但如果外星人问的是R(6,6)，那么人类将别无选择，只能拼死一战了！

\section{背景知识}

\subsection{图}

称数学结构$G=\{V(G),E(G),\psi_G\}$为一个图，其中V(G)是非空集合，$\psi_G$是从集合E(G)到$V(G) \times V(G)$的一个映射，则称G是一个以V(G) 为顶集合。以E(G)为边集合的有向图，V(G)中的元素称为图G的顶点，E(G)中的元素称为G的边，$\psi_G$称为G的关联函数。若$\psi{_G}(e)=(u,v)$，$e\in E(G)$，$(u,v)\in V(G)\times V(G)$，则简写成$e=uv$；称u是有向边e的尾，v为有向边e 的头。若$|V(G)|=\nu$，$|E(G)|=\varepsilon$，$\nult; \infty $，$\varepsilonlt; \infty $时，称G为有限图，否则为无限图。只有一个顶点而无边的图称为平凡图，其他所有的图都称为非平凡图。边集为空的图称为空图。图G的顶点数和边数可分别用符号n(G)和m(G)表示。连接两个相同顶点的边的条数，称为边的重数。重数大于1的边称为重边。端点重合为一点的边称为环。既没有环也没有重边的图称为简单图。其他所有的图都称为复合图。\\

\indent 边记为uv，也可记uv为e，即e=uv。此时称u和v是e的端点，并称u和v相邻，u(或v) 与e相关联。若两条边有一个共同的端点，则称这两条边相邻。

\subsection{Ramsey理论}

Ramsey理论是组合数学中的一个重要分支，它在通信、计算机等方面有一系列的应用。\\

\indent 1834年，德国数学家迪利克雷提出了鸽笼原理，其可以简单地描述为：有n 1只鸽子，飞进n个鸽笼是，至少有一个鸽笼内有两只鸽子。\\

\indent 时隔一百年，英国数学家F.P.Ramsey在其论文《形式逻辑上的一个问题》中提出了Ramsey定理，并且证明了R(3,3)=6。\\

\indent 受限于Ramsey的英年早逝，Ramsey理论的发展较为缓慢，直到数年之后出现两位匈牙利数学家Paul Erdos和 George Szekeres重新发现了这一定理。这两位数学家从集合论的观点出发，发现了著名的集合Ramsey 问题。\\

\indent 经过数十年的发展，Ramsey理论从最初孤立的几个定理逐渐发展成一个庞大的数学分支，Ramsey数是其中一个很重要的研究对象，研究它有重要的意义。

\subsection{Ramsey定理}

对任意给定的自然数r，k以及$q_1,q_2,...,q_k\ge r$，都存在$n(r,q_1,q_2,...,q_k)$，当$n\ge n(r,q_1,q_2,...,q_k)$时，对$\{1,2,...,n\}$的所有r元集的任一种k染色，必有一个$i\in \{1,2,...,n\}$，使得$\{1,2,...,n\}$有一个$q_i$元子集，它的所有r 元集是同一种颜色的。

\subsection{Ramsey数}

给定正整数a和b，令R(a,b)是保证任意的n阶图中必存在a个点的团或存在b个点的独立集的最小n值，则称R(a,b)为Ramsey数。其中，称R(a,a)为对角线Ramsey 数，并将其简记为R(a)。\\

\indent Ramsey数有几个等价定义：

\begin{itemize}

\item 任意n个人中必存在a个人相互认识，或b个人相互不认识。

\item 对任意n阶图G，要么G中存在含a个点的团，要么G的补图中含b 个点的团。

\item 对$K_n$的边用两种颜色任意染色，使得着色后在其子图中，或存在一个1色$K_a$，或存在一个2色$K_b$。

\end{itemize}

\subsection{广义Ramsey数}

给定无孤立点的简单图$H_1,H_2,...,H_s$，令$r(H_1,H_2,...,H_s)$是最小的正整数n，使得对$K_n$的任意一个s边着色，着色后在$K_n$的子图中必存在一个i色$H_i$，其中$1\le i \le s$。 称$r(H_1,H_2,...,H_s)$为广义Ramsey数。

\section{研究目的}

目前对于Ramsey数的研究多集中在广义Ramsey数和一些特殊图的Ramsey 数，对于经典Ramsey数的研究已经陷入停滞，经典Ramsey数的求值是Ramsey理论中一个十分困难且重要的问题。时至今日，

对于R(5,5)的精确值都尚未确定，它的上下界已经很久没有改变。\\

\indent 由于Ramsey数用传统方法研究起来太过困难，所以人们采用计算机来研究Ramsey数，常见的算法有DNA遗传算法和模拟退火算法。DNA遗传算法是一种基于DNA与某些生物酶的反应原理所

提出的一种新型分子生物计算方法。首先生成一个初始数据池，然后用一系列的DNA操作来删除不正确的解，最后通过DNA检测操作把正确的解检测出来。模拟退火算法起源于对固体退火的模拟，由

加温、等温、冷却三个过程构成。由于其具有严密的数学基础，且全局收敛性已得到严格证明，故被用来求解Ramsey数。\\

\indent 本文通过研究对称分离问题来研究对角线Ramsey数的下界，从分布在单位圆上的对称的完全图出发，目的是进一步提升对角线Ramsey数的下界，以期最终完全得到对角线Ramsey 数。\\

\indent 首先，我们取n个点，然后让它们对称分布在单位圆上，接着将各个点两两相连，即得到一个对称分布的完全n阶图。本文的所有讨论均是基于此图。为了叙述方便，

我们现引入Ramsey指标这一概念：

剩余内容已隐藏，请支付后下载全文，论文总字数：19330字