图论
维基百科,自由的百科全书
图论(graph theory)是数学的一个分支,它以图(graph)为研究对象,研究顶点(vertex)和边(edge,又称line)组成的图形的数学理论和方法。
图论中的图是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用顶点代表事物,用连接两顶点的边表示相应两个事物间具有这种关系。
图论起源于著名的柯尼斯堡七桥问题。
图论的研究对象相当于一维的拓扑学。
目录 |
[编辑] 历史
[编辑] 图论问题
- 图的着色:
- 边着色
- 顶着色
- 面着色
- 匹配问题
- 平面图
[编辑] 重要的算法
- 戴克斯特拉算法
- 克鲁斯卡尔算法
- 普里姆算法
[编辑] 参见