计算机图论知识恶补瀚哥版

图算法讲义凡事没有绝对，一切皆有可能广东财经大学计算机实验班瀚哥组 第页目录TOC\o"1-3"\h\u22664引语 232224步骤 26240正文1：基本数据结构 328147线性表 3286561.线性表介绍 3194672.顺序表：向量 448523.链表 426680栈，队列 7305621.栈虚基类（Stack.h) 7138762.顺序栈和链式栈（Stack.cpp) 8105523.顺序队列 993314.链式队列 1019938正文2：图背景 1130818历史（摘自wiki) 1123526柯尼斯堡的七桥 1116899骑士周游问题 1128836环游世界游戏 1218696四色问题 1315733应用 1410261正文3：图的表示 143697图定义 1411993图术语 1416538邻接矩阵 1710776邻接表 1727211图的抽象数据结构 1826845具体代码实现参见参考 1820496参考 1920593图代码 24凡事没有绝对，一切皆有可能组员：陈锦瀚何游敏苏江吟方桂凯（排名不分先后）时间：2014年3月18日

图算法讲义引语一切的理论都是为现实服务的。计算机的出现解决了人脑的限制，人脑不够快！《人脑与机器》说：机器的智慧不会超过人的智慧。机器就是人造的，我们用一道程序来模拟我们的思考并求出结果。人脑异常复杂，经常有第六感等超自然感觉，还可以并行地做好几件事，如：可以眼睛一边看电视，一边在洗脚，一边还在吃花生，更重要的是他竟然在和同学说话，脑袋里却在想他的女朋友。无疑，人类是有想法的很聪明的懒人：一：计算机代替人，可以提高工作效率。二：换句话，你就解放了，可以翘着腿喝咖啡，等结果。但是！机器不知怎么做，你要教他，而且还要教得很好，故有了程序。第一：程序应该达到预期的结果，不能出错。第二：必须很快得到结果，否则你就要喝咖啡好几百年了，因为一个坏的教导会不停运行直到地老天荒。怎么办？答案：想好的算法，好的算法又要好的数据结构。人是不能满足的高等动物，渴望我要快，更快，再快的节奏！于是，一代代又一代人研究算法，给出各种算法复杂度分析：渐进符号，程序测试等，励志突破前人，名垂千古。当然，说白了，他们是没什么事做，也只能做那件事，这就是所谓的社会分工。不要鄙视程序猿！一个不调侃自己的程序猿不是好的程序猿，一个不直面惨淡程序的程序猿也不是好的程序猿。好吧，让我们来挠腮抓头吧，进入今天的图讲解。图高端，大气，上档次，所以会讲很长很长，还会提供c++代码支持。提供c++代码原因：第一：类c，面向对象，群众基础深。第二：我喜欢。（我自己喷自己，建议改为JAVA).一部图论就是一部计算机的心酸苦难史。所以，由我们组来讲解有关图的各种复杂关系，让我们来一场心与心的碰撞吧！以下讲义以大白话为主，不喜勿喷。步骤程序=算法+数据结构。我们由该公式开始讲解。图论背景：图论来源于现实的抽象，把一些东西（object）当成点，以线连接点，这就是连小孩子都会理解的图论。为了便于解决问题：如走迷宫问题，旅行商旅行问题，找最短旅行路径问题，找最便宜旅行路径问题，找你祖宗十几代问题，考试安排问题，座位协调问题，手机无线电通讯问题，水资源调运问题，最重要的是找女朋友问题。所以，图论被扩充，定义了很多的术语，目的就是解决相应的问题。注：术语该出现的时候他自然会出现。数据结构：为了便于在计算机中实现程序，所以要编程。从机器语言到汇编语言，再到高级语言，这些语言指导计算机做事。有一种病叫做：代码恐惧症，但是你一直会看到代码！一幅图怎么用计算机表示？抽象！怎么抽象？邻接表和邻接矩阵，而邻接矩阵和邻接表由数组和指针实现。所以有必要先介绍线性表：向量和链表，然后介绍栈和队列。而树结构，树实际上是一种特殊的图，而图也就成为最顶层的数据结构，其重要性不言而喻。以下将会用代码讲述各种数据结构，这是讲图算法的基础，超级啰嗦，不喜勿喷。算法：实现了伟大的数据结构后，还要会用这些数据结构。Dijkstra算法（单源最短路径），Floyd算法（多源最短路径），Prim算法，Kruskal算法（最小生成树MST）已经吓退你了吧！我们会利用DFS（深度搜索）和BFS（广度搜索）以及构造的拓扑排序来实现这些算法。DFS和BFS由栈和队列实现，采用递归方法。授课人群：接受过九年义务教育，有基本的理性和一点点的感性（可以喷我），喜欢数学（这个学科需要思维灵敏，不喜欢数学，没问题！不过，不喜欢，可以去爱嘛！）的广大的计算机爱好者。借用俺母校校训：勤奋，活泼，求实，向上。授课基础：计算机科学导论（知道计算机基本结构），数学（一年级到十二年级），程序设计（C,C++,JAVA,PYTHON,VB,会打码)，数据结构，英语（过了四级就好），心理学（心里素质必须硬）。惨无人道的授课开始，进入正文1或者跳到正文3！都是讲数据结构的！正文1：基本数据结构线性表数据的组织形式！1.线性表介绍线性表是由有限节点集N，以及定义在N上的线性关系r所组成的线性结构（有序的）。直白一点就是说所有节点可以按关系r排列成一个线性序列：n0->n1->n2->...-nk（有前趋后驱）。抽象数据结构组成：取值空间（可能取值的集合），运算集。存储结构：1.定长：一般数组。2.变长：动态数组，链接结构代码如右：以下介绍顺序为：顺序表-向量（vector),链表：单链表，双链表，循环单链表，循环双链表。2.顺序表：向量算法2.1:插入操作时间开销：，其中元素个数为k，各位置插入概率为p。算法2.2：删除操作3.链表算法3.1：查找单链表第i个结点算法3.2：插入算法算法3.3：删除算法算法3.4：求长度算法双链表操作如右图主要链表：瀚哥总结：向量又称顺序表没有使用指针，可以节省计算机存储空间，而且直接下标访问数组，很容易懂！就现在随便就几G内存来说，应该是不必省空间，事实上，是要看情况的！数组固定了长度，而链表不必提前确定长度，而且还可以变长度，并且插元素，删元素不必像数组一样整排移动。所以，这两种方式只是想引起你的思考，如何权衡，学会两方面看问题。栈，队列特殊的线性表：栈，队列。栈（LIFO,Last-In-First-Out)：就像你洗盘子的时候，你洗好了一个盘子，把它放到（push压入)桌子上，然后洗第二个，叠上去。最后，洗好了。这时，桌子有一叠盘子。你想吃饭，要用盘子，所以你要把最上面那个盘子拿出来(pop弹出)。这就是后进先出，最迟叠的盘子最先被用到。1.栈虚基类（Stack.h)代码如右图。2.顺序栈和链式栈（Stack.cpp)表示以上程序真正运行有点问题，STL很复杂。我被这个/mdl13412/article/details/6649700吓傻了。栈主要用于程序递归，如后缀表达式求值，求汉诺塔等递归问题（递归栈）。3.顺序队列栈只从TOP那一头入，也只能从TOP一头出，队列则是一头只能出，另外一头只能入。称为FIFO(First-In-First-Out)先进先出，顾名思义，队列就是一条队。小孩子都会知道先排队买冰淇淋的可以先买到冰淇淋，然后可以先吃，而这叫做规则，后到的人不能先买到，体现了公平。队列的使用也是十分广泛的。代码如下：4.链式队列正文2：图背景在此文中，将会介绍图论的历史以及其应用，由此引出一大堆的算法。历史（摘自wiki)一般认为，于1736年出版的欧拉的关于柯尼斯堡七桥问题的论文是图论领域的第一篇文章。此问题被推广为著名的欧拉路问题，亦即一笔画问题。而此论文与范德蒙德的一篇关于骑士周游问题的文章，则是继承了莱布尼茨提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的欧拉公式与图论有密切联系，此后又被柯西等人进一步研究推广，成了拓扑学的起源。这个问题是基于一个现实生活中的事例：当时东普鲁士柯尼斯堡（今日俄罗斯加里宁格勒）市区跨普列戈利亚河两岸，河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？柯尼斯堡的七桥莱昂哈德·欧拉在1735年提出，并没有方法能圆满解决这个问题，他更在第二年发表在论文《柯尼斯堡的七桥》中，证明符合条件的走法并不存在，也顺带提出和解决了一笔画问题[1]。这篇论文在圣彼得堡科学院发表，成为图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数，这样的点称为偶顶点。相对的，连有奇数条线的点称为奇顶点。欧拉论述了，由于柯尼斯堡七桥问题中存在4个奇顶点，它无法实现符合题意的遍历。欧拉最后给出任意一种河──桥图能否全部走一次的判定法则，从而解决了“一笔画问题”。对于一个给定的连通图，如果存在两个以上（不包括两个）奇顶点，那么满足要求的路线便不存在了，且有n个奇顶点的图至少需要n/2笔画出。如果只有两个奇顶点，则可从其中任何一地出发完成一笔画。若所有点均为偶顶点，则从任何一点出发，所求的路线都能实现.骑士周游问题Alexandre-ThéophileVandermonde(28February1735–1January1796)wasaFrenchmusician,mathematicianandchemistwhoworkedwithBézoutandLavoisier（拉瓦锡）;hisnameisnowprincipallyassociatedwithdeterminanttheoryinmathematics.HewasborninParis,anddiedthere.Vandermondewasaviolinist,andbecameengagedwith（从事)mathematicsonlyaround1770.InMémoiresurlarésolutiondeséquations(1771)hereportedonsymmetricfunctions（对称函数）andsolutionofcyclotomicpolynomials（割圆多项式）;thispaperanticipatedlater（预先考虑到后来的）Galoistheory(seealsoabstractalgebrafortheroleofVandermondeinthegenesisofgrouptheory群论起源).InRemarquessurdesproblèmesdesituation(1771)hestudiedknight'stours,andpresaged（预示）thedevelopmentofknottheory（钮结理论）byexplicitlynotingtheimportanceoftopologicalfeatureswhendiscussingthepropertiesofknots:"Whateverthetwistsandturnsofasystemofthreadsinspace,onecanalwaysobtainanexpressionforthecalculationofitsdimensions,butthisexpressionwillbeoflittleuseinpractice.Thecraftsman（工匠）whofashions（塑造）abraid（编织物),anet,orsomeknotswillbeconcerned,notwithquestionsofmeasurement,butwiththoseofposition:whatheseesthereisthemannerinwhichthetheadsareinterlaced（交错的）"由一个维球，只可以在维空间扭成结，而且必定能在维空间解结将一个国际象棋的骑士（或称马）放在棋盘上，有什么路径能使它走遍棋盘上每一格呢？假若骑士能够从最后位置合法地走到最初位置，则称此巡逻为“封闭巡逻”，否则，称为“开巡逻”。对于8*8棋盘，一共有26,534,728,821,064种封闭巡逻。到底有多少种开巡逻仍旧是未解决的问题。在九世纪的古印度恰图兰卡就有出现使用半个8*8棋盘的骑士巡逻棋谜。问题的变化包括用不同大小的棋盘，及一种以此问题为基础的两人游戏。许多数学家曾钻研此问题，包括欧拉。这问题是在图论里的哈密顿路径问题的特别案例。环游世界游戏1857年，哈密顿发明了“环游世界游戏”（icosiangame），与此相关的则是另一个广为人知的图论问题“哈密顿路径问题”。1859年，英国数学家汉密尔顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“绕行世界”。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。“图”这一名词是西尔维斯特在于1878年发表在《自然》上的一篇论文中提出的。欧拉的论文发表后一个多世纪，凯莱研究了在微分学中出现的一种数学分析的特殊形式，而这最终将他引向对一种特殊的被称为“树”的图的研究。由于有机化学中有许多树状结构的分子，这些研究对于理论化学有着重要意义，尤其是其中关于具有某一特定性质的图的计数问题。除凯莱的成果外，波利亚也于1935至1937年发表了一些成果，1959年，DeBruijn做了一些推广。这些研究成果奠定了图的计数理论的基础。凯莱将他关于树的研究成果与当时有关化合物的研究联系起来，而图论中有一部分术语正是来源于这种将数学与化学相联系的做法。四色问题图论研究史上最著名也是产生成果最多的问题之一：“是否任何一幅画在平面上的地图都可以用四种颜色染色，使得任意两个相邻的区域不同色？”这一问题最早于1852年由FrancisGuthrie提出，最早的文字记载则现于德摩根于同一年写给哈密顿的信上。包括凯莱、肯普等在内的许多人都曾给出过错误的证明。泰特（Tait）、希伍德（Heawood）、拉姆齐和哈德维格（Hadwiger）对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，HeinrichHeesch发表了一个用计算机解决此问题的方法。1976年，阿佩尔（Appel）和哈肯（Haken）借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机一一验证了它们可以用四种颜色染色。但此方法由于过于复杂，在当时未被广泛接受。1860年之1930年间，若当、库拉托夫斯基和惠特尼从之前独立于图论而发展的拓扑学中吸取大量内容进入图论，而现代代数方法的使用更让图论与拓扑走上共同发展的道路。其中应用代数较早者如物理学家基尔霍夫于1845年发表的基尔霍夫电路定律。图论中概率方法的引入，尤其是埃尔德什和AlfrédRényi关于随机图连通的渐进概率的研究使得图论产生了新的分支随机图论。应用图论的应用范围很广，它不但能应用于自然科学，也能应用于社会科学。它非但广泛应用于电信网络、电力网络、运输能力、开关理论、编码理论、控制论、反馈理论、随机过程、可靠性理论、化学化合物的辨认、计算机的程序设计、故障诊断、人工智能、印制电路板的设计、图案识辩、地图着色、情报检索，也应用于诸如语言学、社会结构、经济学、运筹学、兵站学、遗传学等等方面。正文3：图的表示图定义图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合图术语图术语1、无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边(Edge)，用无序偶(Vi,Vj)来表示。右图G1是一个无向图，G1={V1,E1}，其中V1={A,B,C,D}，E1={(A,B),(B,C),(C,D),(D,A),(A,C)}2、有向边：若从顶点Vi到Vj的边有方向，则称这条边为有向边，也成为弧(Arc)，用有序偶<Vi,Vj>来表示，Vi称为弧尾，Vj称为弧头。右图G2是一个无向图，G2={V2,E2}，其中V2={A,B,C,D}，E2={<B,A>,<B,C>,<C,A>,<A,D>}有向图和无向图

