数学课堂
进阶≈ 14 分钟未开始

图论基础

核心概念

图:由若干顶点(点)和连接顶点的边(线)组成的结构,记作 G=(V,E)G=(V,E)。VV 是顶点集,EE 是边集。

度:与某顶点相连的边数,记作 deg⁡(v)\deg(v)。

常见概念:

  • 简单图:没有重边、没有自环的图;
  • 完全图 KnK_n:nn 个顶点两两都有边相连,共 n(n−1)2\dfrac{n(n-1)}{2} 条边;
  • 路径 / 回路:依次经过顶点的走法;起点终点相同的路径是回路;
  • 连通图:任意两点之间都有路径相连。

直观理解 · 动手试试

图论是"把关系画成点和线"。人与人的认识、城市与道路、球队之间的比赛——凡是"一些对象 + 它们之间的两两关系",都能抽象成图。一旦画成图,许多看似复杂的问题就变成了数点、数边、数度的组合问题。

最基础也最有用的量是度:一个点连了几条边。很多竞赛题的突破口,就是去统计每个点的度、或者所有度的总和。学会"把生活语言翻译成图语言",是用图论解题的第一步。

完全图

K6:6 点两两相连

边数
C(6,2) = 15
每点的度
5
6

每两个顶点之间一条边,共 C(n,2) = n(n−1)/2 条;每个顶点与其余 n−1 个相连,度为 n−1。

例题 1完全图的边数

66 个顶点的完全图 K6K_6 有多少条边?

▸查看解答步骤

答: K₆ 有 15 条边

例题 2握手情境建模

66 个人两两握手一次,把人看作顶点、握手看作边。每个人(顶点)的度是多少?

▸查看解答步骤

答: 每人度为 5

即时练习

完全图 K5K_5 有多少条边?

C52=5×42=10C_5^2 = \frac{5\times4}{2} = 10。

完全图 K5K_5 中每个顶点的度是多少?

每个顶点与其余 44 个相连,度为 n−1=4n-1 = 4。

1010 支球队两两比赛一场,共要进行多少场比赛?

C102=10×92=45C_{10}^2 = \frac{10\times9}{2} = 45 场。

下列关于"度"的说法正确的是?

度是与该顶点相连的边数度是图中顶点的总数度是图中边的总数度一定是偶数

度 = 与该顶点相连的边数,不同顶点的度可以不同,也可以是奇数。

    易错点

    • 完全图边数用 n2n^2。 是 n(n−1)2\dfrac{n(n-1)}{2}(每对点一条边),不是 n2n^2 或 n(n−1)n(n-1)。
    • 混淆度与顶点数。 度是"连出的边数",针对单个顶点,而非全图规模。
    • 建模时点边对应错。 先想清楚"谁是顶点、什么关系是边",翻译错了后面全错。

    下一步

    前置知识点
    —
    接下来学习