切入加权无向连通图

背景：我是图论的新手，特别是在“图切”中。请不要太技术和快速。谢谢。
假设我有一个加权无向连通图G =（V，E）。我有一个变量A，它包含一个整数值，我想从图G的权重低于A的值中删除/切割所有边。
问题1：如果这已经存在于图论中（我看到max-cut ，min-cut，st cut等），它叫什么名字？
问题2：如何使用数学符号正式表达/定义此方法。
谢谢你的建议。切入加权无向连通图

来源

2015-07-28 george24

你说的 “删除/切” 是什么意思？ – MrGreen

@MrGreen我的意思是“删除”边缘。 – george24

您有：

一个图形G
一组顶点V
和边组成E这是一组顶点对（即E = {{x,y} : x ∈ V, y ∈ V}）。
每条边都有一个权重（假定为自然数），您可以使用函数（即∀ e ∈ E : weight(e) ∈ ℕ）指定权重。

然后图形G'与重量除去的边缘不小于a：由下式给出（注单数元素/值通常使用小写而集列表/等使用大写通常表示为/表示）：

G' = (V, { e ∈ E : weight(e) ≥ a })
或G' = (V,E') : E' = { e ∈ E : weight(e) ≥ a }

，或者使之更加明确，你是移除元素从E，你可以长篇大论，并把它定义为：

G' = (V, E \ { e ∈ E : weight(e) < a })
或G' = (V,E') : E' = E \ { e ∈ E : weight(e) < a }

来源

2015-07-29 10:36:11 MT0

@MTO非常感谢你的兄弟！问题领域的优秀细分和非常明确的解释。啊，只要我能给你一瓶啤酒！还有一个问题，这个过程的最大运行时间是多少，我怎么才能正式描述它。谢谢。 – george24

运行时间应该是'O（E）' - 您需要迭代每个边并测试它的权重，然后创建一个代表该图的新数据结构。每一步 - 创建一个新图形;测试重量;并添加边缘到新图形 - 应该是'O（1）'（如果有效地完成），并且您将为每个边缘重复步骤（总共为'O（E）'）。要正式说明它，你只需要写一些类似的东西，但要小心地将算法分解成其组成部分并从那里开始工作。 – MT0

是的，因为每个边都需要被访问，所以在这种情况下'O（E）'看起来合乎逻辑。谢谢：） – george24

据我所知，你想删除重量小于A的边缘。这与cuts in graphs无关。

我想你想要的数学表达式为：

G'(V', E') = G(V, Q) : Q = {x: x <= A and x belongs to E}

来源

2015-07-28 10:52:56 MrGreen

是的，我认为我不必看切割。感谢数学表达。 – george24

不客气 – MrGreen

切入加权无向连通图

回答

相关问题