在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。如上，G1为无向图，G2为有向图。4、简单图：在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。以下两个则不属于简单图：完全图：具有n个顶点，n(n-1)/2条边的无向图，称为完全无向图，具有n个顶点，n(n-1)条弧的有向图,称为完全有向图。完全无向图和完全有向图都称为完全图。如下图。6、稀疏图和稠密图：对于一般无向图，顶点数为n，边数为e，则0≤e≤n(n-1)/2。

对于一般有向图，顶点数为n，弧数为e，则0≤e≤n(n-1)。

当一个图接近完全图时，则称它为稠密图，相反地，当一个图中含有较少的边或弧时，则称它为稀疏图。这里的稀疏和稠密是模糊的概念，都是相对而言的，通常认为边或弧数小于n*logn（n是顶点的个数）的图称为稀疏图，反之称为稠密图。7.权：在图的边或弧中给出相关的数，称为权。权可以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网。如下图。

8.子图：假设有两个图G1=(V1,E1)和G2=(V2,E2)，如果V2⊆V1，E2⊆E1，则称G2为G1的子图(Subgraph)。连通图和强连通图

在无向图中，若从顶点i到顶点j有路径，则称顶点i和顶点j是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。

在有向图中，若从顶点i到顶点j有路径，则称从顶点i和顶点j是连通的，若图中任意两个顶点都是连通的，则称此有向图为强连通图，否则称为非强连通图。

