程序员经验分享-hwhale

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

2024-04-20

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

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


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

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

Vertex

npcomplete

disjointsets

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

  • 查找大小为 n 的列表中的哪些数字与另一个数字相加的算法

    我有一个十进制数 我们称之为goal 和其他十进制数的数组 我们称该数组为elements 并且我需要找到来自的所有数字组合elements总和就是目标 我更喜欢 C Net 2 0 中的解决方案 但无论如何 最好的算法可能会获胜 您的方法

  • 路径压缩和按等级合并如何相辅相成？

    我一直在阅读有关联合查找问题的内容 两个主要改进是路径压缩和按等级并集 据我了解 按等级并集用于确定如何组合不相交的树 如果我们有两棵不相交的树 T1 和 T2 那么我们将具有较小等级的树的根附加到具有较高等级的树 如果我们不使用路径压缩

  • glVertexAttribPointer 内置顶点属性，如 gl_Vertex、gl_Normal

    我必须使用 glVertexAttribPointer 将顶点属性发送到期望它们作为内置的着色器 gl Vertex gl Color etc The glVertexAttribPointer函数需要指定每个内置属性的索引 或位置 我可以

  • SceneKit 每个顶点颜色

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

  • 通过将集合划分为两个子集来查找可以由集合形成的最大总和

    说明 Given a set of numbers S Find maximum sum such that Sum A1 Sum A2 Where A1 S and A2 S and A1 A2 And Sum X is the sum

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

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

  • 简化为派系问题

    子图同构 我们有图 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 并且

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

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

  • Vertex 中的 R iGraph 热图

    我对 R 很陌生 有一个问题被困住了 是否可以在顶点上打印热图iGraph 我知道我可以做一个彩色的正方形或圆形 但是小型热图可能吗 这是绘制我当前图表的代码 create graph graph lt graph data frame n

  • iPhone 上的 OpenGL ES 2.0：GL_POINT_SMOOTH 使用 ES 2.0 绘制正方形，但适用于 ES 1.0

    我正在尝试使用顶点缓冲区对象来绘制圆 并在 iPhone 上的 OpenGL ES 2 0 中启用 GL POINT SMOOTH 来绘制点 我使用以下 ES 1 0 渲染代码在 iPhone 4 上成功绘制圆圈 glVertexPoint

  • 在工作面试中要求解决 NP 完全问题是否正确？ [关闭]

    Closed 这个问题是无关 help closed questions 目前不接受答案 今天有一个question https stackoverflow com questions 1720737 from an interview r

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

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

  • 每个物品重量相同的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

  • 在 C++ 中实现等价关系（使用 boost::disjoint_sets）

    假设您有许多元素 并且需要跟踪它们之间的等价关系 如果元素A等价于元素B 则它等价于B所等价的所有其他元素 我正在寻找一种有效的数据结构来编码这些信息 应该可以通过与现有元素的等价来动态添加新元素 并且根据该信息应该可以有效地计算新元素等价

  • 在线性时间内打印出不相交集数据结构中的节点

    我正在尝试在 Cormen 等人的 算法简介 中进行此练习 该练习与分离集数据结构有关 假设我们要添加操作PRINT SET x 给定 一个节点x并打印所有成员x已设置 按任何顺序 展示如何 我们可以只向不相交集中的每个节点添加一个属性 森

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

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

  • 有向图的并查/不交集数据结构

    我正在寻找一个高效的联查 aka 不相交集 https en wikipedia org wiki Disjoint set data structure 我的数据结构有向图 https en wikipedia org wiki Dire

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

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

  • 我是否需要采取明确的操作来促进与持久数据结构的共享？

    我来自命令式背景 正在尝试实现一个简单的不相交集 并集查找 数据结构 以获得在 Haskell 中创建和修改 持久 数据结构的一些练习 目标是有一个简单的实现 但我也关心效率 我的问题与此相关 首先 我创建了一个按等级并集的不相交集森林实现

随机推荐

热门标签