graph-coloring

6热度

1回答

如何计算绘制树的方法？

如何计算使用m种颜色绘制树节点的方式，以便每个边的末端具有不同的颜色？欢迎任何多项式解决方案。

-1热度

1回答

图着色算法的实现

我开始知道图着色算法是NP-Complete问题。不过，我想知道是否可以使用启发式方法实现任何实现，特别是区别图着色？如果可能的话，是否有任何合适的资源来了解这一点？

0热度

1回答

图分布的色数

我正在开发一种算法，用于查找图的色数并使用该数提供有效的着色。为此，我使用二分查找找到可能的答案K，并使用遗传算法检查K是否可行。问题是色数分布不均匀。例如，对于具有1000个顶点的图，其色数最可能低于100.这种方式在我的二进制搜索中，我不需要在左边界和右边界之间的中间进行分割，而是找到半色的中间号码分配。你知道我可以从哪里获得关于这个发行版的信息吗？我发现一个源给我一些细节，但对于节点少于10

1热度

2回答

Python“如果超过最大步数，打破循环”

我正在研究一个（非常复杂和不雅）Python代码，通过蛮力3色图形，并且在我的主代码块I' m试图包含一个声明，说“如果通过循环的最大运行次数超过（某些任意数量），跳出第一个（while a in range(0,len(vertices))）循环”。 a = 0 steps = 0 while a in range(0,len(vertices)): for j in newdic

0热度

1回答

超图的顶点着色，不均匀性限制NP-hard？

是一个超图的顶点着色，没有统一性限制NP-hard？我看过显示k-联合超图的顶点着色的论文是NP-hard。然而，我找不到任何明确说明在一般情况下（而不仅仅是k均匀）超图的顶点着色是否是NP难的来源。

0热度

1回答

为图表着色，以便每个节点都是彩色的或与彩色节点相邻

假设您有一个连通无向图G.您希望G中的每个节点都是彩色的或与彩色节点相邻。设计一个算法来适当地为图G着色。您只能对楼层（n/2）节点着色，其中n是节点的总数。我尝试了一个解决方案，但是我发现它没有完全解决约束问题，我想要一个微调或被告知我在错误的轨道上。我的解决方案基本上是运行BFS，并在每个“三级”着色节点。但是我发现了一个失败的实例 - 只有三个节点的链表。如果我为头部或尾部着色，那么其中

0热度

1回答

python中地图着色的随机实例

我需要在python中生成随机地图着色问题实例来实现最小冲突求解器。我应该遵循这个策略：在单位正方形上分散n个点;随机选择一个点X，通过一条线段将X连接到最近的点Y，使得X尚未连接到Y，并且该线段不与其它线段交叉（例如，请参阅此处如何测试线段交叉点）。重复上一步直到不再有可能的连接。这些点表示地图上的区域，并且这些线路将邻居连接起来。我甚至不知道如何开始。

1热度

1回答

使图着色不太严格

我正在试验graph coloring算法。这是一种对图的节点进行着色的方式，使得没有2个相邻节点具有相同的颜色。假设我有以下数据我想“色”（分配到组），其中每个字都是一个节点：猫黑色猫灰色狗灰色狗黑我希望以下组：猫，狗黑色，灰色但如果我加入我的第四动物，这是grey（就像颜色）的名字？所以第四行变成：狗黑灰色着色算法不能颜色和名称进行区分，所以black和grey将在最终

-1热度

1回答

排列不同组的阵列，以便它的元素没有邻居相似的组

我有可以通过它的一个被分成3个不同的组的阵列的属性： $shuffleMeGood = array( 0 => array('id' => '1', 'group' => 'banana'), 1 => array('id' => '2', 'group' => 'banana'), 2 => array('id' => '3', 'group' => 'banana'

0热度

2回答

如何检查图形是否可着色？

我想查找图形是否可以2色或不更多。双方或非双方。这里是我在C++中的代码我正在使用威尔士鲍威尔算法，但代码中有些错误可能是我错过了一些角落案例或一些逻辑错误。输入n =没有。顶点，m =否。基于0的索引 #include <iostream> #include <algorithm> using namespace std; pair <int,int> s[1001]; int