9．连通分量和强连通分量

无向图中，极大的连通子图为该图的连通分量。显然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量。有向图中，极大的强连通子图为该图的强连通分量。显然，任何强连通图的强连通分量只有一个，即它本身，而非强连通图有多个强连通分量。

10．路径、回路

在无向图G中，若存在一个顶点序列Vp,Vi1，Vi2，…，Vin，Vq,使得（Vp,Vi1）,(Vi1,Vi2),…..，(Vin,Vq)均属于E（G），则称顶点Vp到Vq存在一条路径。若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。起点和终点相同的路径称为回路，简单路径组成的回路称为简单回路。路径上经过的边或弧的数目称为该路径的路径长度。

11．有根图v在一个有向图中，若从顶点V有路径可以到达图中的其它所有顶点，则称此有向图为有根图，顶点V称作图的根。即顶点V的入度为0，其余顶点的入度均为1。

12．生成树、生成森林

连通图的生成树是一个极小连通子图，它包含图中全部n个顶点和n-1条不构成回路的边。非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。邻接矩阵相邻矩阵：表示顶点间相邻关系的矩阵。若G是一个具有n个顶点的图，则G的相邻矩阵是如下定义的n*n矩阵：A[i,j]=1，若（Vi，Vj）（或<Vi，Vj>）是图G的边；A[i,j]=0，若（Vi，Vj）（或<Vi，Vj>）不是图G的边。相邻矩阵的空间代价为O(n2)如：邻接矩阵可以用于有向图或无向图，也可以用于有权重的图。容易找到一个点的出度和入度，也便于理解。邻接表n个顶点m条边的无向图，需用(n+2m)个存储单元n个顶点m条边的有向图，需用(n+m)个存储单元图的抽象数据结构比较：邻接表和邻接矩阵实现图各有优势，当出现稠密图时，邻接矩阵更好，因为邻接表指针具有结构性开销，而相邻矩阵可能只需要1bit。各种分析，各种好处，这就是权衡，算法分析的重点。具体代码实现边类，图基类，邻接矩阵实现的图类，邻接表实现的图类5555发你哈哈哈哈哈

