加权无向连通图中的割
背景：我是图论的新手，特别是“图割”。请不要太技术和速度。谢谢。
假设我有一个加权无向连通图G=(V，E)。我有一个变量a，它包含一个整数值，我想从图G中删除/裁剪所有权重低于a值的边。
问题1：如果图论中已经存在这一点（我看到了max-cut、min-cut、s-t cut，等等），它怎么称呼？
问题2：我如何使用数学符号正式表达/定义这种方法。
谢谢你的建议。
共有1个答案
您有：
- 图
G - 由一组顶点构成
v - 和边
e，它是一组顶点对（即e={{x,y}:x∈V,y∈V})。 - 每个边都有一个权重（假定为自然数），您可以使用函数（即
pee∈e:weight(e)∈)指定该权重。
那么，具有不小于A权重的去掉边的图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)- 或
g'=(V,E'):E'=E\{E∈E:weight(E)
-
例如：在这张图中，见图中有3个相连的组件，没有。分别为3、2和1的节点的。
-
我想知道什么是实现无向加权图的有效方法。我想在上面执行Prims和Kruskal算法。我知道邻接列表，但这不会浪费内存；为。假设我有两个顶点A和B，由权重为“x”的边连接，所以我需要在邻接列表中添加两个条目： 我是不是漏掉了什么？
-
假设我们有一个加权无向图，其中，对于任意两个顶点，都有一条唯一的路径连接它们。有n个顶点和1个边，每条路的成本是c\u i。 现在，如果连接两个给定顶点的每条路径都有一定的成本，这取决于它所经过的道路，那么我们如何有效地计算所有城市对之间的总成本？ 例如，每条道路的成本可以是它经过的第一条道路和最后一条道路的总和，或者是它经过的每条道路的成本的某些幂的总和，或者是成本的最大值减去它经过的道路的最小
-
我有一个文本文件中的数据，我想创建一个无向加权图，因为我从文件中读取它。数据由tweet组成。对于tweet中的每个单词，我在图中创建一个节点。对于其他单词，我在它们之间创建一条边，并为它们的权重增加1。因此边缘的权重应该是所有tweet中出现的两个单词的数量。 我创建一个图表： 我使用两个节点的ID获取它们之间的边： 但是，即使图形是无向的，也无法找到从id2到id1的边。因此，我使用了以下方法
-
总结 因此，我有一个有向无环加权图，其中每条边都有一个输入和输出节点，每个节点都有一个ID，我使用一个字典将所有传入的边映射到一个节点的ID，并使用另一个字典对所有传出的边进行同样的操作，这样，当出现节点ID时，我可以在大约O(1)时间内告诉所有传入和传出的边。 要求 我需要能够添加新的随机边(即连接两个随机节点)，以保证无论图有多大，它都不会有任何循环。 我试过的 由于我完全控制如何构建我的图，
-
我知道Bellman Ford算法使用负权值，但我希望我可以修改我现有的最短路径方法。