一、基本概念
图：G（V，E），V顶点的集合，不可为空；E边的集合可为空
弧：顶点的有序对<u,v>，成为顶点u到顶点v的一个弧，u为弧尾,v为弧头。
路径：从一个顶点到另一个顶点的边的有序序列
简单路径：路径上顶点都不相同的路径
简单回路：图的顶点序列中除第一个顶点和最后一个顶点相同外，其余顶点都不重复出现的回路。
稀疏图：一般，边数小于完全图的5%,|E|<|V|log|V|
稠密图:接近完全图
完全图:任意两个顶点之间存在边（有向图则任意两个顶点之间存在方向相反的两个弧）
无向图：边数,n(n-1)/2，有向图 n(n-1)
无向图:边是顶点的无序对
有向图:边是顶点的有序对
度：与顶点相关联的边的数目
出度：从一个顶点发出几条边
入度：从有几个边到该顶点
子图：图G‘(V',E')，和图G(V,E)，其中V'是V的子集，E'是E的子集，则称G'为G的子图
生成子图,|V'|=|V|，子图的顶点数与原图相同
有根图：在一个有向图中，存在一个顶点V0,从该顶点有路径可以到达图中其他所有顶点
则称此图为有根图，其中V0称为此图的根
数为有根图，森林为有根图的集合
连通图：
无向图中，顶点v到顶点w之间有路径存在，则称这两个顶点是连通的
若G的任意两个顶点都是连通的，则称图G为连通图。（任意两个顶点间有路径存在）
极大连通子图：无向图的连通分量。极大要求包括所有的边。
极小连通子图：使得边最小，同时保持连通性。
有向图：v到w有一个条有向路径，同时w到v有一条有向路径,则称这两个顶点强连通。
强连通图：有向图中任意一对顶点之间都是强连通的。
强连通分量：有向图的极大强连通子图。
生成树：包含图中全部顶点的一个极小连通子图。