参考图论/wiki/%E5%9B%BE%E8%AE%BA伽罗瓦理论/wiki/%E4%BC%BD%E7%BE%85%E7%93%A6%E7%90%86%E8%AB%96纽结理论/wiki/%E7%B4%90%E7%B5%90%E7%90%86%E8%AB%96恰图兰卡/wiki/%E6%81%B0%E5%9B%BE%E5%85%B0%E5%8D%A1四色定理/wiki/%E5%9B%9B%E8%89%B2%E9%97%AE%E9%A2%98保罗·爱多士/wiki/%E4%BF%9D%E7%BD%97%C2%B7%E5%9F%83%E5%B0%94%E5%BE%B7%E4%BB%80数学达人简历/gzsx/xszx_1/czsxxszp/数据结构与算法/徐卓群.-北京：高等教育出版社，2004.7哈密顿，W．R．(Hamilton，WilliamRowan),1805年8月4日生于爱尔兰都柏林；1865年9月2日卒于都柏林．力学、数学、光学．

哈密顿的父亲阿其巴德(ArchibaldRowanHamilton)为都柏林市的一个初级律师．哈密顿自幼聪明，被称为神童．他三岁能读英语，会算术；五岁能译拉丁语、希腊语和希伯来语，并能背诵荷马史诗；九岁便熟悉了波斯语，阿拉伯语和印地语．14岁时，因在都柏林欢迎波斯大使宴会上用波斯语与大使交谈而出尽风头．

