请输入您要查询的字词:

 

单词 Cut
释义

cut


On a digraphMathworldPlanetmath, define a sink to be a vertex with out-degree zero and a source to be a vertex with in-degree zero. Let G be a digraph with non-negative weights and with exactly one sink and exactly one source. A cut C on G is a subset of the edges such that every path from the source to the sink passes through an edge in C. In other words, if we remove every edge in C from the graph, there is no longer a path from the source to the sink.

Define the weight of C as

WC=eCW(e)

where W(e) is the weight of the edge e.

Observe that we may achieve a trivial cut by removing all the edges of G. Typically, we are more interested in minimal cuts, where the weight of the cut is minimized for a particular graph.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 14:17:21