图的基本概念

无向图 vs 有向图
无向图：(v，w)；有向图：
在图形中那个的区别就是带不带箭头

简单图 vs 多重图

1. 不存在重复边
2. 不存在顶点到自身的边

=> 简单图

完全图
任意两个顶点之间都存在边，n个顶点有n(n-1)/2条边

子图
一个图V’的边和顶点都属于V，称V‘是V的子图

连通图 vs 强连通图

1. 连通图只针对无向图 => 连通性，强连通图只针对有向图 => 强连通性
2. 非连通图的边最多可以有C² _n-1，连通图最少有n-1
3. 强连通图的边最少需要n

生成树 vs 生成森林

1. 生成树是连通图的包含图中的所有顶点的极小连通子图
   1. 顶点为n，生成树的边有n-1
2. 非连通图的各个连通分量构成非连通图的生成森林
   
   

顶点的度、入度和出度

1. n个顶点，e条边的无向图，度为2e，即无向图的全部顶点的度的和 = 边数 ✖ 2
   1. 无向图没有入度、出度之分
2. n个顶点，e条边，出度 = 入度 = 边数 = e

边的权和网
边上带权值的图称带权图，即网

稀疏图、稠密图

路径、路径长度和回路

简单路径、简单回路
顶点不重复出现的路径称为简单路径
除开始顶点和结束顶点，其他顶点不重复出现的路径称为简单回路

距离
前提是两顶点存在路径，路径长度 = 距离

有向树
一个顶点的入度为0，其余顶点入度为1的有向图称有向树