Menger's theorem (original) (raw)
In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices.Proved by Karl Menger in 1927, it characterizes the connectivity of a graph.It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs.
| Property | Value |
|---|---|
| dbo:abstract | Der Satz von Menger ist eines der klassischen Ergebnisse der Graphentheorie. Er wurde von 1927 von Karl Menger bewiesen und stellt einen Zusammenhang zwischen der Anzahl disjunkter Wege und der Größe von Trennern in einem Graphen her. Insbesondere die globale Variante des Satzes trifft auch Aussagen über den K-Zusammenhang und den Kantenzusammenhang eines Graphen. Der Satz ist eine Verallgemeinerung des Satzes von König (1916), wonach in bipartiten Graphen die Paarungszahl der Knotenüberdeckungszahl entspricht. Er lässt sich wie der Satz von König auch auf unendliche Graphen übertragen (Ron Aharoni, 2009). (de) In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices.Proved by Karl Menger in 1927, it characterizes the connectivity of a graph.It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs. (en) メンガーの定理（メンガーのていり、英: Menger's theorem）とは、グラフ理論および関連する数学の分野における定理であり、有限無向グラフに属する連結グラフに関する定理である。カール・メンガーが1927年、辺連結度と点連結度について見出した。辺連結度版のメンガーの定理は、後に最大フロー最小カット定理として一般化された。 辺連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小辺カット（辺切断，除去することで x と y が連結されなくなる最小の辺の数）の大きさは、x から y の辺独立経路 (辺素パス) の最大数と等しい。 点連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小点カット（点切断。除去することで x と y が連結されなくなる最小の頂点の数）の大きさは、x から y の頂点独立経路 (点素パス) の最大数と等しい。 メンガーの定理は、無限グラフでも成り立つことが証明されている（ポール・エルデシュが最初に推測していた）。 (ja) En théorie des graphes, le théorème de Menger est à l'origine du théorème flot-max/coupe-min qui le généralise. Il fut prouvé par Karl Menger en 1927. (fr) 그래프 이론의 수학적 분야인 멩거의 정리에서는 유한 그래프에서 최소 의 크기가 정점 쌍 사이에서 발견될 수 있는 최대 분리 경로 수와 동일하다고 한다. 1927년에 카를 멩거(Karl Menger)가 증명한 것으로 그래프의 연결성은 연결 그래프를 특징짓는다. 이것은 에 의해 일반화되며, 이는 가중 그래프로 선형 프로그램에 대한 의 특별한 경우이다. 이러한 멩거의 정리를 무한한 그래프로 확대하여 추측한다면 이것은 에르되시-멩거 추측이라고 한다. (ko) Em teoria dos grafos e áreas relacionadas da matemática, o teorema de Menger é um resultado básico sobre conectividade em grafos finitos não direcionados. Foi provada a K-aresta-conectividade e K-vértice-conectividade por Karl Menger em 1927. A versão para aresta-conectividade do teorema de Menger foi generalizada mais tarde pelo Teorema do Fluxo Máximo–Corte Mínimo. A versão do teorema de Menger para aresta-conectividade funciona da seguinte forma: G é um grafo finito não direcionado e x e y são dois vértices distintos. Então o teorema afirma que o tamanho mínimo de arestas que precisam ser removidas para desconectar x e y é igual ao número máximo de caminhos aresta-independentes emparelhados de x para y.Estendendo para subgrafos: um subgrafo maximal desconectado por não menos que k-arestas de corte é idêntico aos subgrafo maximal com um número mínimo de k caminhos aresta-independente entre qualquer par de nós x, y no subgrafo. A versão do teorema de Menger para vértice-conectividade funciona da seguinte forma: G é um grafo finito não direcionado e x e y são dois vértices não adjacentes. Então o teorema afirma que o número mínimo de vértices que precisam ser removidos para desconectar x e y é igual ao número máximo de caminhos vértice-independentes emparelhados de x para y.Estendendo para subgrafos: um subgrafo maximal desconectado por não menos que k-vértices de corte é identico aos subgrafo maximal com um número mínimo de k caminhos vértice-independente entre qualquer par de nós x, y no subgrafo. (pt) Теорема Менгера — основной результат о связности в конечном неориентированном графе, тесно связанный с теоремой Форда — Фалкерсона.Сформулирована и доказана в 1927 году Карлом Менгером (мл.). (ru) Теорема Менгера — основний результат про зв'язність у скінченному неорієнтованому графі, тісно пов'язаний із теоремою Форда — Фалкерсона. Сформулював та довів 1927 року . (uk) 在图论中，门格尔定理（英：Menger's Theorem）指在有限图中，最小的大小等于任意在所有顶点对之间可以找到的不相交路径的最大数量。这一定理的证明由卡尔·门格尔于1927年发表。这被认为是图论中最重要且经典的定理之一。该定理刻畫了连通性的性质，增加了邊的權重可推廣成最大流量小割定理，而最大流量小割定理是線性規劃的强对偶性定理的直接推論。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Proof_of_Menger's_Theorem.svg?width=300 |
| dbo:wikiPageExternalLink | http://brain.math.fau.edu/locke/Menger.htm http://gepard.bioinformatik.uni-saarland.de/teaching/ws-2008-09/bioinformatik-3/lectures/V12-NetworkFlow.pdf http://www.math.unm.edu/~loring/links/graph_s05/Menger.pdf http://gepard.bioinformatik.uni-saarland.de/teaching/ws-2008-09/bioinformatik-3/lectures/V13-MaxFlowMinCut.pdf |
| dbo:wikiPageID | 1155738 (xsd:integer) |
| dbo:wikiPageLength | 11543 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1120532242 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:End_(graph_theory) dbr:Nonadjacent dbc:Graph_connectivity dbr:Paul_Erdős dbr:Characterization_(mathematics) dbr:Vertex_separator dbr:Kőnig's_theorem_(graph_theory) dbr:Ron_Aharoni dbr:Connectivity_(graph_theory) dbr:Max-flow_min-cut_theorem dbr:Path_(graph_theory) dbr:Gammoid dbr:K-edge-connected_graph dbr:K-vertex-connected_graph dbr:Linear_programming dbr:Edge_cut dbr:Directed_graph dbr:Graph_theory dbc:Theorems_in_graph_theory dbr:Karl_Menger dbr:Bipartite_graph dbc:Network_theory dbr:Vertex_(graph_theory) dbr:Mathematical dbr:Linear_program dbr:Finite_graph dbr:Vertex_cut dbr:Cut_set dbr:Eli_Berger dbr:File:Proof_of_Menger's_Theorem.svg |
| dbp:bot | InternetArchiveBot (en) |
| dbp:date | March 2020 (en) |
| dbp:fixAttempted | yes (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_journal dbt:Dead_link dbt:Harv dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Graph_connectivity dbc:Theorems_in_graph_theory dbc:Network_theory |
| gold:hypernym | dbr:Characterization |
| rdf:type | yago:WikicatMathematicalTheorems yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices.Proved by Karl Menger in 1927, it characterizes the connectivity of a graph.It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs. (en) メンガーの定理（メンガーのていり、英: Menger's theorem）とは、グラフ理論および関連する数学の分野における定理であり、有限無向グラフに属する連結グラフに関する定理である。カール・メンガーが1927年、辺連結度と点連結度について見出した。辺連結度版のメンガーの定理は、後に最大フロー最小カット定理として一般化された。 辺連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小辺カット（辺切断，除去することで x と y が連結されなくなる最小の辺の数）の大きさは、x から y の辺独立経路 (辺素パス) の最大数と等しい。 点連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小点カット（点切断。除去することで x と y が連結されなくなる最小の頂点の数）の大きさは、x から y の頂点独立経路 (点素パス) の最大数と等しい。 メンガーの定理は、無限グラフでも成り立つことが証明されている（ポール・エルデシュが最初に推測していた）。 (ja) En théorie des graphes, le théorème de Menger est à l'origine du théorème flot-max/coupe-min qui le généralise. Il fut prouvé par Karl Menger en 1927. (fr) 그래프 이론의 수학적 분야인 멩거의 정리에서는 유한 그래프에서 최소 의 크기가 정점 쌍 사이에서 발견될 수 있는 최대 분리 경로 수와 동일하다고 한다. 1927년에 카를 멩거(Karl Menger)가 증명한 것으로 그래프의 연결성은 연결 그래프를 특징짓는다. 이것은 에 의해 일반화되며, 이는 가중 그래프로 선형 프로그램에 대한 의 특별한 경우이다. 이러한 멩거의 정리를 무한한 그래프로 확대하여 추측한다면 이것은 에르되시-멩거 추측이라고 한다. (ko) Теорема Менгера — основной результат о связности в конечном неориентированном графе, тесно связанный с теоремой Форда — Фалкерсона.Сформулирована и доказана в 1927 году Карлом Менгером (мл.). (ru) Теорема Менгера — основний результат про зв'язність у скінченному неорієнтованому графі, тісно пов'язаний із теоремою Форда — Фалкерсона. Сформулював та довів 1927 року . (uk) 在图论中，门格尔定理（英：Menger's Theorem）指在有限图中，最小的大小等于任意在所有顶点对之间可以找到的不相交路径的最大数量。这一定理的证明由卡尔·门格尔于1927年发表。这被认为是图论中最重要且经典的定理之一。该定理刻畫了连通性的性质，增加了邊的權重可推廣成最大流量小割定理，而最大流量小割定理是線性規劃的强对偶性定理的直接推論。 (zh) Der Satz von Menger ist eines der klassischen Ergebnisse der Graphentheorie. Er wurde von 1927 von Karl Menger bewiesen und stellt einen Zusammenhang zwischen der Anzahl disjunkter Wege und der Größe von Trennern in einem Graphen her. Insbesondere die globale Variante des Satzes trifft auch Aussagen über den K-Zusammenhang und den Kantenzusammenhang eines Graphen. Der Satz ist eine Verallgemeinerung des Satzes von König (1916), wonach in bipartiten Graphen die Paarungszahl der Knotenüberdeckungszahl entspricht. (de) Em teoria dos grafos e áreas relacionadas da matemática, o teorema de Menger é um resultado básico sobre conectividade em grafos finitos não direcionados. Foi provada a K-aresta-conectividade e K-vértice-conectividade por Karl Menger em 1927. A versão para aresta-conectividade do teorema de Menger foi generalizada mais tarde pelo Teorema do Fluxo Máximo–Corte Mínimo. A versão do teorema de Menger para aresta-conectividade funciona da seguinte forma: A versão do teorema de Menger para vértice-conectividade funciona da seguinte forma: (pt) |
| rdfs:label | Satz von Menger (de) Théorème de Menger (fr) Menger's theorem (en) 멩거의 정리 (ko) メンガーの定理 (ja) Teorema de Menger (pt) Теорема Менгера (ru) Теорема Менгера (uk) 门格尔定理 (zh) |
| owl:sameAs | freebase:Menger's theorem yago-res:Menger's theorem wikidata:Menger's theorem dbpedia-de:Menger's theorem dbpedia-fi:Menger's theorem dbpedia-fr:Menger's theorem dbpedia-hu:Menger's theorem dbpedia-ja:Menger's theorem dbpedia-ko:Menger's theorem dbpedia-pt:Menger's theorem dbpedia-ru:Menger's theorem dbpedia-uk:Menger's theorem dbpedia-zh:Menger's theorem https://global.dbpedia.org/id/54qNr |
| prov:wasDerivedFrom | wikipedia-en:Menger's_theorem?oldid=1120532242&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Proof_of_Menger's_Theorem.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Menger's_theorem |
| is dbo:knownFor of | dbr:Karl_Menger |
| is dbo:wikiPageDisambiguates of | dbr:Menger |
| is dbo:wikiPageRedirects of | dbr:Menger's_Theorem dbr:Erdős-Menger_conjecture dbr:Erdős–Menger_conjecture dbr:Menger's_n-arc_theorem dbr:Menger_theorem dbr:Mengers_theorem |
| is dbo:wikiPageWikiLink of | dbr:Menger dbr:Independence_Theory_in_Combinatorics dbr:List_of_network_theory_topics dbr:Connectivity_(graph_theory) dbr:Max-flow_min-cut_theorem dbr:Menger's_Theorem dbr:Nash-Williams_theorem dbr:Hall's_marriage_theorem dbr:Planar_separator_theorem dbr:Gammoid dbr:January_1902 dbr:K-edge-connected_graph dbr:K-vertex-connected_graph dbr:List_of_Austrian_scientists dbr:Erdős-Menger_conjecture dbr:Barrier_resilience dbr:Cayley–Menger_determinant dbr:Erdős–Menger_conjecture dbr:Structural_cohesion dbr:Karl_Menger dbr:Menger's_n-arc_theorem dbr:Menger_theorem dbr:Mengers_theorem dbr:Strong_orientation dbr:List_of_theorems dbr:Plünnecke–Ruzsa_inequality dbr:Rudolf_Halin dbr:Sperner_family |
| is dbp:knownFor of | dbr:Karl_Menger |
| is foaf:primaryTopic of | wikipedia-en:Menger's_theorem |
