图论

图论 (Graph theory) 是数学的一个分支，图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

图

图 (Graph) 是一个二元组G = (V(G), E(G)。其中 V(G)是非空集，称为点集 (Vertex set)，对于 V 中的每个元素，我们称其为 顶点 (Vertex) 或 节点 (Node)，简称 点； E(G)为 V(G)各结点之间边的集合，称为 边集 (Edge set)。
常用 G = (V, E) 表示图。
当 V, E 都是有限集合时，称 G 为 有限图。
当 V 或 E 是无限集合时，称 G 为 无限图。

图的分类

  1. 按照边的方向
    1. 无向图，一种特殊的有向图。
    2. 有向图

      树：无环无向连通图

拓扑图与拓扑排序

指有向无环图(Directed acyclic graph, DAG)
拓扑排序

基本概念

如果路径上的各顶点均不互相重复，称这样的路径为简单路径。如果路径上的第一个顶点与最后一个顶点重合，这样的路径称为回路(cycle)或环或圈。