1、图的定义图 G(V,E)V顶点集合非空E边集合顶点之间关系2、有向图 无向图无向图边没有方向双向互通A-B 与 B-A 是同一条边有向图边带方向称为弧起点弧尾终点弧头3、度、入度、出度无向图顶点度依附该顶点的边的条数有向图入度指向该点的边数出度从该点出发的边数顶点度 入度 出度握手定理必考无向图所有顶点度数之和 2× 边数有向图所有入度之和 所有出度之和 边数4、稠密图 稀疏图边少 → 稀疏图边多 → 稠密图无严格界限一般 Enlogn视为稀疏5、路径、回路、简单路径路径顶点依次相连的序列简单路径顶点不重复回路环起点 终点简单回路除起点终点外其余顶点不重复6、连通相关概念无向图连通两点之间有路径连通图任意两点都连通连通分量无向图极大连通子图有向图强连通双向都有路径强连通图任意两点互相可达强连通分量有向图极大强连通子图7、权与网边上带有数值距离、代价→ 带权图 网8、n 个顶点图边数考点无向完全图2n(n−1)条边有向完全图n(n−1) 条边