图论tulun

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

图论

数学的 一个分支。研究一组点所代表的事物和联结这些点的线所代表的事件之间的相互关系和数学理论。起源于欧拉对七桥问题的研究。20世纪60年代以来发展很快，在网络问题和电网络理论中应用较多。

图论theory of graphs

不是研究一般几何图形的理论，而是只研究由点和线所连结成的图形的数学分支，这里，有时对所研究的点线图形还规定了线段的方向、长度或其他量。一个典型的、与经济学有关的图论问题是旅行推销员问题：怎样为一个计划到若干城市去推销商品的推销员设计一条旅行路线，使得他的旅费最省或推销的经济效益最高。
在数学上，图论研究基本上属于拓扑学范畴，但也应用很多现代数学知识。现代的图论研究又经常利用电子计算机作为工具。19世纪出现的著名的图论难题——四色问题（能否用四种颜色为任何一张地图着色），就是在1976年由两位美国数学家宣称，已经用电子计算机经1200小时的计算而得到解决。
图论的问题往往都很困难。像四色问题那样的经典难题相当多。还有些问题，如上面所举的旅行推销员问题，则已被证明是没有一般解法的。
经济学中有不少问题可利用图论作为工具。交通运输、工业组织、市场议价、经济计划、经济决策、社会选择等理论中都有不少图论问题。例如，可对一个经济决策问题的各层次、步骤及其后果，画出一张决策图；决策问题的解就是从中找出一条最优路线来。

图论

研究图的组合关系及结构的数学分支。图论起源于著名的七桥问题： 哥斯尼堡 (今苏联加里宁格勒，18世纪属东普鲁士) 城内有一条大河，河中有两个小岛，河两岸及河中的两岛由七座桥相连，试问是否存在一种走法，使每座桥走过一次且只走一次。数学家欧拉于1736年证明了这是一个不可能的问题，对这个问题的讨论，开创了图论的研究。图论中所研究的的图与常规数学中的图形不同，它不按比例画，点和线的位置有随意性，主要用来表示某些事物之间的某种特定关系。对于任何包含多种要素的系统，都可以用这样的图来描述这个系统的各部分之间的关系及结构，并且可用图的有关理论进行定量分析。实际上，目前对许多问题的研究，都已经用图来模拟了。例如，现在大家熟悉的网络图，是对复杂庞大的工程系统和管理系统进行研究的一种常用工具，有了它，能很方便地对这种系统描述和分析。网络图就是图的一种形式。因此，图论是研究网络问题的重要工具。图论在计算机科学、运筹学、控制论、系统分析、经济管理、运输网络、工程技术等方面，都有广泛应用。

图论

graph theory