| dbo:abstract
|
- Der Satz von König ist ein mathematischer Satz aus der Graphentheorie, der für bipartite Graphen einen Zusammenhang zwischen einer größten Paarung und einer minimalen Knotenüberdeckung aufzeigt. Er lautet: In einem bipartiten Graphen ist die Größe einer größten Paarung gleich der Größe einer kleinsten Knotenüberdeckung. Der Satz ist nach dem ungarischen Mathematiker Dénes Kőnig benannt, der ihn 1931 bewiesen hat.Unabhängig von König hat der Mathematiker Jenő Egerváry, ebenfalls im Jahr 1931, eine allgemeinere Formulierung des Theorems für gewichtete Graphen bewiesen.Deshalb wird der Satz gelegentlich auch als Satz von König und Egerváry bezeichnet. Er lässt sich auch auf unendliche Graphen übertragen, wie schon Paul Erdős vermutete und wie Ron Aharoni bewies. (de)
- En el área matemática de teoría de grafos, el teorema de König, probado por Dénes Kőnig (1931), describe una equivalencia entre el máximo emparejamiento y el problema de cubrimiento de vértices mínimo en grafos bipartitos. Fue descubierto independientemente, también en 1931, por Jenő Egerváry en el caso más general de grafos con peso. (es)
- In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs. (en)
- Le théorème de Kőnig est un résultat de théorie des graphes qui dit que, dans un graphe biparti, la taille du transversal minimum (i. e. de la couverture par sommets minimum) est égale à la taille du couplage maximum. La version pondérée du théorème est appelée théorème de Kőnig- (en). (fr)
- ( 이 문서는 그래프의 꼭짓점 덮개와 최대 부합에 관한 것입니다. 무한 그래프에 대한 정리에 대해서는 쾨니그 보조정리 문서를, 기수에 대한 정리에 대해서는 쾨니그의 정리 (집합론) 문서를 참고하십시오.) 그래프 이론 및 조합론에서 쾨니그의 정리(Kőnig의定理, 영어: Kőnig’s theorem)는 이분 그래프에 대한 최소 꼭짓점 덮개 문제와 최대 부합 문제가 서로 동치라는 정리다. (ko)
- В теории графов теорема Кёнига (теорема Кёнига-Эгервари, венгерская теорема), доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах.Независимо была открыта, в том же 1931, в несколько более общем виде для случая взвешенных графов. (ru)
- У теорії графів теорема Кеніга, доведена Денешем Кенігом в 1931, стверджує рівноцінність задач знаходження максимального парування і мінімального вершинного покриття в дводольних графах. В тому ж 1931 році в дещо більш загальному вигляді для випадку зважених графів це ж було незалежно відкрито угорським математиком Йене Егерварі. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 24134 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:authorlink
| |
| dbp:first
| |
| dbp:last
| |
| dbp:wikiPageUsesTemplate
| |
| dbp:year
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En el área matemática de teoría de grafos, el teorema de König, probado por Dénes Kőnig (1931), describe una equivalencia entre el máximo emparejamiento y el problema de cubrimiento de vértices mínimo en grafos bipartitos. Fue descubierto independientemente, también en 1931, por Jenő Egerváry en el caso más general de grafos con peso. (es)
- In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs. (en)
- Le théorème de Kőnig est un résultat de théorie des graphes qui dit que, dans un graphe biparti, la taille du transversal minimum (i. e. de la couverture par sommets minimum) est égale à la taille du couplage maximum. La version pondérée du théorème est appelée théorème de Kőnig- (en). (fr)
- ( 이 문서는 그래프의 꼭짓점 덮개와 최대 부합에 관한 것입니다. 무한 그래프에 대한 정리에 대해서는 쾨니그 보조정리 문서를, 기수에 대한 정리에 대해서는 쾨니그의 정리 (집합론) 문서를 참고하십시오.) 그래프 이론 및 조합론에서 쾨니그의 정리(Kőnig의定理, 영어: Kőnig’s theorem)는 이분 그래프에 대한 최소 꼭짓점 덮개 문제와 최대 부합 문제가 서로 동치라는 정리다. (ko)
- В теории графов теорема Кёнига (теорема Кёнига-Эгервари, венгерская теорема), доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах.Независимо была открыта, в том же 1931, в несколько более общем виде для случая взвешенных графов. (ru)
- У теорії графів теорема Кеніга, доведена Денешем Кенігом в 1931, стверджує рівноцінність задач знаходження максимального парування і мінімального вершинного покриття в дводольних графах. В тому ж 1931 році в дещо більш загальному вигляді для випадку зважених графів це ж було незалежно відкрито угорським математиком Йене Егерварі. (uk)
- Der Satz von König ist ein mathematischer Satz aus der Graphentheorie, der für bipartite Graphen einen Zusammenhang zwischen einer größten Paarung und einer minimalen Knotenüberdeckung aufzeigt. Er lautet: In einem bipartiten Graphen ist die Größe einer größten Paarung gleich der Größe einer kleinsten Knotenüberdeckung. Er lässt sich auch auf unendliche Graphen übertragen, wie schon Paul Erdős vermutete und wie Ron Aharoni bewies. (de)
|
| rdfs:label
|
- Satz von König (Graphentheorie) (de)
- Teorema de König (teoría de grafos) (es)
- Théorème de Kőnig (théorie des graphes) (fr)
- Kőnig's theorem (graph theory) (en)
- 쾨니그의 정리 (ko)
- Теорема Кёнига (комбинаторика) (ru)
- Теорема Кеніга (комбінаторика) (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