哈密顿自幼喜欢算术，计算很快．1818年遇到美国“计算神童”Z．科耳本(Colburn)后对数学产生了更深厚的兴趣．1820年再相逢时，哈密顿已阅读了I．牛顿(Newton)的《自然哲学的数学原理》(Mathematicalprinciplesofnaturalphilosophy)，并对天文学有强烈爱好，常用自己的望远镜观测大体；还开始读P．S．拉普拉斯(Laplace)著作《天体力学》(Mécaniquecé1este)，1822年指出了此书中的一个错误．同年开始进行科学研究工作，对曲线和曲面的性质进行了系列研究，并用于几何光学．他的报告送交爱尔兰科学院后，R．J．布林克莱(Brinkley)院士评论说：“这位年轻人现在是这个年龄(17岁)的第一数学家．”

1823年7月7日，哈密顿以入学考试第一名的成绩进入著名的三一学院，得到正规的大学训练，后因成绩优异而多次获得学院的古典文学和科学的最高荣誉奖．他在1823到1824年间完成了多篇有关几何学和光学的论文，其中在1924年12月送交爱尔兰皇家科学院会议的有关焦散曲线(caustics)的论文，引起科学界的重视．

1827年6月10日，年仅22岁的哈密顿被任命为敦辛克天文台的皇家天文研究员和三一学院的天文学教授．

