图论：柯尼斯堡桥问题、艾科西亚游戏
图论是与线连接的点的网络有关的数学分支。的主题图论起源于休闲数学问题（参见 数字游戏），但它已发展成为数学研究的重要领域，并应用于化学，运筹学，社会科学和计算机科学。
图论的历史可以追溯到1735年，当时瑞士数学家 莱昂哈德·欧拉（Leonhard Euler）解决了柯尼斯堡桥问题。柯尼斯堡（Königsberg）桥梁问题是一个古老的难题，它涉及到是否有可能在横跨一条穿过岛屿的叉形河上的七座桥梁中的每一条上找到一条路径的可能性，但又不会跨过任何一座桥梁。欧拉认为没有这样的道路。他的证明仅涉及桥梁的物理布置，但从本质上讲，他证明了图论中的第一个定理。
如在图论中使用的，术语“图”不指数据图，例如折线图或条形图。相反，它是指一组的顶点（即点或节点）以及连接顶点的边（或线）。当任意两个顶点通过一个以上的边连接时，该图称为多图。没有循环且任意两个顶点之间最多具有一个边的图称为简单图。除非另有说明，否则图被认为是指简单图。当每个顶点通过边与其他每个顶点连接时，该图称为完整图。在适当的情况下，可以将方向分配给每个边以产生已知的有向图或有向图。
图的基本类型。
与每个顶点关联的重要数字是 度，定义为进入或退出该边的数量。因此，回路的顶点度为2。例如，图中所示的简单图的顶点都具有2度，而所示的完整图的顶点都具有3度。知道完整图中的顶点数可表征其本质。出于这个原因，完全图通常命名ķ ñ，其中ñ指顶点的所有顶点的数量，ķ ñ有度ñ - 1（翻译成现代图论的术语，欧拉对柯尼斯堡桥问题定理可以重述如下：如果在多图的边缘存在一条路径，一次遍历每个边缘一次，然后最多存在两个奇数个顶点；此外，如果路径在同一顶点处开始和结束，则没有顶点具有奇数度。）
图论中的另一个重要概念是 path，它是沿着图形边缘的任何路线。路径可以直接在两个顶点之间遵循一条边，或者可以通过多个顶点遵循多个边。如果有一条路径链接图中的任何两个顶点，则称该图已连接。在相同顶点处开始和结束而没有多次遍历任何边的路径称为电路或封闭路径。在访问每个顶点时，恰好跟随每个边缘一次的电路称为欧拉回路，该图称为欧拉图。连接了一个欧拉图，此外，它的所有顶点都具有偶数度。
图是顶点或节点以及一些或所有顶点之间的边的集合。当存在一条恰好遍历每个边缘一次的路径，从而该路径在同一顶点处开始和结束时，该路径称为欧拉回路，而该图称为欧拉图。欧拉（Eulerian）是指瑞士数学家Leonhard Euler，他在18世纪发明了图论。
1857年，爱尔兰数学家 威廉·罗恩·汉密尔顿（William Rowan Hamilton）发明了一个拼图游戏（“艾科西亚游戏”），后来以25英镑的价格卖给了游戏制造商。难题在于找到一种特殊的路径，后来称为哈密顿回路，沿十二面体（由12个五边形面组成的柏拉图实体）的边缘开始和结束于同一个角，同时恰好通过每个角一次。骑士之旅（参见 数字游戏：棋盘问题）是涉及哈密尔顿回路的娱乐性问题的另一个示例。哈密顿图比欧拉图更具挑战性，因为在连通图中存在哈密顿回路的必要和充分条件仍然未知。
哈密顿回路将路径在同一顶点上开始和结束（闭合回路），使得每个顶点都被精确访问一次的有向图称为哈密顿回路。19世纪的爱尔兰数学家威廉·罗恩·汉密尔顿（William Rowan Hamilton）开始了此类图的系统数学研究。
图论的历史和 拓扑关系密切，这两个领域共享许多共同的问题和技术。欧拉（Euler）将他在柯尼斯堡（Königsberg）桥问题上的工作称为“位置几何”的一个例子，而19世纪下半叶拓扑思想的发展被称为“位置分析”（“位置分析”）。 ” 在1750年发现的欧拉多面体式V - ë + ˚F = 2有关顶点的数量（V），边缘（ë）和面（˚F一的）多面体（如上述十二面体的实体，其面为多边形）。多面体的顶点和边缘在其表面上形成图形，这种概念导致人们考虑在其他表面（例如圆环面（实心甜甜圈的表面））上的图形，以及它们如何将表面划分为圆盘状的面。欧拉公式很快被推广到曲面，即V – E + F = 2 – 2 g，其中g表示曲面的属或“甜甜圈孔”的数量（请参见 欧拉特性））。在考虑了通过嵌入图将表面划分为多边形的表面之后，数学家开始研究通过将多边形粘贴在一起来构造表面以及后来更一般的空间的方法。这是组合拓扑学领域的开始，后来通过法国数学家亨利·庞加莱（HenriPoincaré）等人的工作，发展成为所谓的代数拓扑学。
图论与拓扑之间的联系导致了一个称为 拓扑图理论。这方面的一个重要问题是平面图。这些图可以在平面上（或等效地在球体上）以点线图的形式绘制，除了在它们相交的顶点处，没有其他边交叉。具有四个或更少顶点的完整图是平面的，但是具有五个或五个以上顶点（K 5）的完整图则不是平面。如果没有顶点之间的边相交，则不能在平面或球面上绘制非平面图。使用点和线图来表示图实际上是从19世纪化学发展而来的，其中带字母的顶点表示单个原子，而连接线表示化学键（度数对应于化合价）），其中平面度会产生重要的化学后果。在这种情况下，单词图的首次使用归因于19世纪的英国人詹姆斯·西尔维斯特（James Sylvester），他是对计数代表分子的特殊类型图感兴趣的几位数学家之一。
另一类图是完整的二部图K m，n的集合，这些图由简单的图组成，这些图可以划分为m和n个顶点的两个独立集合，从而每个集合和每个顶点的顶点之间都没有边一组中的一个通过边连接到另一组中的每个顶点。像K 5一样，二分图K 3，3也不是平面的，这证明了英国休闲问题主义者亨利·杜德尼（Henry Dudeney）在1913年提出的解决“气-水-电”问题的主张。1930年，波兰数学家Kazimierz Kuratowski证明，任何非平面图都必须包含某种类型的K 5或K 3，3。虽然K 5和K 3，3不能嵌入球体中，但它们可以嵌入圆环中。图形嵌入问题涉及确定其中可以嵌入图形的表面，从而概括了平面性问题。直到1960年代后期，才针对所有n解决了完整图K n的嵌入问题。
拓扑图理论的另一个问题是 地图着色问题。这个问题是众所周知的结果四色图问题，该问题询问是否可以仅使用四种颜色对每个地图上的国家/地区进行着色，以使共享边的国家/地区具有不同的颜色。这个问题最初是在1850年代由当时伦敦大学的学生弗朗西斯·古思里（Francis Guthrie）提出的，这个问题有着悠久的历史，充满了不正确的解决方案。以等效的图论形式，可以将这个问题转化为一个问题，以询问平面图的顶点是否可以始终仅通过使用四种颜色以通过边连接的顶点具有不同颜色的方式进行着色。最终在1976年通过对近2,000种特殊配置进行计算机检查来证明了这一结果。有趣的是，与高属表面上的颜色图所需的颜色数量有关的相应着色问题已于几年前得到了彻底解决。例如，圆环上的地图可能需要多达七种颜色。这项工作证实，自1890年以来，英国数学家珀西·希伍德（Percy Heawood）的公式正确地给出了除单面（称为单面）外的所有表面的这些着色数。克莱因瓶（Klein bottle），其正确的色号在1934年被确定。
间的电流在图论的利益是关于高效问题的算法寻找最优路径中的曲线图（根据不同的标准）。两个著名的例子是中国邮递员问题（访问每个边的最短路径至少一次）在1960年代得到了解决， 旅行商问题（最短路径在同一顶点处开始并到达每个边一次，这是一条最短的路径），由于它在路由数据，产品和人员中的应用而继续吸引着许多研究人员的注意力。有关此类问题的工作与线性规划领域有关，线性规划领域是由美国数学家乔治·丹茨格（George Dantzig）于20世纪中叶创立的。