Vertex Coloring

释义 Definition

顶点着色：图论中的一种“着色”方式，给图（graph）的每个顶点分配一种颜色，并通常要求相邻顶点（由边相连的顶点）颜色不同；满足该要求的称为 proper vertex coloring（适当/合法顶点着色）。该概念常用于排课、频率分配、资源冲突消解等建模问题。（在不同语境下也可能泛指“给顶点分配颜色”的过程。）

发音 Pronunciation (IPA)

/ˈvɝːtɛks ˈkʌlərɪŋ/ （亦常见 /ˈvɜːtɛks ˈkʌlərɪŋ/）

例句 Examples

Vertex coloring assigns a color to each vertex of a graph.
顶点着色为图中的每个顶点分配一种颜色。

Finding the minimum number of colors needed for a vertex coloring is NP-hard for general graphs.
对一般图而言，求顶点着色所需的最少颜色数是一个 NP-难问题。

词源 Etymology

vertex 源自拉丁语 vertex（意为“转折点、顶点”），在数学中指多边形或图中的“点/顶点”；coloring 来自动词 color（着色）加后缀 -ing，表示“着色的过程/方法”。合起来 vertex coloring 就是“对顶点进行着色”的图论术语，用于区分于 edge coloring（边着色） 等相关概念。

相关词 Related Words

• Graph
• Vertex
• Edge
• Graph Coloring
• Chromatic Number
• Proper Coloring
• Clique
• Bipartite
• Planar Graph
• Four-Color Theorem

文学与著作中的用例 Literary Works

• Douglas B. West, Introduction to Graph Theory（讨论图着色与顶点着色、色数等核心概念）
• Reinhard Diestel, Graph Theory（在图着色章节中系统使用“vertex coloring/graph coloring”等术语）
• Béla Bollobás, Modern Graph Theory（涉及着色问题的理论与应用）
• Thomas H. Cormen et al., Introduction to Algorithms（相关章节/习题中常以图着色建模并提及顶点着色与复杂性）