About: Kőnig's theorem (graph theory)

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

About: Kőnig's theorem (graph theory) Goto Sponge NotDistinct Permalink

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

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FK%C5%91nig%27s_theorem_%28graph_theory%29&graph=http%3A%2F%2Fdbpedia.org&graph=http%3A%2F%2Fdbpedia.org

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.

Attributes	Values
rdf:type	yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 yago:VisualCommunication106873252 yago:WikicatPerfectGraphs
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)
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)
foaf:depiction
dcterms:subject	Perfect graphs Articles containing proofs Matching (graph theory) Theorems in graph theory Bipartite graphs
Wikipage page ID	5465118 (xsd:integer)
Wikipage revision ID	1121876491 (xsd:integer)
Link from a Wikipage to another Wikipage	Perfect graphs Approximation algorithm Perfect matching Regular graph Umlaut (diacritic) Vertex cover Vertex cover problem Degree (graph theory) Incidence matrix Independent set (graph theory) Induced subgraph Articles containing proofs Matching (graph theory) Matching (graph theory) Matching in hypergraphs Mathematics Max-flow min-cut theorem Maximum flow problem Chromatic number NP-complete Line graph Clique (graph theory) Hall's marriage theorem Hopcroft–Karp algorithm Perfect graph Matching polytope Acta Mathematica Hungarica Weighted graph Distributed algorithm Dual linear program Max-flow min-cut theorem Dénes Kőnig Flow network Dilworth's theorem Discrete Mathematics (journal) Fractional matching Graph theory Theorems in graph theory Gyula Kőnig Jenő Egerváry Bipartite graph Bipartite graphs Double acute accent Polynomial time Maximum matching Chromatic index Linear program Minimum vertex cover
Link from a Wikipage to an external page	https://archive.org/details/graphtheorywitha0000bond https://books.google.com/books%3Fid=tarLTNwM3gEC&pg=PA48
sameAs	Kőnig's theorem (graph theory) Kőnig's theorem (graph theory) Kőnig's theorem (graph theory) Kőnig's theorem (graph theory) Kőnig's theorem (graph theory) Kőnig's theorem (graph theory) Kőnig's theorem (graph theory) Kőnig's theorem (graph theory) Kőnig's theorem (graph theory) Kőnig's theorem (graph theory) Kőnig's theorem (graph theory) Kőnig's theorem (graph theory) Kőnig's theorem (graph theory)
dbp:wikiPageUsesTemplate	dbt:About dbt:Citation

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, 43 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software