程序员经验分享-hwhale

一组顶点不相交的循环，使得每个顶点都属于一个循环

2024-04-20

这里我有一个有向图G。我需要判断是否存在 一组顶点不相交的循环，使得每个顶点都属于一个循环。

我不确定这是否可以在多项式时间内完成或者是否是 NP 完全的？有人能至少指出我正确的方向吗？


将每个顶点拆分为“内”顶点和“外”顶点。那么顶点不相交的循环覆盖对应于该图上的完美​​匹配。您可以像找到完美匹配一样快地找到问题的答案（即多项式时间）

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Vertex

npcomplete

disjointsets

一组顶点不相交的循环，使得每个顶点都属于一个循环 的相关文章

  • Hierarchical Russian Roulette for Vertex Connections论文研读

    第二篇论文研读文章了 xff0c 虽然依旧很菜 xff0c 但这一篇开始就相对轻松一点了 文档种有些问题 xff0c 其中所有 实时 应该替换为 高效 Hierarchical Russian Roulette for Vertex Con

  • SceneKit 每个顶点颜色

    我一直在使用 SceneKit 但我不知道如何创建每个顶点颜色几何体 更准确地说 我想这样做 http openglbook com chapter 2 vertices and shapes html 如果不清楚 请告诉我 Thanks

  • 压缩阻塞文件中的记录的好算法是什么？

    假设您有一个由一堆固定大小的块组成的大文件 每个块都包含一定数量的可变大小的记录 每条记录必须完全适合单个块 并且根据定义 此类记录永远不会大于整个块 随着时间的推移 随着记录从这个 数据库 中移入和移出 记录会被添加到这些块中或从这些块中

  • 简化为派系问题

    子图同构 我们有图 G 1 V 1 E 1 G 2 V 2 E 2 Question 图 G 1 与 G 2 的子图同构吗 即 是否存在 G 2 V V 2 的顶点子集和 G 2 E E 2 边的子集 使得 V V 1 和 E E 1 并且

  • 非自相交多边形创建算法的有效性

    作为扩展和部分答案我的话题我写了一个简单的算法 给定一组点 具有 xy 坐标 可以形成一个非自相交的多边形 主张 给定具有不同坐标的任意点集 始终可以构造规则或不规则 非自相交的多边形 算法 假设有一个包含所有顶点的集合V 1 按x坐标对V

  • 实施 Kruskal 算法时测试电路

    我正在尝试编写一个程序来找到最小生成树 但我在使用该算法时遇到的一个问题是测试电路 在java中执行此操作的最佳方法是什么 好的 这是我的代码 import java io import java util public class Jun

  • BGL：如何有效地存储edge_descriptors和vertex_descriptors？

    因此 在解决了 BGL 的循环依赖问题之后 我遇到了另一个障碍 我目前正在使用邻接列表来对我的图进行建模 应用节点和边的捆绑属性来存储图中的一些信息 所以我有这样的事情 class Node int x int y position cla

  • 布尔表达式的最小化是NP完全的吗？

    我知道布尔可满足性是 NP 完全的 但它是布尔表达式的最小化 简化 我的意思是采用符号形式的给定表达式并生成符号形式的等效但简化的表达式 NP 完全 我不确定是否会从可满足性降低到最小化 但我觉得可能是这样 有人有确切消息么 好吧 这样看

  • 将基本 3D 模型导入 OpenGL 应用程序

    好吧 我正在做简单的 OpenGL ES 编程 当我说简单时 我所做的最复杂的事情只不过是美化的斜角立方体和 L 形 想想俄罗斯方块 但在 3D 中 但是 将所有顶点数据放入应用程序中要么是 a 手动编码 啊 要么 b 第 3 方游戏引擎

  • 使用模拟退火进行图形着色

    我正在尝试使用模拟退火提出图形着色问题的算法 网上有通用算法 但是当我查看它时 我无法理解如何将这个算法应用于这个问题 图中的每个节点必须具有与其邻居不同的颜色 我该如何使用模拟退火算法来实现这一点 这个问题中的 温度 时间表 是什么 请帮

  • 每个物品重量相同的0-1背包是NP完全的吗？

    0 1 背包问题称为 NP 完全问题 但如果每个项目的权重相同 问题仍然是NP完全问题吗 不 因为你总是只拿最有价值的东西

  • 如何向 THREE.BufferGeometry 添加面？

    我以编程方式创建了一个简单的网格 var CreateSimpleMesh new function var xy maxX 7 maxY 10 river 0 5 0 4 1 3 2 2 3 2 4 1 5 1 6 0 grassGeom

  • 在Python中导入CAD对象并存储为数组

    我正在使用 Autodesk Fusion 360 对 3D 零件进行建模 参见下图 然后可以将其导出并保存为 step iges sat 或 smt 文件 我想要实现的目标是将这部分转换为Python中的3D numpy数组 数组的每个元

  • 将数字列表分为 2 个等和列表的算法

    有一个数字列表 该列表将被分为 2 个大小相等的列表 并且总和相差最小 金额必须打印出来 Example gt gt gt que 2 3 10 5 8 9 7 3 5 2 gt gt gt make teams que 27 27 对于某

  • 根据中心性对顶点着色

    我正在尝试更改 igraph 生成的图形中顶点的颜色 更具体地说 我有一个从邻接矩阵创建的 95 个节点图 我想根据它们的度数 介数 特征值中心性 接近度对它们进行着色 但我猜在我知道如何用它来做之后 我可以和其他人一起做 所以到目前为止我

  • 如何找到 OpenGL es 2.0 顶点着色器专业版中所有制服的列表

    我正在尝试学习如何对顶点着色器进行编程 在苹果的示例项目中 他们有一行来设置 glUniform1f uniforms UNIFORM TRANSLATE Glfloat transY 然后这个值被用在 value passt in f g

  • 从活动顶点数组生成平滑法线

    我正在尝试通过挂钩 OpenGl 调用来破解和修改旧版 opengl 固定管道游戏的多个渲染功能 而我当前的任务是实现着色器照明 我已经创建了一个适当的着色器程序 可以正确照亮大部分对象 但该游戏的地形是在没有提供正常数据的情况下绘制的 游

  • 一组顶点不相交的循环，使得每个顶点都属于一个循环

    这里我有一个有向图G 我需要判断是否存在 一组顶点不相交的循环 使得每个顶点都属于一个循环 我不确定这是否可以在多项式时间内完成或者是否是 NP 完全的 有人能至少指出我正确的方向吗 将每个顶点拆分为 内 顶点和 外 顶点 那么顶点不相交的

  • 使用并集查找（又名不相交集）检测图是否是二分图

    我正在 Spoj 上做一个问题 基本上可以简化为检测图是否是二分图 我正在尝试使用 dfs 为图表着色 但它太慢了 有人评论这个 没有 bfs 没有 dfs 没有二部图 简单的并查集就可以做到 确实速度很快 提示 1 偶数长度的环不会影响两

  • glVertexAttribDivisor 和 glVertexBindingDivisor 有什么区别？

    我一直在寻找将属性与任意顶点分组关联起来的方法 起初似乎是我实现这一目标的唯一方法 但后来我偶然发现了这个问题 https stackoverflow com questions 14169228 opengl single vertex

随机推荐

热门标签