| dbo: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) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Min_cut_example.svg?width=300 |
| dbo:wikiPageID |
3562453 (xsd:integer) |
| dbo:wikiPageLength |
5363 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1099217035 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbc:Network_flow_problem dbr:Cycle_(graph_theory) dbr:Undirected_graph dbr:Vertex_separator dbr:Segmentation-based_object_categorization dbc:Graph_theory_objects dbr:Max-flow_min-cut_theorem dbr:Maximum_cut dbr:Gomory–Hu_tree dbr:Graph_(discrete_mathematics) dbr:Cluster_analysis dbr:K-edge-connected_graph dbr:Karger's_algorithm dbr:Minimum_k-cut dbr:Cut_(graph_theory) dbr:Flow_network dbr:Partition_of_a_set dbr:Graph_partition dbr:Graph_theory dbr:Maxflow dbr:Image_segmentation dbr:Metric_space dbr:NP-hardness dbr:Spectral_clustering dbr:Stoer-Wagner_algorithm dbr:File:Min_cut_example.svg |
| dbp:wikiPageUsesTemplate |
dbt:Mvar dbt:Reflist dbt:Set_index_article dbt:Short_description |
| dcterms:subject |
dbc:Network_flow_problem dbc:Graph_theory_objects |
| gold:hypernym |
dbr:Cut |
| rdf:type |
yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity dbo:Food yago:Rule105846932 |
| 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) |
| rdfs:label |
مسألة القطع الأدنى (ar) Coupe minimum (fr) Minimum cut (en) Наименьший разрез (ru) 最小割 (zh) |
| owl:sameAs |
freebase:Minimum cut freebase:Minimum cut yago-res:Minimum cut wikidata:Minimum cut dbpedia-ar:Minimum cut dbpedia-fa:Minimum cut dbpedia-fr:Minimum cut dbpedia-ru:Minimum cut dbpedia-th:Minimum cut dbpedia-zh:Minimum cut https://global.dbpedia.org/id/4rjDB |
| prov:wasDerivedFrom |
wikipedia-en:Minimum_cut?oldid=1099217035&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Min_cut_example.svg |
| foaf:isPrimaryTopicOf |
wikipedia-en:Minimum_cut |
| is dbo:wikiPageRedirects of |
dbr:Min-cut dbr:Min_cut dbr:Mincut |
| is dbo:wikiPageWikiLink of |
dbr:List_of_algorithms dbr:David_Karger dbr:Approximate_max-flow_min-cut_theorem dbr:Kőnig's_theorem_(graph_theory) dbr:Segmentation-based_object_categorization dbr:Max-flow_min-cut_theorem dbr:Maximum_cut dbr:Network_flow_problem dbr:Quadratic_pseudo-Boolean_optimization dbr:Glossary_of_graph_theory dbr:Closure_problem dbr:Community_structure dbr:Planar_separator_theorem dbr:HCS_clustering_algorithm dbr:K-edge-connected_graph dbr:Karger's_algorithm dbr:Minimum_k-cut dbr:Dual_graph dbr:Graph_cut_optimization dbr:Graph_partition dbr:Matroid_girth dbr:LEMON_(C++_library) dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Separation_oracle dbr:Submodular_set_function dbr:Stoer–Wagner_algorithm dbr:Min-cut dbr:Min_cut dbr:Mincut |
| is rdfs:seeAlso of |
dbr:HCS_clustering_algorithm |
| is foaf:primaryTopic of |
wikipedia-en:Minimum_cut |
