图论

以图为研究对象的数学分支
image
图论是一门研究边和点的连接结构的数学理论，它是组合数学的一个分支，和其他数学分支如群论、矩阵论、拓扑学有着密切关系。图是图论的主要研究对象，它是由若干给定的顶点及连接两顶点的边所构成的图形，用于描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。图论起源于著名的柯尼斯堡七桥问题，该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。图论的研究对象相当于一维的单纯复形。图论是离散数学的重要研究对象之一，它被广泛应用于计算机科学、通信网络、社交网络、生物学、物理学等领域。

概述

图
是一个二元组
使得
的平方，所以E的元素是V的2-元子集。为了避免符号上的混淆，我们总是默认
。集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。
图论
图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。