论文部分内容阅读
在数学中，图论是研究图的理论.图是离散数学中最重要的研究对象之一，它是用来描述集合元素间二元关系的一种数学结构.一个图是由图中的顶点以及连接它们的边所组成.具体来说，一个图G=(V(G)，E(G))由顶点集合V(G)和边集E(G)构成，其中E(G)中的元素称为边，是V(G)的二元子集.图可以用来描述生物，物理，社会与信息系统中的各种关系和过程，图论中的结果在计算机，社会和自然科学中的许多领域中也有着广泛的应用. 本文主要研究了以下三个方面的内容: 一、两个图论定理的新方法研究 图论中有许多经典的定理与结果，其中蕴含着很多深刻的数学思想和规律，其不同的证明方法往往有助于我们更好的理解定理背后的深刻内涵.Hall匹配定理和Brooks定理分别是图论中的两个重要理论，图的匹配理论和染色理论中最为基础和重要的两个定理.本文用新的方法重新研究了这两个经典的图论定理并分别给出了自己的证明.进一步，本文还对Brooks定理的一个加强猜想做了一些注记. 二、与Murty-Simon猜想相关的一些研究 Murty-Simon猜想是由Murty和Simon提出的一个关于2-边临界图边数的猜想:n个顶点的2-边临界图边数的上确界是「n2/4」且完全二部图K「n/2」，「n/2」是唯一的极图.到目前为止该猜想取得的最好的结果是由Zoltan Füredi于1992年发表的，他证明了Murty-Simon猜想对于充分大的n是成立的.本文对Füredi的这篇文章中的一个关键性引理进行了更加深入的讨论和研究，并对原结论做了推广. 三、与1-2-3猜想相关的一些研究 1-2-3猜想是由Karo(n)ski,(L)uczak和Thomason于2004年提出的一个猜想:可从集合{1，2，3}中对任何一个没有孤立边的图G的边赋权（假设该边赋权函数是w）使得函数f(v)=∑u∈N(v)w（uv）是G的一个正常（点）着色.本文对由1-2-3猜想延伸出来的图的（k，k）-可选问题做了一些研究并对完全图是(2，2)-可选的这个结果给出了一个新的证明.