Forbidden Subgraph

定义 Definition

forbidden subgraph（禁用/禁止子图）：在图论中，指不允许出现在某个图或某类图中的子图。常见于极值图论与图性质刻画：通过规定“不能包含某些子图”，来定义或描述一类图（例如：不含三角形的图、无 \(K_5\) 或 \(K_{3,3}\) 子图的图等）。在不同语境下也可能指“禁止作为（诱导）子图出现”的版本。

发音 Pronunciation (IPA)

/fɔːˈbɪd(ə)n ˈsʌbɡrɑːf/

例句 Examples

A triangle is a forbidden subgraph in a triangle-free graph.
在无三角形图中，三角形就是一个禁止子图。

Theorem statements in extremal graph theory often bound the maximum number of edges in an \(n\)-vertex graph that avoids a given forbidden subgraph \(H\).
极值图论中的定理常常会给出：在一个有 \(n\) 个顶点且避免某个禁止子图 \(H\) 的图中，边数最多能有多少的上界。

词源 Etymology

forbidden 源自 forbid（禁止），表示“不允许的”；subgraph 由 *sub-*（“下级/部分”）+ graph（图）构成，表示“一个图的部分结构（子图）”。合起来就是“被规则排除、不能出现的子图”，这一术语在20世纪图论发展、尤其是极值问题研究中被广泛使用。

相关词 Related Words

• Forbidden
• Subgraph
• Induced
• Minor
• Extremal
• Turán
• Planar
• Bipartite

文献与作品 Literary / Notable Works

• Diestel, Graph Theory（《图论》）：在极值图论与“排除子图”相关章节中常使用 forbidden subgraph 的表述与思想。
• Bollobás, Extremal Graph Theory（《极值图论》）：以“给定禁止子图 \(H\)，研究避免 \(H\) 的图的最大边数”等为核心主题。
• West, Introduction to Graph Theory（《图论导引》）：讨论Turán型问题、无某些子图的图类时会出现该术语或同类表述。
• Kuratowski’s Theorem 相关教材/综述：用“禁止结构”（常表述为禁止子图或禁止细分）刻画平面图（与 \(K_5\)、\(K_{3,3}\) 相关）。