哈密顿有兄弟姐妹八人，家庭负担很重；为减轻父亲经济压力，他毕业后带着三个妹妹住到敦辛克天文台．哈密顿不擅长天文观测，在天文台工作的五年中，仍主要从事理论研究；但因与外界很少联系，工作成果并未引起重视．

1832年，哈密顿成为爱尔兰皇家科学院院士后非常活跃，与学术界人士广泛交流讨论，包括一些诗人和哲学家．他从S．T．科勒里奇(Coleridge)的作品中了解到I．康德(Kant)的哲学，热情地读完康德主要著作《纯理性批判》(KritikderReinenVernunft)．康德哲学观点对哈密顿后期的工作有很大影响．

1834年，哈密顿发表了历史性论文“一种动力学的普遍方法”(Onageneralmethodindynamics)，成为动力学发展过程中的新里程碑．文中的观点主要是从光学研究中抽象出来的．

在对复数长期研究的基础上，哈密顿在1843年正式提出了四元数(quaternion)，这是代数学中一项重要成果．

由于哈密顿的学术成就和声望，1835年在都柏林召开的不列颠科学进步协会上被选为主席，同年被授予爵士头衔．1836年，皇家学会因他在光学上的成就而授予皇家奖章．1837年，哈密顿被任命为爱尔兰皇家科学院院长，直到1845年．1863年，新成立的美国科学院任命哈密顿为14个国外院士之一．

哈密顿的家庭生活是不幸福的．早在1823年，他爱上了一位同学的姐姐卡塞琳·狄斯尼(CatherineDisney)，但遭到她的拒绝，哈密顿却终身不能忘情．在恋爱生活中一再碰壁之后，他于1833年草率地同海伦·贝利(HelenBayly)结婚．虽然生育二子一女，终因感情不合而长期分居．哈密顿经常不能正规用餐，而是边吃边工作．他去世后，在他的论文手稿中找到不少肉骨头和吃剩的三明治等残物．

