图论

图论是以“图”为研究对象的一个数学分支，是组合数学和离散数学的重要组成部分。图是用来对对象之间的成对关系建模的数学结构，由“顶点”（又称“节点”或“点”）以及连接这些顶点的“边”（又称“弧”或“线”）组成。值得注意的是，图的顶点集合不能为空，但边的集合可以为空。图可能是无向的，这意味着图中的边在连接顶点时无需区分方向。否则，称图是有向的。下面左图是一个典型的无向图结构，右图则属于有向图。

[描述来源：Wikipedia；URL：https://en.wikipedia.org/wiki/Graph_theory]

[图片来源：Wikipedia；URL：https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)]

图可用于在物理、生物、社会和信息系统中建模许多类型的关系和过程。许多实际问题可以用图来表示。因此，图论成为运筹学、控制论、信息论、网络理论、博弈论、物理学、化学、生物学、社会科学、语言学、计算机科学等众多学科强有力的数学工具。在强调其应用于现实世界的系统时，网络有时被定义为一个图，其中属性(例如名称)之间的关系以节点和/或边的形式关联起来。

在计算机科学中,图用来表示通信、数据组织、计算设备、计算流等网络，在社交媒体、计算机芯片设计、自然语言处理、路径规划等很多方面有广泛应用。例如,网页之间的链接结构可以表示为一个有向图，其中顶点代表网页而有向的边表示从一个页面链接指向另一个。

发展历史

描述(300字)

1736年著名数学家Euler关于哥尼斯堡七桥问题（Seven Bridges of Königsberg）发表的一篇论文被广泛认为是图论的最早起源。随后的两百年间，图论都处在较为缓慢的萌芽阶段。研究基本停留在解决一些游戏中问题。这其中最著名的是Francis Guthrie于1852年提出的四色猜想（Four color theorem）。这一问题在之后的一百余年中一直没有得到证明。这一阶段，图论较为重要的应用成果包括：1845年，物理学家Gustav Kirchhoff利用图论中树型结构提出了Kirchhoff电路定律（Kirchhoff's circuit laws）用以计算电路中的电压和电流。1875年，Arthur Cayley在化学领域利用树型图解决了饱和氢化物同分异构体数目的计算问题。

到了1860-1930年间，图论从之前相对独立的拓扑学中汲取了很多内容。随着现代代数的发展，图论逐渐与拓扑学有了深入交叉。1936年匈牙利数学家Dénes König总结了200年来图论的发展历程和主要成果，出版了图论的第一部专著《有限图和无限图的理论》（Theorie der endlichen und unendlichen Graphen），标志着图论成为一门独立、系统的数学学科。学科的建立，加上计算机的发明和使用，大大加快了图论的发展速度。1976年，Kenneth Appel 和 Wolfgang Haken借助计算机历时1200小时给出了四色猜想问题的证明，成为图论历史上的一座里程碑。随后的半个世纪以来，随着计算机科学的进步，图论更是以惊人的速度向前发展，已产生了许多新的分支，如拓扑图论、代数图论、算法图论、应用图论、极值图论、拟阵图论、模糊图论、网络图论、超图理论、随机图论等。

主要事件

发展分析

瓶颈

图论中存在挑战并值得研究的问题包括

• 图枚举问题
• 子图、诱导子图问题
• 图着色问题
• 图的包容统一问题
• 路径问题
• 网络流问题
• 可见性问题
• 覆盖问题
• 分解问题
• 图分类问题

未来发展方向

由各种实际网络（互联网、社会网络、生物神经网等）分析需求抽象出的对超大图的研究

图论与概率论、代数等数学领域的交叉研究，如概率图论，极值图论等

图论与计算机科学在复杂度分析和复杂计算等领域的交叉研究

Contributor:Han Hao