5.1 图

图的基本概念

(1)

无向图：边是无向边，用无序偶对(v1,v2)来表示
有向图：边是有向边，也称弧，用有序偶<v1,v2>来表示，v1称为弧尾，v2称为弧头
网：边是带权的图，图可以看成是边的权都为1的网

(2)

简单图：不存在顶点到其自身的边，且同一条边不重复出现
无向完全图：任意两个顶点之间都存在边，有n个顶点的无向完全图有 n × (n - 1) / 2条边
有向完全图：任意两个顶点之间都存在方向护卫相反的两条弧，有n个顶点的无向完全图有 n × (n - 1) 条弧
稀疏图&稠密图：有很少条边或弧的图称为稀疏图，反之称为稠密图，相对的概念。

(3) 顶点与边的关系

无向图：TD(v)表示顶点v的度
有向图：TD(v) = ID(v) + OD(v) 表示顶点v的都等于v的入度加出度
路径，环

(4) 连通图

连通图：任意两个点有路径的无向图（连通图内所有点的边都在连通图里）
强连通图：任意两个点有路径的有向图（连通图内所有点的边都在连通图里）
连通分量：无向图中极大连通子图（即尽可能多的边，顶点的集合）
强连通分量：有向图中极大连通子图
生成树：极小连通子图，n个顶点，n-1条边（所以不存在环）