图论与拓扑、图论与代数交叉问题的案例研究

河北师范大学硕士学位论文图论与拓扑、图论与代数交叉问题的案例研究姓名王献芬申请学位级别硕士专业应用数学指导教师邓明立20070405河北师范大学硕士学位论文摘要在数学科学内部，不同学科分支之间思想和方法相互交叉、彼此渗透是数学科学发展的一大重要趋势；本文围绕这一中心思想，选取图论与拓扑、图论与代数的交叉问题作为主要案例，尝试以一些典型问题作个案分析，从历史发展观的角度，对每个问题采用时序分析，遵循思想演绎规律，探讨了这种交叉融合发展到一定程度将导致重大发现，甚至交叉学科的产生；指出交叉问题的历史研究对阐明数学的发展规律有特殊意义；同时笔者认为，这种通过数学内部的因素交叉问题来分析数学学科发展的动力，是数学史研究中的一个新的分析方向。在具体内容上，全文共分四部分，其中第一部分从多面体公式到欧拉一庞加莱示性数，考察了这一过程是怎样超越了度量观念，又是如何朝向拓扑发展的；第二部分介绍从GUTHRIE问题到HADWIGER猜想的思想演变，考察了染色问题的两条发展路线；一方面由于曲面拓扑特征的考虑，从而导致着色数理论的形成，对拓扑图论的发展起着重要的里程碑意义；另一方面剖析了WAGNER定理引发HADWIGER提出著名猜想的关键性因素，首次指出“缩图”GRAPHMINOR的引入开拓了研究染色问题的新视角，从而使染色问题得到进一步区分和一般化。这两部分均属于图论与拓扑交叉问题的范例；第三部分介绍回路的代数化思想，阐述了在回路基础集构造方面，代数工具和代数方法不断深入的过程，以及这个过程如何促使惠特尼最早引入了拟阵1935年。第四部分从最简单的图树及其早期计数开始描述，直到波利亚计数定理的提出，这是一个与置换群的思想相联系的理论，为进一步研究其所蕴含的交叉思想给出了一个良好开端回路的代数化、树的计数理论的发展是关于图论与代数的两个经典问题。从整体上看，这四部分合起来论述了数学科学内部学科的交叉渗透的演化趋势，同时考察这些交叉问题的历史背景和发展过程也是体现数学统一性的一个重要方面，对深刻理解现代数学交叉渗透的趋势是很有价值的。关键词多面体公式欧拉庞加莱示性数GUTHRIE问题HADWIGER猜想WAGNER定理缩图GRAPHMINOR回路基础集波利亚计数定理河北师范大学硕士学位论文ABSTRACTTHEREALEINFLIEATIONALWAYSOFTHINKINGBETWEENDIFFERENTDISCIPLINESINMATHEMATICALSCIENCE,WHICHISALLIMPORTANTTENDENCYINTHEDEVELOPMENTOFMATHEMATICSTHUSTHEDISSERTATION,WITHTHISTENDENCYASTHECENTERFOCUSESONTHECASESTUDIESOFPROBLEMSOFOVERLAPBETWEENGRAPHTHEORYANDTOPOLOGY。硒WELLASGRAPHTHEORYANDALGEBRAINVIEWOFHISTORICALDEVELOPMENT,THEPRESENTPAPERSTUDIESTHATTHEKINDOFOVERLAPPINGFUSIONMAYCALLSTHESIGNIFICANTDISCOVERIES，CVGN嬲EMERGENCEOFINTERDISCIPLINESUSINGTHESUCCESSIONANALYSISTOEACHQUESTIONANDFOLLOWINGTHEDEDUCTIONRULESITHASTHESPECIALSIGNIFICANCETOEXPOUNDEDMATHEMATICSLAWOFDEVELOPMENTCONCRETELY,THEDISSERTATIONCONSISTSOFFOURPARTSHOWTOSURMOUNTTHEMEASUL峙IDEA,ANDHOWTOFACETOWARDSANALYSISSITUSAREOBSERVED,DURINGTHEFISTPARTFROMPOLYHEDRALFORMULATOEULERPOINCAR6SNUMBERINTHESECONDPART,THEEVOLUTIONFROMGUTHRIESQUESTIONTOHEDWIGERSCONJECTUREISINVOLVED，PARTICULARLYANALYZINGHOWWAGNERTHEOREMINITIATEDHUGOHADWIGERTOPROPOSETHEFAMOUSCONJECTURETHEREINSPECTESTHECOLORINGQUESTIONFOLLOWINGITSTWODEVELOPMENTROUTES；ONTHEONEHAND，CURVEDSURFACESHOWINGTOPOLOGICALCHARACTERISTICISCONSIDEREDASARESULTOFTOPOLOGICALINVESTIGATION，THECHROMATICNUMBERTHEORYISBEINGFORMED，WHICHISAMILESTONEINTOPLOGICALGRAPHTHEORYITSHOWSTHAT，ONTHEOTHERHAND，THEINTRODUCTIONOFGRAPHMINORHASDEVELOPEDNEWVISIONSFORFUTURERESEARCH,THUSTHECOLOURINGQUESTIONCANOBTAINTHEFURTHERDISCRIMINATIONANDGENERALIZATIONTHEFIRSTTWOPARTSALETHEEASESOFPROBLEMSOFOVERLAPBETWEENGRAPHTHEORYANDTOPOLOGYPARTIIIISBASEDONTHEALGEBRAOFCIRCUITS，EXPLAININGHOWAFUNDAMENTALSETOFCIRCUITSMAYBECONSTRUCTEDANDHOWTOINFUSEALGEBRAIDEASINTOTHESTUDYOFGRAPHS，ANDHOWTOINITIATEWHITNEYPRESENTMATROID1935THATISAFMEBEGINNINGFORFURTHERSTUDYINGTHEREINTRODUCESONETHEORYWHICHRELATESTOTHEPERMUTATIONGROUPFROMCOUNTINGTREES，THESIMPLESTGRAPHS，TOPDLYASENUMERATIONTHEOREMINPARTWTHEALGEBRAOFCIRCUITSANDCOUNTINGTREESARETWOCLASSICALQUESTIONSABOUTTHEGRAPHTHEORYANDALGEBRATHESEFOURPARTSASAWHOLEILLUSTRATEINFLIEATIONALWAYSOFTHINKINGBCTWEANDIFFEREMDISCIPLINESINMATHEMATICALSCICUCE,ITALSOINSPECTSTHAT,SIMULTANEOUSLY,THEHISTORICALPERSPECTIVEANDTHEDEVELOPINGPROCESSOFTHESEOVERLAPPINGQUESTIONSMANIFESTSUNIFICATIONOFMATHEMATICSITISVALUABLETOUNDERSTANDTHETENDENCYOFIDEOLOGICALINFILTRATIONOFMODERNMATHEMATICSKEYWORDSPOLYHEDRALFORMULAEULERPOINEARDNUMBERGUTHRIESQUESTIONHADWIGERSCONJECTUREWAGNERSFUNDAMENTALSETOFCIRCUITSTHEOREMGRAPHMINORPDLYASENUMERATIONTHEOREM学位论文原创性声明本人所提交的学位论文图论与拓扑、图论与代数交叉问题的案例研究，是在导师的指导下，独立进行研究工作所取得的原创性成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中标明。本声明的法律后果由本人承担。论文作者签名王雨暖笋伽7年年月FFI学位论文原创性确认书学生三趑莶所提交的学位论文图论与拓扑、图论与代数交叉问题的案例研究，是在本人的指导下，由其独立进行研究工作所取得的原创性成果。除文中已经注明引用的内容外，该论文不包含任何其他个人或集体已经发表或撰写过的研究成果。艚教师签鼽甜彬劲即7年争月，日河北师范大学硕士学位论文引言1736年，欧拉L60NARDEULER,17071783解决了著名的哥尼斯堡七桥问题，他关于此问题发表的那篇文章成为图论历史上第一篇研究文献1，标志着图论的开始。从此，一系列游戏问题不断得到解决，且基本上呈现出两种特征第一，它们存在或产生完整而严密的结论；第二，可以在精确的数学思想之下创立理论。这样，令人惊奇的有深度的理论结果逐渐丰富多彩起来，这个过程孕育了大量数学思想，从而使得从离散的问题到系统的数学成为可能。1936年，D6NESK6NIG第一个系统阐述了图论的知识，为图论写了第一本著作2，从此图论作为一个独立的学科分支屹立于数学世界。实际上，图论问题的解决通常渗透着数学与其他学科分支的思想与方法，其所涉及的知识常常是跨越学科的。当今图论已迅猛发展成一门重大应用数学学科，受到了学界的广泛研讨和关注，其影响力跨越了数学内部和外部学科。在数学领域内部，研究图论与组合计数、图论与数论、图论与线性代数、图论与群论、图论与拟阵、图论与拓扑、图论与几何、图论与分析、图论与概率以及图论与纽结理论等相互关系的文章汗牛充栋；另一方面，它超越数学内部，直抵今日众多热门的科学研究领域如计算机、通讯工程、国际金融、人工神经网络等等，同时也渗透至日常生活领域这是由于一个图本身表示了一种模式关系3。图论与其他学科的这种极强的交叉融合性是图论迅猛发展的思想根源之一。然而与此同时，这种交叉融合却困惑着那些想系统研究图论史的人们。那么对于图论问题本身的交叉特点，我们将做出什么样的反馈呢由此，笔者尝试从交叉渗透的思想角度剖析问题，考察、比较图论与其他学科相关的问题，对它们进行个案分析，从而形成深刻的见解和较为完整的认识。所以立足交叉是本文的一条主线。这同时也为数学史研究提供了一个新的分析方向。笔者的基本思路是，围绕数学的交叉渗透这一中心思想，选取图论和拓扑以及图论和代数相关的问题为具体内容，提炼史料加以考察、分析和综合说明。因此放弃了描绘图论从产生至发展的完整历史图景的企图，而是有意识地在一些典型的交叉问题上寻找历史线索，并分析和论证这些因素是怎样促进图论某些方面的发展，乃至交叉学科的产生。而这本身也是对图论发展趋势的一个历史考察。具体说来，文章第一部分取材于多面体公式的发展，提炼史料并分析从发表。LEULCR,THCSOLUTIONOFAPROBLEMRELATINGTOTHEGEOMETD,OFPOSITION,COMMENTARIIACADEMIAESCICNTIARAMIMPERIALISPAMPOLITAN卵8F17362KONIG,DTHEODEDERENDLICHENUNDUNENDLICHENGRAPHEN，AKEDEMISCHEVERLAGSGESELLSEHATLLEIPZ垴1936REPRINTEDCHELSEA,NCWYORLL950LOWELLWBEINEKE,ROBINJWILSON,GRAPHCONNECTIONS,OXFORDCLARENDONPRESS,19971河北师范大学硕士学位论文这一公式到获得欧拉庞加莱示性数的发展过程，考察这一过程是怎样超越了度量观念，又是如何朝向拓扑发展的。由于拓扑思想融入多面体问题1750年开始于图论诞生1736年之初，所以笔者将此作为图论与拓扑交叉融合的第一个范例；第二部分介绍从GUTHRIE问题到HADWIGER猜想的思想演变。经考察发现，几乎所有这方面的研究史料都提到了下面的事实，即1937的WAGNER等价定理引发了HADWIGER提出著名猜想；然而却都没有进一步剖析使思想发生质的飞跃的根本原因。所以为挖掘潜在的思想本质，一方面需要详细考察并借鉴先辈们已获得的结论，另一方面需要查阅大量相关的历史文献，特别是要考察WAGNER发表其定理的那篇文章，以及与之有关的一些论文；这也是本文尝试做的一个工作，以试图找到最本质的思想因子。经分析笔者认为使GUTHRIE问题到HADWIGER猜想的推广成为可能，关键在于缩图GRAPHMINOR概念的引入，并且这也为染色问题、乃至整个图论的研究开创了一个新视角。此为本节研究的难点所在。另外，由于HADWIGER猜想是GUTHRIE问题的推广，所以只有对四色定理本身的正确性不再产生疑义时，研究这个推广才更具一般性意义，所以本节专门就C,UTHRIE四染色问题的两次机器证明给予了探讨，借助1994年国际数学家大会上关于此问题的1小时报告澄清了四色定理正确的事实。在该节末尾，笔者认为有必要概述一下HADWIGER猜想的研究现状，并根据当前学术动态，分析其研究进路；接着简要说明了解决问题的三个阶段及每个阶段的方法进路，笔者认为，这个结论具有普遍意义，类似这方面的探讨将可能成为数学史研究者与数学家交流互动最为密切也尤为必要的主题之一。以上两个问题均属于图论与拓扑交叉的范围，而第三、四个则是图论与代数思想融合的案例。第三部分阐述回路的代数化思想，代数工具和方法广泛地应用到了回路基础集的构造方面，这种思想很好地被惠特尼掌握了，促使他最早发现了拟阵1935年。第四部分从最简单的图计数树的早期发展开始描述，直到波利亚计数定理的提出，这是一个与置换群的思想相联系的理论，为进一步研究这种渗透给出了一个良好开端可见，除第二部分较为特殊外，其他三部分将时间段选取在了17361936年间。在交叉问题的选取上也是仁者见仁，因为我们不需要也不可能将所有的交叉问题囊括进来，不过只要立足交叉，就会殊途同归宏观整体上都能从一个侧面扼要地盐析出交叉渗透的趋势；具体案例上，像刚才所言，每个问题也都能得到深刻的理解和较为完整的认识显然这种思考的角度和方法也避免陷于不可能完成的宏大叙事之中。不过，这种研究方式也有其本身的复杂性，需要努力去挖掘一些因之前不受重视而缺乏记载的史实。此外，所选问题之间的相互独立性似乎很容易造成在言语表述上的涣散，笔者试图克服这个困难的努力也是本文引言的目的之一。2河北师范丈学硕士学位论文1从多面体公式到欧拉庞加莱示性数凸多面体的欧拉示性数，也称欧拉公式，即任何多面体，都有顶点数一棱数面数2成立，它是第一个实质性的反映拓扑性质的拓扑不变量。1750年欧拉发表了这个公式及其证明，在此之前，笛卡尔DESCARTES，REN6，15961650在1640年也知道这个公式，莱布尼兹LEIBNIZ，GOTTFIIEDWILHELM,16461716亦有一份手稿的抄件，但到1859年才为数学史家知道【11。有些数学史家认为，阿基米德ARCHIMEDES，约BC287一BC212很可能也知道这个公式，因为归根结底，古希腊对多面体有相当研究。不过，这些研究都没有涉及其拓扑不变性，虽然直到19世纪末，欧拉公式基本上都在多面体的几何学框架中加以讨论。但是笔者认为，从交叉思想的渗透过程来看，1750年欧拉发表这个公式，开始了在图的研究中进行拓扑思考，直到1895年庞加莱HENRIPOINCAR6，18541912在位置分析中得到欧拉一庞加莱示性数这段时期，是拓扑思想逐步深入到这一问题的演化过程，考察这段有意义的历史，有助于理解学科之间交叉渗透的作用。11欧拉发现多面体公式超越度量观念从古希腊时期到十八世纪中叶，多面体研究一直未能突破度量的层面，面积、周长和体积等的测量从来就是备受关注的目标。数学家们试图对几何体以及几何图形的“量”给出一般的原则，即确定实体的度量性质。他们在直接走向这样一个目标的时候，有时会发现一些无助于测量的明显结论，在这些明显似乎又很平凡的结论中，数学家逐渐超越了度量观念，他们取得了思想上的重大突破，开始在图形研究中进行拓扑思考，使得图论和拓扑增强了各自研究所要求的观点的广度和技巧的范围。并且，这种“增强”不是以削弱和取代原来的学科为代价的，而是使学科发展相得益彰。我们知道，有关多面体的研究可以上溯到四千年以前的古埃及金字塔时期，但是，这里我们从大约2000年之前的古希腊讲起古希腊数学家尤其对正多面体的性质感兴趣。他们发现只存在五种正多面体一正四面体、立方体、正八面体、正十二面体和正二十面体【11。THEACTETUS于公元前369年去世曾给出完整的论述，从那里我们知道了ELEMENTOFEUCLID最先开创了多面体的研究。然而奇怪的是，并无任何迹象表明古希腊人是否知道顶点、边和面三者关系的这个简单公式，即顶点数一边数面数2。历史上曾存在两种说法【L】第一、他们可能曾经发现了这一公式，但在接下来的岁月里却遗忘了。据说ALEXANDIA47BC的一次火灾导致了古希腊许多学术研究不复存在，特别是阿基米德的一些手稿因此遭到了破坏。阿基米德是古希腊最伟大的思想家之一，他在多面体方面有着相当的3河北师范大学硕士学位论文研究。不过，这种推测不免带有某种趣味性。一般地，历史学家更倾向于第二种观点古希腊人并没有发明上面所述的公式。因为古希腊数学家关于几何体的研究兴趣多集中在测量问题上，比如角度，侧边长度以及面积、体积的大小等；他们仅仅关心多面体的度量性质，即使注意到度量性质以外的其它方面，最多也是无意识的发现；而多面体公式VEF2中，符号V、E和F不是“有关量度的记号”，它们分别指代顶点数、边数和面数，这显然属于多面体的拓扑特征，而实际上这三个量之间的函数表达式内蕴了一种拓扑不变量。诚然，任何一种数学思想及其相关的重要概念和方法，它们都生长在一定时期的数学文化土壤上，并且离不开数学家的真知灼见。大约在1640年，分析几何的创立者笛卡尔曾给出了这样一个表达式，用它可以来计算多面体所有面的平面角的个数之和；这个事实可以从笛卡尔的文集4V0110，PP257277】里得知。根据笛卡尔的表达式，我们现在很容易就能推导出欧拉关于顶点、边和面的关系式。然而，笛卡尔却没有直接迈向我们现在所谓的多面体公式。这与笛卡尔本人以及笛卡尔所处的数学文化背景不无关系。在笛卡尔对数学的认识观里，“所有那些目的在于研究顺序和度量的科学，都和数学有关”21，显然他把数学紧密地与研究顺序和度量的科学联系起来。再回到笛卡尔那个时代，“科学久已迫切需要的，而且在17世纪一直公开要求着的数学设备，这设备就是数量的工具”【21。那么，数量的工具对于几何对象一个明显的价值，就在于用以寻求其度量属性。无论如何，笛卡尔研究多面体没有超越度量，他可能习惯于运用量度概念思考问题了，或许正因如此也导致了他没有明确提出多面体公式。更令人遗憾的是，他关于多面体问题的那些手稿，直到1859年才被揭晓并发表出来11，而当他的工作得到明鉴时，他差点儿发现的公式早已经众所周知了伟大的数学家欧拉于1750年发现并发表了多面体公式【31。不过，笛卡尔的贡献是值得肯定的，所以，今天为了纪念这两位伟大的数学家，我们有时也称多面体公式为EULERDESCARTES公式。笔者认为，欧拉发现多面体公式，从此开创了在图形研究中进行拓扑思考。正如20世纪数学思想所评价的那样，“第一个实质性的反映拓扑性质的拓扑不变量是凸多面体的欧拉示性数”。14事实上，欧拉最早是以信件的形式将这个公式公布于众的。1750年，欧拉在给哥德巴赫OOLDBACH,CHRIGEAN,16901764的通信这封信一半是德文。另一半是拉丁文，全部内容收藏在EULERGOLDBH的通信中中【51，在那里他阐述了研究多面体的一些结论I，令面的数目H4ADAM,CANDTANNCRY,EOEUVRESDEDC咖CEFPARIS,189719134河北师范大学硕士学位论文、多面体图形的】页角数目S、两个面相交形成的线，称之为“棱”或“边”EAGES竹，其数目A、所有面的侧边SID鼯的数目总和LV、所有面的平面角的数目总和PL，因为在每个平面内，角的数目等于侧边数目，所以在上述五个量中，显然有PL。2，因为两个相交面的交线是这两个面的公共侧边，所以AO2L,或AI2P恒成立。3，显然，P和L总为偶数。4，L3H。或L3H；5，P3S威P3S结论4和5是显然的，这是因为，至少需要3条侧边才能围成一个平面，即任意平面的侧边数至少是3，而任意立体图形的顶角也至少有3个平面角构成。但对于下面的推测，我还没有给出一个完整的、令人满意的证明6，在每个由平面围成的立体图中，面数与角的数目总和要比边数大2，即HSA十2，或HS气L2L2气12P2；11，平面角的数目总和要比多面体顶角数目的4倍少8，即等于4S8。，接着欧拉以三棱镜作为一个具体的实例加以说明，他在文章最后还为自己的发现有所感慨，并诙谐地写道，“在立体几何中，如此显而易见的一般结论却一直没有人发现，这令我很惊讶，更让我困惑的是，定理6和定理11的证明又是非常艰难，我现在还没有得到一个满意的证明”嘲。由此我们不难推测，欧拉并不知道笛卡尔的工作，另外，前面也曾提到过，笛卡尔的手稿直到1859年才发表出来，所以，欧拉独立发现了多面体公式。数学家的一贯严谨使他们对自己的新发现和未能证明的部分，常常不会轻易就选择放弃的。1752年，欧拉写了两篇关于多面体公式的文章，在第一篇论文中5，他用几组几何体验证他发现的公式，但他宣布自己仍未能找到一个一般的证明。在第二篇文章中6，欧拉声称经过认真剖析后得到了证明。他的做法是这样的，将每个多面体恰好切割成一个个四面体，切割过程中保证VEF的值不变，直到最后只剩下一个四面体为止，此时，VEF2。这是一个极具创意的方法技巧，同时也是前所未有的十分恰当的方法一完全抛开了多面体的度量属性。所以，这是思想观念的第一次重要突破。但是，欧拉的剖析具有一定局限性，他所谓的证明也是不充分的。欧拉包括他之前的研究多面体的数学家，他们都忽略了一个重要特征，那就是多面体的凸5EULCR,LELEMENTADOETRINAESOLIDORUMNOVICOMMACADSEIIMPPETROP01417523,PUBLISHED1758，109140OPERAOMNEA”VOL26，7293。EULER,LDEMONSTRATIONONNULLARUMINSIGNIUMPROETAUIMQUIBUSSOLIDAHEDRISPLANISINCLUSASURLTPRAEDI饥NOVICOMMACADSCIIMPPETROPOL417523，PUBLISHED1758，140160OPERAOMNEA1，VOL26，941085河北师范大学硕士学位论文性CONVEXITY。一个多面体是凸的或凸状的CONVEX，如果对于XES，YS即【，Y是S的两个顶点，X和Y的所有线性组合仍在S中。早在古希腊时代，数学家们就知道并证明了多面体的这一特性，但并没有得到广泛应用。1619年I“，天文学家开普勒KEPLER，JOHANNES，15711630描述了一个非凸状NONCONVEX多面体，然而这样的多面体研究不属于我们考虑的范围之内，有兴趣的读者请参见WENNINGER的著作LOL。第一个给出欧拉公式一个完整证明的是法国数学家勒让德LEGENDRE，AM，17521833。1794年7，勒让德利用球多面体的度量性质证明了欧拉多面体公式。他的思想很大程度上类似于笛卡尔，二人均未能超越度量性质的思考层面。不过，勒让德比笛卡尔更清楚自己想要证明什么，因而前者利用度量方法明确得到了这一结果的论证。事实上，欧拉所发现的是仅对所有闭的凸多面体都适用的一个性质，他对这一关系感兴趣主要是想要用它来做多面体的分类【L7】，但他本人并没有想到连续变换下的不变性，也未能确定出满足这类关系的这类多面体17】。笔者认为，要理解公式内蕴的本质特性，“连续变换下的不变性”的考虑是相当重要的，至少是类似的思想如多面体的投影方法，在历史上，这种把多面体公式与一个图的可平面性联系起来的做法是一个全新的认识。12欧拉多面体公式和可平面图欧拉公式对所有可平面图都成立，只要有一点图论知识的人就会认为这个论断是多么自然并且显而易见。是的，当判定一个图是否可平面时，我们就使用多面体公式，这早已熟练到了信手拈来的程度。然而在数学发展史上，最早的提法却隐蔽地出现在欧拉公式的一个不很充分的证明过程中。不过，19世纪的数学家都承认这个证明。后来才发现这个证明仅对闭的凸多面体有效。1813年I卅，一位法国数学家使用三角剖分的方法给欧拉公式一个相对一般的结论，为说明他的一般性结果，他将多面体的一个面作为底面，小心翼翼地由剩余的面向底面做投影，使其不产生新的顶点，从而得到多面体的一个平面图。这个方法将多面体公式推广到了平面网络的情形，自然地把多面体公式与“画”在平面上的图可平面图对应了起来。利用这种做法给出不充分证明的法国数学家就是柯西AUGUSTINLOUISCAUCHY，17891857。柯西与勒让德不同，后者研究多面体关心的还只是量，而前者在证明欧拉多面体公式的过程中另辟蹊径，从一些全新的方面给予了深入考察。柯西采用的就是图论中的三角剖分以及属于拓扑性质的投影做法。在一篇论文题目为“多面体研究第一篇研究报告”“RECHERCHES7LEGENDRE,AMELDMENTSDEGORAETRIE1。EDNFIRMINDIDOT,PADS,1794INNMMLBIGGS，EKEILHLLOYD，ROBINJWILSON,GRAPHTHEORY17361936，CLARENDONPRESS,OXFOUD,1986,78，6河北师范大学硕士学位论文FIG1SURLESPOLY6DRESPREMIERMONOIRE”中，柯西发现了欧拉公式一些新的特征。我们最感兴趣的一个就是，欧拉公式确实内蕴了可平面图所要满足的条件，这是拓扑思想融入图论的一个重要方面。他的做法是这样的他事先挖去了一个面的内部，他认为可把这个面作为底面，其余面向它作投影，宛如将它们平铺在一个平面上一样，这样不计原先去掉的那个面，他得到了VEFISFA1。实际上，柯西的投影过程类似于下面的方法从正方体的上方一点P，将正方体投影到下面的一个平面II，在这一投影过程如FIG1中，正方体的边、线分别投影成平面II上的平面图示的边、线，同时，正方体的各个面对应着投影图中由线隔开的部分，靠近点P的那个面似乎消失了，不妨认为它的投影面是图示中的最外围较大的那个区域柯西所谓的挖去的那个面。显然，对于任意凸多面体，选取适当的点P和平面II，都能得到多面体相应的平面投影图示。投影过程中，我们要求表示边的线只能相交于表示顶点的点处，在这种意义下，FIG2通常认为不是长方体的平面投影图。我们对画出一个正方体的平面图已经非常熟悉了，事实上，画出一个立体图的平面图形就是利用了刚才所描述的投影原理。如果选取不同视角就会得到不同的平面投影，但它们是同构的。是什么保证了这些图的同构呢是投影过程，这本质上是一个连续变换，它保证了图的某种不变性。我们看到，经投影产生的图好像对立体感的要求降低了，事实上恰恰相反，除了要求新图中保持原图的顶点不变外，投影产生的边不能出现新的交点。我们通常所说的可平面图，就是指这个图能够通过平面上的图表示出来。柯西的投影过程恰好表明了，凡是凸多面体对应的图都是可平面的。一个可平面图还可以看作是一个地图，图的每个区域代表国家，每条线表示“国界”。当然，同一种地图除可以表示在平面上外，还可以画在其他曲面上，例如，如果我们仍运用投影原理，在凸多面体内部选点，由此向外投影到一个球面上，便得到该多面体的球面地图，此时的边不再是直的而是弯曲的，失去了原7河北师范大学硕士学位论文有的度量性质，这样做的显著特征在于交点只出现在顶点处。一般地，地图是指任意表面上的图表示，其特征在于线只在端点处相交。通过分析平面图以及地图的特征，我们说欧拉公式的柯西形式是平面图的一个早期结果。平面图是图论意义下的平面图，而其研究方式却是拓扑的。柯西认为，如果在多面体内部加入适当的顶点和边，则将多面体分成P个独立的多面体，这种情况下，有下面式子成立VCF兰PL当PL，也就是不用进行剖分时，便是VEF屹，即欧拉公式是上式的特例。他继续分析，如果将多面体“压平”，就能使之成为一个多边形的平面网络，并且这种情况满足他的一般公式，此时只需令PO即可；在PO的证明过程中，他没用使用有关度量的术语，而是充分运用了“三角剖分的思想【L】，这种思想显然属于图论范畴；而他的摄影做法，我们刚才已经分析了，像是把多面体“平铺”在平面上一样，它是一个连续变换过程，这个过程保持了图的拓扑特征的不变性，因此属于图的拓扑性质的考虑。柯西的直接意向是想获得公式的证明，他在报告文集中证明了欧拉公式的一个推广形式VE卢PL，但这个证明因为假设了任一闭的凸多面体同胚于球面，有不足之处【N。不过，这个证明对一个可画在平面上的图满足欧拉公式是有效的，并且他的方法恰好说明了，只要可平面的图都应满足欧拉多面体公式。总之，欧拉多面体公式既是图论的，也是拓扑的。13欧拉公式遇到有“洞”多面体与柯西撰写报告文集大约同一时期，日内瓦的数学教授LHUILIERSIMONAMTOINEJEANLHUILIER,17501840一直在系统地研究着欧拉公式的反例。LHUILIER发现了三种类型的多面体使得欧拉公式不成立，为了解决这一问题，他对欧拉公式做出了进一步推广并给出了拓扑证明。他的思考方法也是图论与拓扑思想交叉的范例。19世纪初，LHUILIER曾写了两篇相关的论文。在第一篇“EXEEPTIOUSDONTCETH60R6MEESTSUSCEPTIBLE”文章中，他给出了使得欧拉公式不成立的三类反例。这篇文章于1811年发表在MDMACAD1MPSCISTPDTERSB；对于另一篇篇幅较长的论文“多面体研究报告”M6MOIRESUJ“LAPOLYHEDROMETRY嘲，他想在法国数学家热尔GERGONNE，JD17711859仓0办的纯粹与应用数学纪事8ANNALESDEMATHEMATICQUESPURESETAPP脚UDES上发表，就递交给了GERGONNE，但OERGONNE没有立即将其全文刊登，可能他也认为篇幅过于长了。但对于LHUILICR的研究报8创办于1810年，见【美】莫里斯克莱因著，朱学贤等译，古今数学思想【ML第二册，上海科学技术出版社，2003，3853河北师范大学硕士学位论文台舍FIG3告，他还是给予了充分重视，在认真斟酌其论文思想之后，GERGONNE又将自己的一些观点纳入LHUILICR的文章，然后发表在他创办的数学年刊上ANNALEDEMATHMATIQUES318123，169189。笔者认为，LHUILI盯在后一篇文章中做出了两个重要贡献一个是他应用欧拉公式，重新论证了自然界只存在五个正凸多面体的事实；另一个就是他深入研究了三类特殊的多面体，得到了我们现在所谓的欧拉公式的推广形式VEF229。我们知道，自然界只存在五种正凸多面体，这在当时特别是在数学家的圈子里已经是不争的事实了，但是LHUILIER的论证却能引起数学家的注目，不难想像到LHUILIER有他的独到之处，数学家WILSON在他的图论一17361936中给予了归纳【11第一、整个推导过程丝毫没有涉及诸如全等或其它的度量概念。第二、他首先注意到了正多面体是成对出现的，这促使他预见了对偶思想第三、他将正多面体的面趋于无穷大时视为对平面的正则剖分的极限情况。对于后面两种，笔者认为LHUILIER的考虑在当时也是十分先进的。LHUILIER第二个重要贡献就是他发现了三类多面体使得欧拉公式不成立它们是内部有一个“洞”的多面体、同胚于锚环的多面体和面上有凹坑缺口的多面体”。LHUILIER在第二部分将论述中心完全放在研究这三个不符合欧拉公式的例子上，发现这些反例是研究多面体公式的一个重要转折点，从此引导了曲面拓扑性质的广泛研究。对于内部有一个“洞”的多面体，LHUILIER得到VEF4；第三个例子是面上有凹坑缺口的多面体，即它某一面形如FIG3中第一个面，而不是第二种无缺口。用现代术语，我们称第二种类型的面是学麓谣钐第一类是复单连通的。LHUILIER指出不是单连通的面通常出现在晶体中例如，CALAREOUSSPAR，欧拉公式对于这种晶体也是不成立的。这三个反例中最重要的一个是第二类多面体，下面我们给予较详细的阐述9河北师范大学硕士学位论文FIG4FIG6FIG5我们不妨假设曲面是连通的即一个整块，并且是单连通的。我们首先指出，欧拉特征T1VE的值依赖于地图所在的曲面，而非地图本身。例如，欧拉的一般凸多面体对应于球面地图，它的欧拉特征11_2；而柯西的平面网络对应着扁平盘上的平面地图，此时111。那么LHUILIER所考虑的第二类反例相当于这样一个曲面它是一种没有边界并且不能无限扩张的闭曲面，显然LHUILIER指的不是平面、扁平面或半球面。不难知道，球面是他考虑的这种曲面里最简单的一种，另一种是环形的曲面如图FIG5，称此曲面为环面或锚环ANCHOR。LHUILIER第三个反例实质上就是环面。环面是一类重要的曲面。事实上，我们很容易得到一个环面，首先，我们在立方体其中一对相对的面之间“挖”一个长方体状的洞，如图FIG4，然后我们可以适当地添加一些边，使得每个面都是单连通的，这样就得到一个表面是环面的多面体的例子，细心的读者不难发现，它的110，这就是LHUILIER所发现的【9J。为更好理解LHUILIER的思想方法，我们可以通过类似的方式构造出无穷多个所要求的曲面任取一个球面，首先从其表面“抠”掉两个圆形区域，然后用一个适当的圆筒状的“柄”的两头粘合住这两个洞，这样我们就得到了1个环柄。重复上述过程G次，得到G个环柄，对于FIG6，G2。易知，环面的GL，球面GO。我们这种构造方法在原理上与LHUILIER的在凸多面体内打“洞”的思想相同。LHUILIER证明了，如果一个多面体的地图恰好可以画在有G个“洞”的球面上，那么项点数一边数面数229。现在我们称有G个“洞”或G个“环柄”的闭曲面，其亏格为G，那么称T1229为亏格是G的闭曲面的欧拉特征公式，也就是说”229是一个图能否画在该曲面上的特征。10一。玲；河北师范大学硕士学位论文二E三三一FIG7LHUILIER差不多已经注意到了一个曲面可能展现的所有特性11，然而却忽略了重要的一点，那就是一个曲面还可能是单侧曲面。14朝向拓扑的发展欧拉庞加莱示性数继LHUILIER发现VEF229之后，数学家没有满足于既得的推广结果，己特别是数学家李斯廷LISTING，JOHANNBENEDIKT，18061882，他后来任格丁根的物理教授BO，他曾经这样问自己，球面多面体欧拉特征VEF为什么是27而形如相框的多面体同胚于环面，2却变成了07当遇到柯西的2维多面体时2甚至变成了奇数L更一般地，对于有G个环柄的多面体，欧拉特征就依赖于G，即TL229李斯廷对上述有趣的现象进行了深入细致地分析，他想寻求这种几何图形的定性规律，这导致他于1862年发表了文章“多面体欧拉定理的推广”“DERCENSUSRLUMLICHERCOMPLEXEODERVERALLGEMEINERUNGDESEULERSCHENSATZESVONDENPOLYEDEM一。李斯廷在对欧拉公式进行推广的过程中，一个成果就是得到了他的TLLECENSUSTHEOREMLO。然而，在推广欧拉公式方面，我们发现李斯廷与LHUILIER一样未能考虑到单侧曲面。他虽然给出了莫比乌丝带M6BIUSSTRIP的图形FIG7，见李斯廷在THECENSUS中的图3，但是只是在脚注中提了一下，且是与一个双侧的复连通曲面这在THECENSUS也给出了图示一起出现的。李斯廷写道【LOL，这两个图形的边界都是一条单一的没有扭结的曲线，它们的性质与正文中所描述的简单图不同，即简单图可以连续地收缩为一点，并且若从简单图的一侧到另一侧需要穿过其边界曲线。显然，这种解释根本不明确，相反，我们可以明确的指出，李斯廷没有观察到莫比乌丝带的单侧性另一方面，就李斯廷这篇文章的中心定理THECENSUSTHEOREM”来说，仅从它的注记和草稿就能看出，李斯廷曾经考虑的题目中有六个都提到了拓扑一词，但最后他选择了饥NS耐意思是按照他自己的特殊标准进行的一种生物分类。尽管这个定理形式之简洁优美，令人拍案叫绝，但它却没有达到现代拓扑的总的原则。一个主要原因在于它所描述的“特征”ATTRIBUTES并不十分清晰，甚至有些混乱，并且这些特性通常也不容易被确定；另外它混淆了维数、连通数和扩张的概念“”。但是，李斯廷的铀ECENSUSTHEOREM却具有里程碑意义。然而笔者认为，李斯廷的THECENSUS却只能说是在走向拓扑9英译名“THECSUSOFSPATIALAGGREGATES,ORGENERALIZATIONOFEULERSTHEOREMONPOLYHEDM”。10定理内容为，AA一BPC竹一D60详见JOHANNBENEDIKTLISTING，EBREITENBERGER,HISTORYOFTOPOLOGY,LAP91911河北师范大学硕士学位论文的方向的一个过渡性理论。他建立了前人未能意识到的拓扑的许多方面，特别是在证明中他对拓扑性质的严密性追求深深地影响着后入；然而，试图给欧拉公式一个彻底的推广离不开精确的定义，而寻求精确的定义对于李斯廷本人甚至他那个时代的任何一个数学家来讲都具有非常的挑战性，这是一项不平凡的业绩，他们为之奋斗不息，李斯廷所扮演的角色正是这项事业的先锋与开拓者。简言之，他就像任何一个勇猛的探险者一样，大胆地在一个新的领域做出了开创性的研究。然而，他的工作是不成熟的，不久就让位于后来的更为实用、有效的学科使命。这个使命的承担者就是当时伟大的数学家庞加莱。在某种程度上，他继承了李斯廷的一些思想。李斯廷曾经定义过拓扑对象“复形COMPLEXES”于1862年的“多面体欧拉定理的推广”中，他当时还考察了复形的拓扑性质，主要研究这些性质是如何影响欧拉特征的他还借用了生物科学中关于这些性质的术语PERIPHRAXIS”、CYCLASIS”。与李斯廷一样，庞加莱也由基本的胞腔“CELLS”O一胞腔即顶点和卜胞腔边构造“复形”。胞腔也称单形，一个单形只不过是一个N维的三角形。就是说，零维单形是一个点；一维单形是一条边；二维单形是一个三角形；三维单形是一个四面体；N维单形是一个具有N1个顶点的广义的四面体。庞加莱的基本思想是将代数结构这一数学工具极好地融合了构造复形的方法，从而实现了拓扑思想的代数形式化，这正是李斯廷所未能考虑到的。他对于一个给定的复形，构作它的K维定向单形的线性组合，得到一个链CHAIN；并定义了闭链的边缘，然后他引进了他称之为BETTI数为了归功于ENRICOBETTI的那些量。1895年，庞加莱发表了他的主要论文位置分析叫，庞加莱在位置分析的16欧拉定理啦OREMEDEULER中，结合贝帝数也是一种拓扑不变量进一步推广了欧拉公式，得到了欧拉庞加莱示性数，这是研究曲面的拓扑特征非常有用的定理之一。在他的第一篇1899年和第二篇1900年补充中，庞加莱证明了Q维的BETTI数PQ即BETTI的连通数加1是PQ一1一L，其中是Q维单形的个数。通过引入N维复形KN的示性数CHARACTERISTICNKN，即如果复形有毗个K维单形，定义NKNKN_“1KAK这个量就是EULER数VEF的一个推广。庞加莱关于这个示性数的结果是如果PK是KN的L卜维BETTTI数，那么NKN岛一1KPK这个结果叫做EULERPOINCAR6公式。庞加莱的位置分析连同其后发表的5篇补充1899，1900，1902，1904共同构成了组合拓扑学的主要骨架“，他使组合拓朴学成为数学的一个重要分支。有关多面体公式的探讨这个时候已经进入组合拓扑学领域了，我们这里不再赘述。但对于拓扑思想不断融入多面体研究的这段演进过程，这里至少给予了精炼的介绍和较为恰当的分析，引导了理解交叉问题的思想融合的特点。河北师范大学硕士学位论文2从GUTHRIE染色问题到HADWIGER猜想1852年，GUTHRIE提出了地图染色问题【L】，这是一个典型的具有拓扑性质的图论问题，也是拓扑学早期的重要问题之一。对于这个本身就兼具图论和拓扑两个学科性质的特殊的交叉问题，它的发展自然也是交叉特性体现的一个侧面，本节阐述了从GUTHRIE染色问题到HADWIGER猜想发展过程中的几个明显重要的历史转折点。笔者这里首次指出，使GUTHRIE问题到HADWIGER猜想的推广成为可能，关键在于缩图GRAPHMINOR概念的引入。同时也因此使染色问题得到了进一步的区分和一般化，开拓了研究染色问题的新视角。通过认真考察WAGNER发表其定理的那篇文章，以及与之有关的一些论文；并结合前辈数学家的相关工作，试图挖掘最本质的思想根源。这是历史研究者所面临的难点之一，本节的尝试有助于突破这一难点。由于HADWIGER猜想是GUTHRIE问题的推广，只有对四色定理本身的正确性不再产生疑义时，研究这个推广才更具一般性意义，所以有必要探讨CMTHDE四染色问题的两次机器证明，我们借助1994年国际数学家大会上关于此问题的L小时报告去澄清四色定理正确的事实。末尾部分概述了HADWIGER猜想的研究现状，并根据当I；学术动态，分析其研究进路接着简要说明解决问题的三个阶段及每个阶段的方法进路，以期对相关研究起到借鉴之意义；另外笔者认为，这个结论具有普遍意义，类似这方面的探讨将可能成为数学史研究者与数学家交流互动最为密切也尤其必要的主题之一。HADWIGER猜想是图论中未解决的重要猜想之一，是那种形式非常简单、极易陈述但又极难解决的问题，猜想预言一个图如果不含K州为其缩图GRAPHMINOR，则该图可N色。N妻1这一猜想是1943年由瑞士数学家HUGOHADWIGER提出的“”，不难看出N4的情况就是格思瑞GUTHRIE，FRANCIS，18311899儿在地图染色时发现的四色问题“。这一问题于1976年由阿佩尔和哈肯在计算机的辅助证明下，使之成为四色定理，而对计算机证明四色问题而引发的疑虑，17年后由于PAULSEYMOUR和其他三位数学家的工作终于得到了澄清。1994年，PAULSEYMOUR在国际数学家大会上再次向世人宣布了四色定理是成立的“”现在，四色定理的正确性已无可争辩，在20世纪上半页，随着图论研究的不断深入，对四色问题的探索也向着形式高度抽象的一般性模式而发展，数学家们关注的焦点呈现出了与数学抽象性相联系的追求一般性算法的倾向，此特征也渗透到了图的染色这一具体问题。笔者认为，瓦格纳WAGNER，KLAUS，19102000的