首页 > 试题广场 >

完全匹配是指图中所有结点都得到匹配的匹配。 设G= (V,

[问答题]
完全匹配是指图中所有结点都得到匹配的匹配。  设G= (V,  E)是结点划分为V=LUR的无向二分图，其中|L|=|R|。对于任意XV,定义X的邻居为:
                            N(X) = {y∈V:对某个x∈X,(x,y)∈E}
即由与X的某元素相邻的结点所构成的集合。请证明Hall定理:图G中存在一个完全匹配当且仅当对于每个子集A L，有|A|≤| N(A)|

查看答案及解析
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小
难度：
0条回答 130浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号