哈密顿工作勤奋，思想活跃．发表的论文一般都很简洁，别人不易读懂，但手稿却很详细，因而很多成果都由后人整理而得．仅在三一学院图书馆中的哈密顿手稿，就有250本笔记及大量学术通信和未发表论文．爱尔兰国家图书馆还有一部分手稿．

他的研究工作涉及不少领域，成果最大的是光学、力学和四元数．他研究的光学是几何光学，具有数学性质；力学则是列出动力学方程及求解；因此哈密顿主要是数学家．但在科学史中影响最大的却是他对力学的贡献．哈密顿量是现代物理最重要的量，当我们得到哈密顿量，就意味着得到了全部。欧拉（LeonhardEuler公元1707-1783年）1707年出生在瑞士的巴塞尔（Basel）城，13岁就进巴塞尔大学读书，得到当时最有名的数学家约翰·伯努利（JohannBernoulli，1667-1748年）的精心指导。欧拉渊博的知识，无穷无尽的创作精力和空前丰富的著作，都是令人惊叹不已的！他从19岁开始发表论文，直到76岁，半个多世纪写下了浩如烟海的书籍和论文。到今几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等，数也数不清。他对数学分析的贡献更独具匠心，《无穷小分析引论》一书便是他划时代的代表作，当时数学家们称他为"分析学的化身"。欧拉是科学史上最多产的一位杰出的数学家，据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%，彼得堡科学院为了整理他的著作，足足忙碌了四十七年。欧拉著作的惊人多产并不是偶然的，他可以在任何不良的环境中工作，他常常抱着孩子在膝上完成论文，也不顾孩子在旁边喧哗。他那顽强的毅力和孜孜不倦的治学精神，使他在双目失明以后，也没有停止对数学的研究，在失明后的17年间，他还口述了几本书和400篇左右的论文。19世纪伟大数学家高斯（Gauss，1777-1855年）曾说："研究欧拉的著作永远是了解数学的最好方法。"欧拉的父亲保罗·欧拉（PaulEuler）也是一个数学家，原希望小欧拉学神学，同时教他一点教学。由于小欧拉的才人和异常勤奋的精神，又受到约翰·伯努利的赏识和特殊指导，当他在19岁时写了一篇关于船桅的论文，获得巴黎科学院的奖的奖金后，他的父亲就不再反对他攻读数学了。1725年约翰·伯努利的儿子丹尼尔·伯努利赴俄国，并向沙皇喀德林一世推荐了欧拉，这样，在1727年5月17日欧拉来到了彼得堡。1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1735年，欧拉解决了一个天文学的难题（计算慧星轨道），这个问题经几个著名数学家几个月的努力才得到解决，而欧拉却用自己发明的方法，三天便完成了。然而过度的工作使他得了眼病，并且不幸右眼失明了，这时他才28岁。1741年欧拉应普鲁士彼德烈大帝的邀请，到柏林担任科学院物理数学所所长，直到1766年，后来在沙皇喀德林二世的诚恳敦聘下重回彼得堡，不料没有多久，左眼视力衰退，最后完全失明。不幸的事情接踵而来，1771年彼得堡的大火灾殃及欧拉住宅，带病而失明的64岁的欧拉被围困在大火中，虽然他被别人从火海中救了出来，但他的书房和大量研究成果全部化为灰烬了。沉重的打击，仍然没有使欧拉倒下，他发誓要把损失夺回来。在他完全失明之前，还能朦胧地看见东西，他抓紧这最后的时刻，在一块大黑板上疾书他发现的公式，然后口述其内容，由他的学生特别是大儿子A·欧拉（数学家和物理学家）笔录。欧拉完全失明以后，仍然以惊人的毅力与黑暗搏斗，凭着记忆和心算进行研究，直到逝世，竟达17年之久。