图论tulun

一个数学分支，以由给定点的集合以及连结两点的线所构成的图形为研究对象.早在1736年前，莱布尼兹曾提到过“位置几何学”，但既未给出较明确的含义，也未引起数学家的注意.欧拉深入研究了流传的“哥尼斯堡七桥问题”，指出这是属于几何学的问题，但却不必求出尺寸大小，也不能通过量的计算来求出解答，由此，欧拉重提“位置几何学”，确认这个几何分支只讨论与位置有关的关系，研究位置的性质；不去考虑长短大小，也不涉及量的计算.欧拉发表了著名论文“哥尼斯堡的七座桥”，从而开创了一个新的数学分支——图论.
早期图论问题多半与智力游戏有关.如哥尼斯堡七桥问题及如在我国流行的一笔画问题等.
从19世纪中叶到本世纪30年代，是图论发展的第二阶段.图论问题被大量提出，并且得到了应用.如基尔霍夫、凯莱分别在电网络及化学研究中，独立地引入树的概念，取得了重大成功.图论的典型问题有哈密尔顿提出的“周游问题”和“货郎担问题”，以及地图染色的“四色问题”，图的可平面性问题等等.1936年图论的第一本专著问世.
本世纪中叶图论发展进入一个崭新阶段.由于交通运输、生产、军事，以及计算机网络等方面提出了大量的实际问题，特别是大型计算机使得大规模的计算问题的求解成为可能，而使图论及其应用得到飞速发展.图论的开创性工作是建立了网络流理论.图论与线性规划、动态规划等优化理论和方法，已经相互渗透，并促进了组合最优化等理论及算法的研究.