图
图（Graph） 就是由 顶点 和 边 组成的 非线性结构，用来表示 多对多 的关系。
图 G 是由集合 V 和 E 构成的二元组，记作 G=(V,E) ,其中：
- V是图中 顶点 的 非空 有限 集合
- E 是图中 边 的 有限集合
解释： 在图中：
- 数据元素 用 顶点 表示
- 数据元素之间的 关系 用 边 表示。
注意：不可以是空图。即：必须有一个顶点
提示：没有根节点
特点
图中 任一顶点 都有可能与 其他顶点 有关系
分类
- 有向图
- 有向完全图
- 无向图
- 无向完全图
- 连通图
- 简单图
- 简单无向图
- 简单有向图
有向图
图中 所有边 都有 方向 的
若图中每条边都是有方向的，那么顶点之间的关系用 <vi,vj> 表示，说明从 vi 到 vj 有一条有向边（也称为弧)：
vi是有向边的起点，称为弧尾yj是有向边的终点，称为弧头。
无向图
图中 每条边 都是 无方向 的
顶点 vi 和 vj 之间的边用 (vi，yj) 表示。
在无向图中 (vi，yj) 与 (vj，yi) 表示的是同一条边。
连通图
路径：在无向图，一个顶点 可以 直接 或 间接 到达 另一个顶点。如上图：V1 可以到 V3 ，V3 可以到 V4 ，也就是说：V1 可以到 V4
路径长度：路径上边的数量
连通图： 无向图中，任意 两个顶点 之间都有 路径 相连
如上图：V1 与 V3 连通，V3 与 V4 连通，也就是说：V1 与 V4 连通
无向完全图
无向图 任意 两个顶点 之间都有 边，称之为 无向完全图
提示：有 n 个顶点的无向完全图有 \frac{n(n-1)}{2} 条边
有向完全图
有向图，任意 两个顶点 之间都有 方向相反 的 两条边
提示：有 n 个顶点的无向完全图有 n(n-1) 条边
简单图
- 不存在重复边
- 不存在顶点到自身的边
简单无向图
无向图中，不存在重复边，不存在顶点到自身的边
n 个顶点，边的数量：
最少边的数量：
n-1最多边的数量： \frac{n(n-1)}{2} 条边
简单有向图
有向图中，不存在重复边，不存在顶点到自身的边
n 个顶点，边的数量：
最少边的数量：
n-1最多边的数量： n(n-1) 条边
概念
权值：边上标有某个含义的数值，该数值称为该边的权值
带权图：边上带有权值的图
网：同 带权图
题
某简单无向连通图 G 的顶点数为 n，则图 G 最少和最多分别有（）条边。
A、n, n2/2
B、n-1,n*(n-1)/2
C、n, n*(n-1)/2
D、n-1, n2/2
分析
分析方式一：根据 简单无向图 可知选择 B
分析方式二：当 n = 1，代入公式，可知选择 B
答案
B