图

通过点集合、边集合表示事物之间联系的概念
图（英文：Graph[1]）是图论的核心概念，它指某类具体事物和这些事物之间的联系。如果用点表示具体事物，用线段表示两个事物之间的联系，由点集合和线段集合可以构成一个图，这些点称为顶点或节点，线段称为边或支路。[7]
图论的历史可追溯至18世纪的哥尼斯堡七桥问题。瑞士数学家莱昂哈德·欧拉（Leonhard Euler）在1735年向圣彼得堡科学院提交的一篇论文《关于位置几何问题的解法》中将该问题形象地转化为一笔画问题，并给出了否定的结果，这一问题的论述标志着图论的诞生。[2][17]同时，他还提出了平面体（多面图）的欧拉公式，早期图论问题的解决为拓扑学的兴起创造了条件。[3]图论思想还与其他学科的难题有关，克希霍夫（Kirchhoff）在1847年运用图论知识解决了电路理论中求解联立方程组的问题，并引入了“树”的概念，但其思想并未受到人们的重视。后来，凯莱（A.Cayley）在有机化学领域发展了“树”的理论。[4]1878年，西尔维斯特（Sylvester）首次将“图”这一概念作为数学名词发表在《自然》杂志上。[5]进入20世纪，人们对图论的研究进入了更加细化的阶段。1927年，门格尔（Menger）建立了连通性理论。[6]1936年，柯尼希（Konig）出版了第一部关于图论的著作《有限图与无限图理论》。后来，学者们意识到可借助计算机工具解决图论问题，1979年，阿佩尔（K.Appel）和哈肯（W.Hakan）证明了四色猜想成立。[5]
图具有一些基本性质，如所有顶点的度数之和等于它们作为端点的次数之和。[12]它包括有向图、完全图、二分图、平面图、树等多种类型。[11][12][13]而不同的图之间往往存在一些特殊关系，如同构、同胚。[7][16]图与图也能进行并、交、差以及环和等基本运算。[15]图的每边最多只有两个顶点，如果推广至任意个，可得到超图的概念。[18]此外，图在现实世界中具有广泛的应用价值，如在环境科学中，复杂的湿地河网水系可以被概化为图，利用图论方法能对其连通程度进行定量分析。[9]

定义

图：一个图
定义为一个偶对
，记作
，其中