图论

维基百科，自由的百科全书

图论（-{graph theory}-）是数学的一个分支，它以图（-{graph}-）为研究对象，研究顶点（-{vertex}-）和边（-{edge}-，又称-{line}-）组成的图形的数学理论和方法。

图论中的图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用连接两顶点的边表示相应两个事物间具有这种关系。

图论起源于著名的柯尼斯堡七桥问题。

图论的研究对象相当于一维的拓扑学。

目录 1 历史 2 图论问题 3 重要的算法 4 参见

[编辑] 历史

[编辑] 图论问题

• 图的着色：
  • 边着色
  • 顶着色
  • 面着色
    • 四色定理

• 匹配问题
• 平面图

• 路径问题：
  • 柯尼斯堡七桥问题
  • 最小生成树
  • 最短路径
  • 遍历
• 连通性问题
• 网络流
  • 最大流
  • 最小费用最大流
  • 容量有上下界的最大流
  • 容量有上下界的最小费用最大流
• 独立集和团
  • 拉姆齐定理
• 拟阵

[编辑] 重要的算法

• 戴克斯特拉算法
• 克鲁斯卡尔算法
• 普里姆算法

[编辑] 参见

• 组合数学