图——图的基本概念

1、图的定义
图 G=(V,E)
V：顶点集合（非空）
E：边集合（顶点之间关系）

2、有向图 & 无向图
无向图边没有方向，
双向互通A-B 与 B-A 是同一条边
有向图边带方向，称为弧，
起点：弧尾，终点：弧头

3、度、入度、出度
无向图顶点度：依附该顶点的边的条数
有向图
入度：指向该点的边数
出度：从该点出发的边数
顶点度 = 入度 + 出度
握手定理（必考）
无向图：所有顶点度数之和 = 2× 边数
有向图：所有入度之和 = 所有出度之和 = 边数

4、稠密图 & 稀疏图
边少 → 稀疏图
边多 → 稠密图
无严格界限，一般 E<nlogn视为稀疏

5、路径、回路、简单路径
路径：顶点依次相连的序列
简单路径：顶点不重复
回路（环）：起点 = 终点
简单回路：除起点终点外，其余顶点不重复

6、连通相关概念
无向图
连通：两点之间有路径
连通图：任意两点都连通
连通分量：无向图极大连通子图
有向图
强连通：双向都有路径
强连通图：任意两点互相可达
强连通分量：有向图极大强连通子图

7、权与网
边上带有数值（距离、代价）→ 带权图 = 网

8、n 个顶点图边数考点
无向完全图：2n(n−1)条边
有向完全图：n(n−1) 条边