Class 1 Graph

释义 Definition

在图论中，“Class 1 graph（第一类图）”通常指边染色数（chromatic index，记作 χ′(G)）等于该图的最大度数 Δ(G) 的图。也就是说，这类图的边可以用 Δ(G) 种颜色染色，使得任意两条相邻边（共享同一顶点）颜色不同。
（注：对应地，Class 2 graph 一般指 χ′(G)=Δ(G)+1。）

发音 Pronunciation (IPA)

/klæs wʌn ɡræf/

例句 Examples

A cycle graph with an even number of vertices is a class 1 graph.
顶点数为偶数的环图是第一类图。

By Vizing’s theorem, every simple graph is either a class 1 graph or a class 2 graph, depending on whether its edge chromatic number equals Δ or Δ+1.
根据维青定理，每个简单图要么是第一类图，要么是第二类图，取决于它的边染色数等于 Δ 还是 Δ+1。

词源 Etymology

“class”源自拉丁语 classis，原意与“等级、类别”相关；“graph”在数学语境中来自希腊语 graphein（“书写、描绘”），在现代数学里指由顶点与边构成的“图”。“Class 1 graph”字面意思就是“第一类的图”，用于区分边染色性质不同的两大类图。

相关词 Related Words

• Chromatic
• Chromatic Index
• Edge Coloring
• Maximum Degree
• Vizing's Theorem
• Class 2 Graph
• Bipartite Graph
• Δ (Delta)

文学与经典著作 Literary Works

• Graph Theory（Reinhard Diestel）——在边染色章节中讨论 Class 1 / Class 2 的划分与相关定理。
• Introduction to Graph Theory（Douglas B. West）——讲解边染色数、最大度数与维青定理时常用到“Class 1 graph”。
• Graph Theory with Applications（Bondy & Murty）——介绍边染色与典型例子时涉及第一类/第二类图的概念。