About: Max-flow min-cut theorem

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Max-flow min-cut theorem Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Rule105846932, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FMinimum_cut&graph=http%3A%2F%2Fdbpedia.org&graph=http%3A%2F%2Fdbpedia.org

In graph theory, a minimum cut or min-cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets) that is minimal in some metric. Variations of the minimum cut problem consider weighted graphs, directed graphs, terminals, and partitioning the vertices into more than two sets. The weighted min-cut problem allowing both positive and negative weights can be trivially transformed into a weighted maximum cut problem by flipping the sign in all weights.

Attributes	Values
rdf:type	yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity Food yago:Rule105846932
rdfs:label	مسألة القطع الأدنى (ar) Coupe minimum (fr) Minimum cut (en) Наименьший разрез (ru) 最小割 (zh)
rdfs:comment	في نظرية البيانات ، مسألة القطع الأدنى أو القص الأدنى تتعلق في إيجاد أقل عدد من الحواف التي تربط بين مجموعتين جزئيتين منفصلتين من الرؤوس. في حالة البيانات المقيّمة غالبا ما يقاس القص الأدنى بالمجموع التراكمي لأثقال هذه الحواف. (ar) En théorie des graphes et en informatique théorique, une coupe minimum (« coupe min », en anglais : minimum cut ou Min Cut) d'un graphe est une coupe contenant un nombre minimal d'arêtes. C'est un objet classique, qui apparaît notamment dans le théorème flot-max/coupe-min et qui peut être utilisé dans différents contextes, notamment en vision artificielle. Le problème algorithmique qui consiste à trouver une telle coupe est considéré comme facile, puisqu'il peut être résolu en temps polynomial, contrairement au problème de la coupe maximum par exemple. (fr) In graph theory, a minimum cut or min-cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets) that is minimal in some metric. Variations of the minimum cut problem consider weighted graphs, directed graphs, terminals, and partitioning the vertices into more than two sets. The weighted min-cut problem allowing both positive and negative weights can be trivially transformed into a weighted maximum cut problem by flipping the sign in all weights. (en) 在图论中，去掉其中所有边能使一张网络流图不再连通（即分成两个子图）的边集称为图的（英語：cut），一张图上最小的割称为最小割（英語：minimum cut或min-cut）。与最小割相关的问题称最小割问题（英語：minimum cut problem或min-cut problem），其变体包括带边权、有向图、包含源点与汇点（简称有源汇），以及将原网络分为多于两个子图等问题。其中，带边权的最小割问题允许有负权边，可通过对所有边权取相反数简单地转化为最大流问题求解。 (zh) Наименьший разрез графа — это минимальный в некотором смысле разрез (разбиение вершин графа на два непересекающихся связанных множества). (ru)
foaf:depiction
dcterms:subject	Network flow problem Graph theory objects
Wikipage page ID	3562453 (xsd:integer)
Wikipage revision ID	1099217035 (xsd:integer)
Link from a Wikipage to another Wikipage	Network flow problem Cycle (graph theory) Undirected graph Vertex separator Segmentation-based object categorization Graph theory objects Max-flow min-cut theorem Maximum cut Gomory–Hu tree Graph (discrete mathematics) Cluster analysis K-edge-connected graph Karger's algorithm Minimum k-cut Cut (graph theory) Flow network Partition of a set Graph partition Graph theory Maxflow Image segmentation Metric space NP-hardness Spectral clustering Stoer-Wagner algorithm
sameAs	Max-flow min-cut theorem Max-flow min-cut theorem Max-flow min-cut theorem Max-flow min-cut theorem Max-flow min-cut theorem Max-flow min-cut theorem Max-flow min-cut theorem Max-flow min-cut theorem Max-flow min-cut theorem Max-flow min-cut theorem Max-flow min-cut theorem
dbp:wikiPageUsesTemplate	dbt:Mvar dbt:Reflist dbt:Set_index_article dbt:Short_description
thumbnail	wiki-commons:Special:FilePath/Min_cut_example.svg?width=300
has abstract	في نظرية البيانات ، مسألة القطع الأدنى أو القص الأدنى تتعلق في إيجاد أقل عدد من الحواف التي تربط بين مجموعتين جزئيتين منفصلتين من الرؤوس. في حالة البيانات المقيّمة غالبا ما يقاس القص الأدنى بالمجموع التراكمي لأثقال هذه الحواف. (ar) En théorie des graphes et en informatique théorique, une coupe minimum (« coupe min », en anglais : minimum cut ou Min Cut) d'un graphe est une coupe contenant un nombre minimal d'arêtes. C'est un objet classique, qui apparaît notamment dans le théorème flot-max/coupe-min et qui peut être utilisé dans différents contextes, notamment en vision artificielle. Le problème algorithmique qui consiste à trouver une telle coupe est considéré comme facile, puisqu'il peut être résolu en temps polynomial, contrairement au problème de la coupe maximum par exemple. (fr) In graph theory, a minimum cut or min-cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets) that is minimal in some metric. Variations of the minimum cut problem consider weighted graphs, directed graphs, terminals, and partitioning the vertices into more than two sets. The weighted min-cut problem allowing both positive and negative weights can be trivially transformed into a weighted maximum cut problem by flipping the sign in all weights. (en) 在图论中，去掉其中所有边能使一张网络流图不再连通（即分成两个子图）的边集称为图的（英語：cut），一张图上最小的割称为最小割（英語：minimum cut或min-cut）。与最小割相关的问题称最小割问题（英語：minimum cut problem或min-cut problem），其变体包括带边权、有向图、包含源点与汇点（简称有源汇），以及将原网络分为多于两个子图等问题。其中，带边权的最小割问题允许有负权边，可通过对所有边权取相反数简单地转化为最大流问题求解。 (zh) Наименьший разрез графа — это минимальный в некотором смысле разрез (разбиение вершин графа на два непересекающихся связанных множества). (ru)
gold:hypernym	Cut
prov:wasDerivedFrom	wikipedia-en:Minimum_cut?oldid=1099217035&ns=0
page length (characters) of wiki page	5363 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Minimum_cut
is rdfs:seeAlso of	HCS clustering algorithm
is Link from a Wikipage to another Wikipage of	List of algorithms David Karger Approximate max-flow min-cut theorem Kőnig's theorem (graph theory) Segmentation-based object categorization Max-flow min-cut theorem Maximum cut Network flow problem Quadratic pseudo-Boolean optimization Glossary of graph theory Closure problem Community structure Planar separator theorem HCS clustering algorithm K-edge-connected graph Karger's algorithm Minimum k-cut Dual graph Graph cut optimization Graph partition Matroid girth LEMON (C++ library)

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (61 GB total memory, 51 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software