图论

图论研究图——由边连接顶点的结构——作为成对关系和网络的数学模型。

Definition

对图的数学研究，图是由一组顶点和一组边（每条边连接一对顶点）组成的集合，以及在这些连接结构下不变的性质。

Scope

该领域涵盖图的结构、性质和参数：连通性、路径和环、树、平面性、着色、匹配和流，以及关于图属性如何相互制约的极值和概率问题。它是离散数学的核心，并为计算机科学、运筹学以及自然科学和社会科学中的网络提供了语言。

Sub-topics

• extremal graph theory
• graph coloring
• graph fundamentals
• trees and spanning structures

Core questions

• 图的连通性、度序列或环结构会产生哪些结构性质？
• 图何时可以在平面上无交叉地绘制或用少量颜色着色？
• 在避免给定子结构的情况下，图可以有多大或多稠密？
• 路径、匹配和流如何实现网络优化？

Key concepts

• 顶点、边和度
• 连通性和连通分量
• 路径、环和树
• 平面性
• 图着色
• 匹配和流

Clinical relevance

图对通信和交通网络、社会和生物交互网络、电路和依赖结构以及调度问题进行建模，使图论成为计算机科学和运筹学的基础工具。

History

图论起源于欧拉1736年对哥尼斯堡七桥问题的解决，并在20世纪通过对图着色、连通性的研究以及埃尔德什（Erdos）、塔特（Tutte）等人的概率和结构方法而成熟。

Key figures

• Leonhard Euler
• William Tutte
• Bela Bollobas

Seminal works

• diestel2017
• bollobas1998

Frequently asked questions

图和网络有什么区别？

图是顶点和边的抽象数学对象；网络通常指赋有额外数据（如权重、容量或方向）以模拟真实系统的图。

哥尼斯堡七桥问题为何重要？

欧拉证明了不存在一条路径可以恰好穿过七座桥各一次，他将问题抽象为顶点和边，从而奠定了图论和拓扑学的基础。