基本概念

图

图(Graph)由顶点集 V 和边集 E 组成,记作 G=(V,E)G=(V, E)。边可有方向(有向图)也可无方向(无向图),可带权值(网)。

常用术语

  • 邻接:两个顶点之间有边相连
  • 度:无向图中顶点关联的边数;有向图中分为入度和出度
  • 路径:顶点序列,边上可不重复(简单路径)
  • 回路(环):起点与终点相同的路径
  • 连通:无向图中任意两顶点之间都有路径;有向图中任意两顶点互相可达称为强连通
  • 连通分量:无向图的极大连通子图
  • 生成树:连通图的极小连通子图,包含全部顶点但只有 n-1 条边

图的性质

  1. 无向图中所有顶点的度数之和等于边数的 2 倍
  2. 有向图中所有顶点的入度之和等于出度之和,等于边数
  3. 具有 n 个顶点的无向完全图有 n(n−1)2\frac{n(n-1)}{2} 条边
  4. 具有 n 个顶点的有向完全图有 n(n−1)n(n-1) 条边

习题

习题 1

下列关于图的说法中,错误的是( )

(A) 无向图中所有顶点的度数之和等于边数的 2 倍 (B) 有向图中所有顶点的入度之和等于所有顶点的出度之和 (C) 具有 n 个顶点的无向完全图有 n(n-1)/2 条边 (D) 具有 n 个顶点的有向完全图有 n(n-1)/2 条边

图完全图顶点度数有向图

解题思路:

本题考查图的基本性质判断。思路是逐条核对四个选项所依据的经典结论:无向图的度数和等于边数的 2 倍,有向图入度之和等于出度之和,而完全图的边数要区分有向与无向两种情形。

详细步骤:

  1. 选项 (A) 正确:无向图中每条边关联两个顶点,对总度数的贡献是 2,因此所有顶点的度数之和等于边数的 2 倍。
  2. 选项 (B) 正确:有向图中每条弧贡献一个入度和一个出度,因此所有顶点的入度之和等于出度之和。
  3. 选项 (C) 正确:无向完全图中每对顶点之间恰有一条边,边数为 n(n−1)2\frac{n(n-1)}{2}。
  4. 选项 (D) 错误:有向完全图中每对顶点之间有两条方向相反的边,故边数为 n(n−1)n(n-1);n(n−1)2\frac{n(n-1)}{2} 是无向完全图的边数。

最终答案:

D。

习题 2

简述图的基本概念及常见术语。

图顶点集与边集顶点度数连通性

解题思路:

本题考查图的基本概念与常用术语。答题时先给出图的定义与两种分类,再按“点与边的关系—顶点度数—路径与回路—连通性—图的性质”逐条解释术语。

详细步骤:

  1. 图由顶点集和边集组成,按边是否有方向可分为有向图和无向图。
  2. 邻接:两个顶点之间有边相连;度:与顶点关联的边数,有向图中分为入度和出度。
  3. 连通:任意两个顶点之间存在路径;连通分量:图中极大连通子图。
  4. 路径:从一个顶点到另一个顶点的边序列;回路:首尾相同的路径;权:边上的数值;生成树:包含全部顶点且无回路的极小连通子图。

最终答案:

图由顶点集和边集组成,分为有向图、无向图。常见术语:邻接(两顶点有边)、度(关联边数,有向图分入度/出度)、连通(任意两顶点有路径)、权(边上的数值)、路径、回路、连通分量、生成树等。

发现内容有问题?

告诉我们哪里需要改进。