图论是数学的一个分支，研究由顶点及连接顶点的边构成的抽象结构——图。它研究邻接关系、连通性、通路和结构约束，而不依赖于图所表示的具体对象。图论与组合数学和计算机科学密切相关，为涉及道路、通信网络、分子结构以及谜题中可能走法的问题提供了通用的描述语言。在这一语境下，图表示的是关系，不一定是绘制出来的曲线。(web.math.princeton.edu)
起源与基本定义
图论发展中的一个奠基性事件，是莱昂哈德·欧拉于1736年解决了柯尼斯堡七桥问题。这个问题问的是：能否走出一条路线，恰好经过七座桥中的每一座一次？将各块陆地表示为顶点、桥表示为边后，决定性的特征便显现出来：四个顶点的度数全为奇数，因此这样的路线不存在。这一论证将关注点从距离和形状转向了连接方式。(ocw.mit.edu)
图通常记为 ，其中 是顶点集， 是边集。在简单无向图中，每条边都是由两个不同顶点构成的无序对；不允许有自环，也不允许同一对顶点之间有多条边。有向图则使用有序对，将从 到 的连接与反方向的连接区分开来。其他定义约定可以允许自环或平行边，而加权图则为边赋予费用、长度等数值。(ocw.mit.edu)
顶点的度数 是与该顶点关联的边的数量；在无向图中，一个自环计数两次。对于任何有限无向图，握手恒等式表明：
因此，度数为奇数的顶点必有偶数个。这些结论成立，是因为每条边都为关联总数贡献两次计数。(ocw.mit.edu)
连通性、路径与树
游走沿着相继的边行进，可以重复经过顶点或边。路径不重复经过顶点，而圈会回到起始顶点，除此之外不重复经过任何顶点。如果任意一对顶点之间都有路径相连，无向图就是连通的。图的连通分量是其极大连通子图。因此，连通性描述的是顶点之间能否到达，而不是到达所需的距离有多短或费用有多低。(ocw.mit.edu)
树是不含圈的连通无向图。树中任意两个顶点之间都恰好有一条路径，而具有 个顶点的有限树有 条边。森林是各个连通分量均为树的无圈图。生成树保留连通图的所有顶点，并选取足以维持连通、又不形成圈的边。(ocw.mit.edu)
欧拉迹恰好经过每条边一次；欧拉回路还要求终点与起点相同。对于至少有一条边的有限无向图，存在欧拉回路的充要条件是：所有非孤立顶点都属于同一个连通分量，且每个顶点的度数均为偶数。存在开放欧拉迹的充要条件是：满足上述连通性条件，且恰好有两个顶点的度数为奇数。(ocw.mit.edu)
着色与平面性
正常的顶点着色为各顶点分配颜色，使相邻顶点的颜色不同。色数是完成这种着色所需的最少颜色数。如果一个非空图的顶点可以划分为两个集合，且每条边都连接分属两个集合的顶点，那么它就是二分图；等价地说，它可以用至多两种颜色进行正常着色。这类图不含奇数长度的圈。着色可用于建模这样一类情形：彼此相连的对象必须获得互不相容的安排。(ocw.mit.edu)
平面图可以画在平面上，使各条边除公共端点外互不相交。对于连通图的平面嵌入，欧拉公式为：
其中 包括无界的外部面。由此可知，至少有三个顶点的简单平面图至多有 条边。四色定理指出，每个有限平面图都可以用至多四种颜色进行正常顶点着色。平面性关注的是是否存在符合要求的画法，而不是某一种具体画法看起来如何。(ocw.mit.edu)
算法与计算问题
图可以使用不同的数据结构存储。邻接表记录每个顶点的邻接顶点，所需存储空间与 成正比。邻接矩阵通过行和列记录连接关系，所需存储空间与顶点数的平方成正比。这些表示方式支持不同的图处理方法。(ocw.mit.edu)
图算法通常用于回答可达性或优化问题。广度优先搜索逐层探索顶点，能够解决无权图的最短路径问题，即使从起始顶点出发所经过的边数最少。当边权非负时，迪杰斯特拉算法可用于求解加权最短路径问题。(ocw.mit.edu)
另一些表面上相似的问题，却具有不同的计算复杂性。哈密顿圈在返回起点之前恰好访问每个顶点一次，而欧拉回路要求遍历所有边。判定一般有限图是否具有哈密顿圈，是一个 NP 完全问题。因此，访问顶点与遍历边的区别，会带来计算性质截然不同的问题。(live.ocw.mit.edu)
代数方法与应用
谱图论通过与图相关的矩阵及其特征值与特征向量，将图的结构与线性代数联系起来。对于简单无向图，邻接矩阵 记录边，对角矩阵 记录顶点的度数。拉普拉斯矩阵为 。其零特征值的重数等于图的连通分量数，从而为连通性提供了代数描述。(math.mit.edu)
图模型将关系与无关的几何细节分离开来。在道路模型中，顶点可以表示交叉路口；在分子模型中，顶点可以表示原子；在谜题模型中，顶点可以表示各种局面。代数方法和谱方法还可用于随机游走、网络划分、电网络分析和网页搜索。因此，同一个底层图可以根据所研究的问题，通过组合论证、数值矩阵或计算过程等不同方式加以研究。(web.math.princeton.edu)