问离散数学-顶点着色
EN

Stack Overflow用户

提问于 2017-01-12 23:03:14

回答 1查看 48关注 0票数 1

我有一个大约一周前布置的家庭作业。问题是，我不明白我的老师教了什么，但他给我们布置了家庭作业……

A= {a，b，s}，B= {b，h，t}，C= {a，t，s}，D= {h，t，s}，E= {a，b}，F= {b，t，s}

如何创建最小顶点着色，A，B，C，D，E和F是顶点？

我知道如何给顶点上色，但我不知道如何从给定的集合创建图形。有什么帮助吗？我试着在网上找过，但没有遇到这样的问题。

发布于 2017-01-12 23:42:00

如果要以这样的方式解释图，即顶点A、B、C、D、E、F当且仅当它们相交时才是连通的，则最优着色具有5种颜色。

生成的图几乎是6个顶点上的完整图- {E,F}和{E,D}是唯一缺失的边。也就是说，它通过{A,B,C,D,F}诱导的子图包含了5个顶点上的完整图。因此，任何顶点着色都不能使用少于5种颜色。总而言之，着色

F : 1
A : 2
B : 3
C : 4
D : 5
E : 1

是图的5-着色，这是最优的。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/41616403

复制

相似问题

问离散数学-顶点着色EN