切入加权无向连通图 [英] Cut in a Weighted Undirected Connected Graph

问题描述

背景:我是图论的新手，特别是在图切"领域.请不要太技术和快速.谢谢.
假设我有一个加权无向连通图G =(V，E).我有一个保存一个整数值的变量A，我想从权重低于A值的图G中删除/剪切所有边.
问题1:如果在图论中已经存在(我见过最大切割，最小切割，s-t切割等)，它是怎么称呼的?
问题2:如何使用数学符号来正式表达/定义这种方法.
谢谢您的建议.

Background: I am a newbie to graph theory, specially in "graph cut". Please don't be too technical and fast. Thank you.
Suppose I have a weighted undirected connected graph G=(V,E). I have a variable A that holds an integer value and I want to remove/cut all edges from the graph G whose weight are below the value of A.
Question 1: If this already exist in graph theory (I saw max-cut, min-cut, s-t cut, etc) how is it called?
Question 2: How can I formally express/define this approach using mathematical symbols.
Thank you for your suggestions.

推荐答案

您有:

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

• a Graph G
• composed of a set of vertices V
• and a edges E which is a set of pairs of vertices (i.e. E = {{x,y} : x ∈ V, y ∈ V}).
• each edge has a weight (assumed to be a natural number) which you can specify using a function (i.e. ∀ e ∈ E : weight(e) ∈ ℕ).

然后给出图G'的图，该图的权重不小于a的边已去除(注意:单个元素/值通常用小写字母表示，而集合/列表/等通常用大写字母表示)通过:

Then the graph G' with removed edges with weight not less than a (note: singular elements/values are usually denoted using lower-case whereas sets/lists/etc are usually denoted using upper-case) is given by:

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

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

或者，为了更明确地说明要从E中删除元素，您可能会long之以鼻，并将其定义为:

or, to make it more explicit that you are removing elements from E, you could be long-winded and define it as:

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

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

这篇关于切入加权无向连通图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！