Wolfram 语言与系统参考资料中心

FindVertexColoring

为图 g 中的顶点找到最少个数的着色.

FindVertexColoring[g,{c₁,c₂,…}]

为图 g 中的顶点找到着色方案 {c₁,c₂,…,c_k}.

范例

打开所有单元关闭所有单元

基本范例 (2)

求彼得森图的顶点着色：

Wolfram Language code: FindVertexColoring[PetersenGraph[]]

为图中相邻的顶点分配不同的颜色：

Wolfram Language code: g = PetersenGraph[];

Wolfram Language code: FindVertexColoring[g, ColorData[106, "ColorList"]]

可视化图：

Wolfram Language code: Annotate[g, {VertexStyle -> Thread[VertexList[g] -> %]}]

范围 (7)

FindVertexColoring 适用于无向图：

Wolfram Language code: FindVertexColoring[[image]]

有向图：

Wolfram Language code: FindVertexColoring[[image]]

加权图：

Wolfram Language code: FindVertexColoring[[image]]

多图：

Wolfram Language code: FindVertexColoring[[image]]

用规则指定图：

Wolfram Language code: FindVertexColoring[{1 -> 2, 1 -> 3, 1 -> 4, 1 -> 5, 2 -> 3, 2 -> 5, 3 -> 4, 4 -> 5}]

为图中相邻的顶点分配不同的颜色：

Wolfram Language code: FindVertexColoring[[image], ColorData[3, "ColorList"]]

FindVertexColoring 适用于大图：

Wolfram Language code: g = GridGraph[{10, 10, 10}];

Wolfram Language code: AbsoluteTiming[FindVertexColoring[g];]

选项 (3)

Method (3)

根据输入自动选择方法；"ILP" 可用于较小的图：

Wolfram Language code: g = PetersenGraph[];

Wolfram Language code: FindVertexColoring[g, Method -> "ILP"]

"BacktrackingDS" 可用于不太大的图：

Wolfram Language code: g = PetersenGraph[];

Wolfram Language code: FindVertexColoring[g, Method -> "BacktrackingDS"]

"HybridEA" 可用于较大的图：

Wolfram Language code: g = GridGraph[{10, 10, 10}];

Wolfram Language code: Length[FindVertexColoring[g, Method -> "HybridEA"]]

应用 (5)

基本应用 (2)

可视化参数化图的顶点着色：

Wolfram Language code: coloring[g_] := Annotate[g, {...}]

Wolfram Language code: Multicolumn[Table[coloring[g], {g, {...}}], 3, Spacings -> 2]

求 CompleteGraph[n] 的一组颜色：

Wolfram Language code: FindSequenceFunction[FindVertexColoring[CompleteGraph[10]], n]

CycleGraph[n]：

Wolfram Language code: FindSequenceFunction[FindVertexColoring[CycleGraph[10]], n]

制定时间表 (1)

一所大学有许多不同的学科. 每个学生都注册了其中一些科目. 构建一个图，其中每个顶点都是一个学科，两个顶点之间的边意味着有一个共同的学生：

Wolfram Language code: g = [image];

给出一个考试时间表，不要将同一学生的两次考试安排在同一时间：

Wolfram Language code: FindVertexColoring[g]

安排所有考试所需的最少的时间段：

Wolfram Language code: Max[%]

移动无线电频率分配 (1)

将频率分配给基站时，分配给同一位置的所有基站的频率必须不同. 构建一个图，其中每个顶点都是一个基站，两个基站之间的边表示它们在彼此的覆盖范围内：

Wolfram Language code: g = [image];

求最少需要多少个频率：

Wolfram Language code: FindVertexColoring[g]

Wolfram Language code: Max[%]

地图着色 (1)

构建一个地图，其中每个顶点都是一个非洲国家，如果两个国家相邻，则在它们之间有一条边：

Wolfram Language code: g = [image];

用最少的颜色为地图着色，其中必须为任何相邻的国家分配不同的颜色：

Wolfram Language code: FindVertexColoring[g, ColorData[14, "ColorList"]];

Wolfram Language code: Annotate[g, {VertexSize -> 3, VertexStyle -> Thread[VertexList[g] -> %]}]

属性和关系 (6)

二分图是可用两种颜色着色的图：

Wolfram Language code: graphs = {[image], [image]};

Wolfram Language code: Max[FindVertexColoring[#]] == 2& /@ graphs

Wolfram Language code: BipartiteGraphQ /@ graphs

可用一种颜色着色的图为空图：

Wolfram Language code: graphs = {[image], [image], [image], [image]};

Wolfram Language code: Max[FindVertexColoring[#]] == 1& /@ graphs

Wolfram Language code: EmptyGraphQ /@ graphs

用 FindVertexColoring 计算 VertexChromaticNumber：

Wolfram Language code: g = PetersenGraph[];

Wolfram Language code: Max[FindVertexColoring[g]]

Wolfram Language code: VertexChromaticNumber[g]

图的边着色是其线图的顶点着色：

Wolfram Language code: g = PetersenGraph[];

Wolfram Language code: FindVertexColoring[LineGraph[g]]

Wolfram Language code: FindEdgeColoring[g]

对于有个顶点的图，其色数和独立数满足 ≤ ：

Wolfram Language code: g = PetersenGraph[];

Wolfram Language code: χ = Max@FindVertexColoring[g];

Wolfram Language code: α = Length[First[FindIndependentVertexSet[g]]];

Wolfram Language code: VertexCount[g] / α <= χ

平面图的面着色是其对偶图的顶点着色：

Wolfram Language code: g = WheelGraph[6, VertexLabels -> Automatic]

Wolfram Language code: FindVertexColoring[DualPlanarGraph[g]]

Wolfram Language code: FindPlanarColoring[g]

Top

	Method	Automatic	使用的方法
	PerformanceGoal	$PerformanceGoal	优化的目标

更多学习资源

技术支持

数据科学、金融与商业

工程

科学与技术

教育科技

教育举措

开始

提高你的技能

与我们合作

成人教育计划

青少年教育计划

欢迎阅读

FindVertexColoring

更多信息和选项

范例

基本范例 (2)

范围 (7)