基本概念
定义
定义是对概念、术语或对象含义的精确描述。理解定义是学习任何知识领域的基础,每个概念都有其明确的定义。
图
图(Graph)由顶点集 V 和边集 E 组成,记作 。边可有方向(有向图)也可无方向(无向图),可带权值(网)。
- 邻接:两个顶点之间有边相连
- 度:无向图中顶点关联的边数;有向图中分为入度和出度
- 路径:顶点序列,边上可不重复(简单路径)
- 回路(环):起点与终点相同的路径
- 连通:无向图中任意两顶点之间都有路径;有向图中任意两顶点互相可达称为强连通
- 连通分量:无向图的极大连通子图
- 生成树:连通图的极小连通子图,包含全部顶点但只有 n-1 条边
- 无向图中所有顶点的度数之和等于边数的 2 倍
- 有向图中所有顶点的入度之和等于出度之和,等于边数
- 具有 n 个顶点的无向完全图有 条边
- 具有 n 个顶点的有向完全图有 条边
习题 1
下列关于图的说法中,错误的是( )
(A) 无向图中所有顶点的度数之和等于边数的 2 倍 (B) 有向图中所有顶点的入度之和等于所有顶点的出度之和 (C) 具有 n 个顶点的无向完全图有 n(n-1)/2 条边 (D) 具有 n 个顶点的有向完全图有 n(n-1)/2 条边
解题思路:
本题考查图的基本性质判断。思路是逐条核对四个选项所依据的经典结论:无向图的度数和等于边数的 2 倍,有向图入度之和等于出度之和,而完全图的边数要区分有向与无向两种情形。
详细步骤:
- 选项 (A) 正确:无向图中每条边关联两个顶点,对总度数的贡献是 2,因此所有顶点的度数之和等于边数的 2 倍。
- 选项 (B) 正确:有向图中每条弧贡献一个入度和一个出度,因此所有顶点的入度之和等于出度之和。
- 选项 (C) 正确:无向完全图中每对顶点之间恰有一条边,边数为 。
- 选项 (D) 错误:有向完全图中每对顶点之间有两条方向相反的边,故边数为 ; 是无向完全图的边数。
最终答案:
D。
习题 2
简述图的基本概念及常见术语。
解题思路:
本题考查图的基本概念与常用术语。答题时先给出图的定义与两种分类,再按“点与边的关系—顶点度数—路径与回路—连通性—图的性质”逐条解释术语。
详细步骤:
- 图由顶点集和边集组成,按边是否有方向可分为有向图和无向图。
- 邻接:两个顶点之间有边相连;度:与顶点关联的边数,有向图中分为入度和出度。
- 连通:任意两个顶点之间存在路径;连通分量:图中极大连通子图。
- 路径:从一个顶点到另一个顶点的边序列;回路:首尾相同的路径;权:边上的数值;生成树:包含全部顶点且无回路的极小连通子图。
最终答案:
图由顶点集和边集组成,分为有向图、无向图。常见术语:邻接(两顶点有边)、度(关联边数,有向图分入度/出度)、连通(任意两顶点有路径)、权(边上的数值)、路径、回路、连通分量、生成树等。
