1.图的基础
i.图的定义
图是由顶点的有穷非空集合和顶点之间边的集合组成，表示为G（V,E），其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。其中G为有穷非空。
图有分有向图和无向图。
若顶点vi到vj之间的边没有方向，则这条边为无向边，表示为（vi，vj）或（vj，vi）。
反之为有向边（或弧），表示为＜vi，vj＞，其中vi称为弧尾，vj称为弧头。
若图中所有边都为无向边，则该图为无向图，反之若都为有向边，则为有向图。
简单图：不存在顶点到其自身的边，且同一条边不重复出现。 王道书只讨论简单图。
简单无向图：
简单有向图：
边的权：赋予每个边一个权值
带权网/图：每个边都带有权
带权路径长度：一条路径上所有边的权值之和
ii.顶点
无向图：顶点v的度：依附于该顶点的边的条数，既为$TD(v)$
在具有n个顶点、e条边的无向图
有向图：
- 入度：是以顶点v为终点的有向边的数目，记为$ID(v)$；
- 出度：是以顶点v为起点的有向边的数目，记为$OD(v)$；
- 顶点v的度 $TD(v)=ID(v)+OD(v)$
iii.顶点-顶点关系
- 路径： $v_p到v_q$之间的顶点序列(序列中不出现重复的顶点称为简单路径)
- 回路:第一个顶点和最后一个顶点相同的路径(除了第一个顶点和最后一个顶点外，其余顶点不重复的路径称为简单回路)
iv.连通图
无向图：如果两个顶点之间有路径，则称这两个顶点是连通的。如果图中任意两个顶点都是连通的，那么该图为连通图。
常见考点：
对于$n$个顶点的无向图，若为连通图，则最少有$n-1$条边，若为非连通图，最多有$C_{n-1}^2$条边
有向图：如果对于任意两个顶点vi和vj，都存在vi到vj和vj到vi的路径，则称那图为强连通图。
常见考点：
对于$n$个顶点的有向图，若为强连通图，则最少有$n$条边
v.子图
设有两个图$G=(V,E)、G’=(V,E’)$，若V’是V的子集，E’是E的子集，称G’为G的子图。
若$V=V’$则G’为G的生成子图
连通分量：无向图中V尽可能大的连通子图
强连通分量：有向图中V尽可能大的强连通子图
连通图的生成树：包含全部全部顶点的一个极小连通子图（边尽量少）
若其顶点为$n$，则生成树有$n-1$条边
非连通图的生成森林：非连通图中的连通分量的连通树构成。
vi.几种特殊的图
- 无向完全图：任意两个顶点之间都存在边，即若$|V|=n$，则$|E|\in[0,C_n^2]$
- 有向完全图：任意两个顶点之间都存在方向相反的两条弧，即若$|V|=n$，则$|E|\in[0,2C_n^2]$
- 稀疏图：边数很少$\Leftrightarrow$稠密图：边数很多;分界线一般来说：$|E|<|V|log|V|$
- 树:不存在回路且连通的无向图（常见考点，若|E|>1，则必有回路）
- 有向树:一个顶点入度为0,其余为1的有向图
vii.总结
