Maximum cut (original) (raw)
Der maximale Schnitt eines Graphen ist eine Zerlegung seiner Knotenmenge in zwei Teilmengen, so dass das Gesamtgewicht der zwischen den beiden Teilen verlaufenden Kanten maximal wird. Im Gegensatz zum minimalen Schnitt ist das Problem NP-vollständig.
| Property | Value |
|---|---|
| dbo:abstract | Der maximale Schnitt eines Graphen ist eine Zerlegung seiner Knotenmenge in zwei Teilmengen, so dass das Gesamtgewicht der zwischen den beiden Teilen verlaufenden Kanten maximal wird. Im Gegensatz zum minimalen Schnitt ist das Problem NP-vollständig. (de) For a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible. Finding such a cut is known as the max-cut problem. The problem can be stated simply as follows. One wants a subset S of the vertex set such that the number of edges between S and the complementary subset is as large as possible. Equivalently, one wants a bipartite subgraph of the graph with as many edges as possible. There is a more general version of the problem called weighted max-cut, where each edge is associated with a real number, its weight, and the objective is to maximize the total weight of the edges between S and its complement rather than the number of the edges. The weighted max-cut problem allowing both positive and negative weights can be trivially transformed into a weighted minimum cut problem by flipping the sign in all weights. (en) En théorie des graphes et en algorithmique, une coupe maximum est une coupe contenant au moins autant d'arêtes que n'importe quelle autre coupe. Une extension de la définition consiste à considérer des poids associés aux arêtes. On considère alors la coupe ayant le poids total maximum. Les coupes maximums sont des objets utiles notamment en physique théorique et en électronique. Mais elles sont surtout connues pour le problème algorithmique qui consiste à trouver une coupe maximum, appelé couramment MAX-CUT, un problème relativement bien étudié, notamment dans le contexte de l'approximation. (fr) In un grafo, un taglio massimo è un taglio di dimensione almeno pari a quella di tutti gli altri tagli. Il problema della ricerca di un taglio massimo in un grafo è noto come problema max-cut. Il problema può essere enunciato semplicemente come segue. Si vuole ottenere un sottinsieme S dell'insieme dei vertici tale che il numero di archi tra S e l'insieme complementare abbia la più alta cardinalità possibile. Esiste una versione più avanzata del problema, che riguarda i grafi pesati. In questa versione, ad ogni arco è associato un numero reale, detto "peso", e l'obiettivo del problema è di massimizzare non il numero di archi ma il peso totale degli archi fra S ed il suo complemento. Il problema max-cut su grafi pesati è solitamente ristretto ai pesi non-negativi, dato che pesi negativi possono determinare un problema di diversa natura. (it) In de grafentheorie is een maximale snede een met maximale grootte of gewicht. Voor een niet-gerichte graaf met knopenverzameling en kantenverzameling , waarbij aan elke kant een gewicht is toegekend, is een maximale snede een partitie van in twee delen , zodanig dat de som van de gewichten van de kanten tussen en maximaal is. Het probleem van het vinden van een maximale snede heet in het Engels max-cut problem en is een klassiek probleem uit de grafentheorie. Het is niet enkel theoretisch van belang. Het komt voor bij het ontwerpen van de lay-out van grote geïntegreerde schakelingen en in statistische natuurkunde. (nl) Para um grafo, um corte máximo é um corte cujo tamanho é de pelo menos o tamanho de qualquer outro corte. O problema de encontrar um corte máximo em um grafo é conhecido como Problema do Corte-Máximo (Max-Cut). O problema pode ser descrito simplesmente como segue. Deseja-se um subconjunto S do conjunto de vértices tal que o número de arestas entre S e o subconjunto complementar é tão grande quanto possível. Há uma versão mais avançada do problema que se chama Corte-Máximo ponderado. Nesta versão cada aresta tem um número real, o seu peso, e o objetivo é maximizar não o número de arestas, mas o peso total das arestas entre S e seu complemento. O problema do Corte-Máximo ponderado é frequente, mas nem sempre, restrito a pesos não-negativos, porque pesos negativos podem alterar a natureza do problema. (pt) Максимальный разрез графа — это разрез, размер которого не меньше размера любого другого разреза. Задача определения максимального разреза для графа известна как задача о максимальном разрезе. Задачу можно сформулировать следующим образом. Следует найти подмножество вершин S, такое, что число рёбер между S и его дополнением было бы настолько велико, насколько это возможно. Существует расширенная версия, задача о взвешенном максимальном разрезе. В этой версии каждому ребру приписано вещественное число, его вес, и целью является максимизация не числа рёбер, а общего веса рёбер между S и его дополнением. Задача о взвешенном максимальном разрезе часто, но не всегда, ограничивается неотрицательными весами, поскольку отрицательные веса могут изменить природу задачи. (ru) 最大割問題（英語：Maximum Cut）是 NP完备 问题。給定一張圖，求一種分割方法，將所有頂點（Vertex）分割成两群，同时使得被切斷的邊（Edge）數量最大。 此問題還有另一個變形的版本：每條邊上有各自的權重，要使得被切斷的邊的權重之和最大。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Max-cut.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.nada.kth.se/~viggo/wwwcompendium/ http://www.nada.kth.se/~viggo/wwwcompendium/node85.html http://code.google.com/p/maxcutpy/ https://repository.upenn.edu/statistics_papers/395 |
| dbo:wikiPageID | 19636775 (xsd:integer) |
| dbo:wikiPageLength | 21616 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102804041 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Route_inspection_problem dbr:NP_(complexity) dbr:Method_of_conditional_probabilities dbr:Algorithmica dbr:Approximation_algorithm dbr:Can._J._Math. dbr:Decision_problem dbr:Derandomization dbr:Induced_subgraph dbc:Combinatorial_optimization dbc:Graph_theory_objects dbc:NP-complete_problems dbr:Complement_(set_theory) dbr:Maximum_2-satisfiability dbr:SIAM_J._Comput. dbr:Odd_cycle_transversal dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:NP-complete dbr:NP-hard dbr:SIAM_Journal_on_Computing dbr:Reducibility_among_combinatorial_problems dbr:Partition_problem dbr:Theoretical_computer_science dbr:Maximum_satisfiability_problem dbr:Karp's_21_NP-complete_problems dbr:Minimum_cut dbr:Minimum_k-cut dbr:J._Comput._Syst._Sci. dbr:Cut_(graph_theory) dbr:Dual_graph dbr:Ford–Fulkerson_algorithm dbr:Gerhard_J._Woeginger dbr:Graph_partition dbr:Ising_model dbr:Journal_of_the_ACM dbr:Order_and_disorder dbr:Spin_glass dbr:Hamiltonian_mechanics dbr:Fixed-parameter_tractable dbr:Bipartite_graph dbc:Computational_problems_in_graph_theory dbr:Winding_number dbr:Discrete_Math. dbr:Planar_graph dbr:Approximation_ratio dbr:Optimization_problem dbr:Randomized_algorithm dbr:Unique_games_conjecture dbr:Vertex_(graph_theory) dbr:Combin._Probab._Comput. dbr:Unfriendly_partition dbr:Statistical_physics dbr:Semidefinite_programming dbr:Very_Large_Scale_Integration dbr:Subset dbr:Randomized_rounding dbr:Theor._Comput._Sci. dbr:Signed_graphs dbr:Constant-factor_approximation_algorithm dbr:File:Max-cut.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cite_arXiv dbt:Main dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Sub |
| dct:subject | dbc:Combinatorial_optimization dbc:Graph_theory_objects dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory |
| gold:hypernym | dbr:Cut |
| rdf:type | yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 dbo:Food yago:State100024720 |
| rdfs:comment | Der maximale Schnitt eines Graphen ist eine Zerlegung seiner Knotenmenge in zwei Teilmengen, so dass das Gesamtgewicht der zwischen den beiden Teilen verlaufenden Kanten maximal wird. Im Gegensatz zum minimalen Schnitt ist das Problem NP-vollständig. (de) En théorie des graphes et en algorithmique, une coupe maximum est une coupe contenant au moins autant d'arêtes que n'importe quelle autre coupe. Une extension de la définition consiste à considérer des poids associés aux arêtes. On considère alors la coupe ayant le poids total maximum. Les coupes maximums sont des objets utiles notamment en physique théorique et en électronique. Mais elles sont surtout connues pour le problème algorithmique qui consiste à trouver une coupe maximum, appelé couramment MAX-CUT, un problème relativement bien étudié, notamment dans le contexte de l'approximation. (fr) 最大割問題（英語：Maximum Cut）是 NP完备 问题。給定一張圖，求一種分割方法，將所有頂點（Vertex）分割成两群，同时使得被切斷的邊（Edge）數量最大。 此問題還有另一個變形的版本：每條邊上有各自的權重，要使得被切斷的邊的權重之和最大。 (zh) For a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible. Finding such a cut is known as the max-cut problem. The problem can be stated simply as follows. One wants a subset S of the vertex set such that the number of edges between S and the complementary subset is as large as possible. Equivalently, one wants a bipartite subgraph of the graph with as many edges as possible. (en) In un grafo, un taglio massimo è un taglio di dimensione almeno pari a quella di tutti gli altri tagli. Il problema della ricerca di un taglio massimo in un grafo è noto come problema max-cut. Il problema può essere enunciato semplicemente come segue. Si vuole ottenere un sottinsieme S dell'insieme dei vertici tale che il numero di archi tra S e l'insieme complementare abbia la più alta cardinalità possibile. (it) In de grafentheorie is een maximale snede een met maximale grootte of gewicht. Voor een niet-gerichte graaf met knopenverzameling en kantenverzameling , waarbij aan elke kant een gewicht is toegekend, is een maximale snede een partitie van in twee delen , zodanig dat de som van de gewichten van de kanten tussen en maximaal is. (nl) Максимальный разрез графа — это разрез, размер которого не меньше размера любого другого разреза. Задача определения максимального разреза для графа известна как задача о максимальном разрезе. Задачу можно сформулировать следующим образом. Следует найти подмножество вершин S, такое, что число рёбер между S и его дополнением было бы настолько велико, насколько это возможно. (ru) Para um grafo, um corte máximo é um corte cujo tamanho é de pelo menos o tamanho de qualquer outro corte. O problema de encontrar um corte máximo em um grafo é conhecido como Problema do Corte-Máximo (Max-Cut). O problema pode ser descrito simplesmente como segue. Deseja-se um subconjunto S do conjunto de vértices tal que o número de arestas entre S e o subconjunto complementar é tão grande quanto possível. (pt) |
| rdfs:label | Maximaler Schnitt (de) Coupe maximum (fr) Taglio massimo (it) Maximum cut (en) Maximale snede (nl) Corte Máximo (pt) Максимальный разрез графа (ru) 最大割問題 (zh) |
| owl:sameAs | freebase:Maximum cut yago-res:Maximum cut wikidata:Maximum cut dbpedia-de:Maximum cut dbpedia-fa:Maximum cut dbpedia-fr:Maximum cut dbpedia-it:Maximum cut dbpedia-nl:Maximum cut dbpedia-pt:Maximum cut dbpedia-ru:Maximum cut dbpedia-sr:Maximum cut dbpedia-zh:Maximum cut https://global.dbpedia.org/id/55WF1 |
| prov:wasDerivedFrom | wikipedia-en:Maximum_cut?oldid=1102804041&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Max-cut.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Maximum_cut |
| is dbo:wikiPageRedirects of | dbr:Approximation_algorithms_for_the_max-cut_problem dbr:Max-cut_problem dbr:Max_cut dbr:Max_weight_cut dbr:Maxcut dbr:Maximal_cut dbr:MAX-CUT dbr:Bipartite_subgraph |
| is dbo:wikiPageWikiLink of | dbr:Pseudo-Boolean_function dbr:Elchanan_Mossel dbr:Method_of_conditional_probabilities dbr:Approximation_algorithm dbr:Arc_diagram dbr:Pathwidth dbr:Cubic_graph dbr:Pseudorandom_graph dbr:Segmentation-based_object_categorization dbr:Analysis_of_Boolean_functions dbr:Odd_cycle_transversal dbr:Quantum_optimization_algorithms dbr:Constraint_satisfaction_problem dbr:Approximation_algorithms_for_the_max-cut_problem dbr:PLS_(complexity) dbr:Karp's_21_NP-complete_problems dbr:Minimum_cut dbr:Minimum_k-cut dbr:Graph_partition dbr:Ising_model dbr:List_of_NP-complete_problems dbr:Quadratic_unconstrained_binary_optimization dbr:Szemerédi_regularity_lemma dbr:Hyper-heuristic dbr:Planar_SAT dbr:Cirq dbr:Max-cut_problem dbr:Max_cut dbr:Max_weight_cut dbr:Maxcut dbr:Maximal_cut dbr:Michel_Deza dbr:Michel_Goemans dbr:Unique_games_conjecture dbr:Exponential_time_hypothesis dbr:Unfriendly_partition dbr:Semidefinite_programming dbr:Set_splitting_problem dbr:Submodular_set_function dbr:MAX-CUT dbr:Bipartite_subgraph |
| is foaf:primaryTopic of | wikipedia-en:Maximum_cut |
