请输入您要查询的字词:

 

单词 HallsMarriageTheorem
释义

Hall’s marriage theorem


Let S={S1,S2,Sn} be a finite collectionMathworldPlanetmath of finite setsMathworldPlanetmath. There exists a system of distinct representatives of S if and only if the following condition holds for any TS:

|T||T|

As a corollary, if this condition fails to hold anywhere, then no SDR exists.

This is known as Hall’s marriage theoremMathworldPlanetmath. The name arises from a particular application of this theorem. Suppose we have a finite set of single men/women, and, for each man/woman, a finite collection of women/men to whom this person is attracted. An SDR for this collection would be a way each man/woman could be (theoretically) married happily. Hence, Hall’s marriage theorem can be used to determine if this is possible.

An application of this theorem to graph theoryMathworldPlanetmath gives that if G(V1,V2,E) is a bipartite graphMathworldPlanetmath, then G has a complete matching that saturates every vertex of V1 if and only if |S||N(S)| for every subset SV1.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 14:39:18