Namespaces
Variants
Actions

Difference between revisions of "König theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (moved König theorem to Konig theorem: ascii title)
m (moved Konig theorem to König theorem over redirect: accented title)
(No difference)

Revision as of 07:54, 26 March 2012

If the entries of a rectangular matrix are zeros and ones, then the minimum number of lines containing all ones is equal to the maximum number of ones that can be chosen so that no two of them lie on the same line. (Here the term "line" denotes either a row or a column in the matrix.) The theorem was formulated and proved by D. König [1]. It is one of the basic theorems in combinatorics and is the matrix analogue of Hall's criterion for the existence of a system of distinct representatives of a family of subsets of a finite set (see Selection theorems). There is also a widespread statement of König's theorem in terms of graphs: In a bipartite graph (cf. Graph, bipartite) the number of edges in a maximal matching is equal to the number of elements of a minimal vertex covering.

König's theorem is often used in various combinatorial questions relating to selection and extremal problems. A generalization to the case of infinite matrices is known [3].

References

[1] D. König, "Graphs and matrices" Mat. Lapok , 38 (1931) pp. 116–119 (In Hungarian)
[2] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[3] M. Lewin, "Essential coverings of a matrix" Proc. Cambridge Philos. Soc. , 67 (1970) pp. 263–267


Comments

A vertex covering or disconnecting set of a graph is a collection of vertices such that every edge is incident with a vertex from (i.e. the edges incident with a vertex from cover ). A minimal vertex covering is a cut set.

The term rank of a matrix of zeros and ones is defined as the largest number of ones such that no two lie in the same row or column. Thus, König's theorem, also known as the König–Egerváry theorem, can also be formulated as: The term rank of a -matrix is equal to the minimum number of rows and columns which together cover all the 1's of .

References

[a1] R.J. Wilson, "Introduction to graph theory" , Longman (1972) pp. §27
[a2] Hj. Walther, "Ten applications of graph theory" , Reidel (1984) pp. Sect. 6.1
How to Cite This Entry:
König theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=K%C3%B6nig_theorem&oldid=22661
This article was adapted from an original article by V.E. Tarakanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article