关于图论中完全匹配的一道题目
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/06/30 19:07:59
关于图论中完全匹配的一道题目
一道图论题目:设R是A到B的一个关系且|A|=|B|=n,证明:如果在A,B和R相对应的网络中,每一个节点的度数至少是n/2,那么对于A,B和R,存在一个完全匹配.提示是利用哈密尔顿回路回路存在性的一个定理:如果n个顶点的连通图每个顶点的度数至少为n/2,那么该图必定存在一条哈密尔顿回路.
一道图论题目:设R是A到B的一个关系且|A|=|B|=n,证明:如果在A,B和R相对应的网络中,每一个节点的度数至少是n/2,那么对于A,B和R,存在一个完全匹配.提示是利用哈密尔顿回路回路存在性的一个定理:如果n个顶点的连通图每个顶点的度数至少为n/2,那么该图必定存在一条哈密尔顿回路.
![关于图论中完全匹配的一道题目](/uploads/image/z/7406449-25-9.jpg?t=%E5%85%B3%E4%BA%8E%E5%9B%BE%E8%AE%BA%E4%B8%AD%E5%AE%8C%E5%85%A8%E5%8C%B9%E9%85%8D%E7%9A%84%E4%B8%80%E9%81%93%E9%A2%98%E7%9B%AE)
我将所述之图理解为一个二部图,记为G,部集为A和B,关系R则是边集.由于图中存在一条Hamilton回路,记此回路为H,则H为G的生成子图.在H中,因点集A中的点之间没有边相连,且每个点的度数为2 (对于B也一样),故H是一个2正则的二部图.由于“任意 r 正则二部图(r≥1)均有一个完美匹配.”故H含有一个完美匹配,因H是G的生成子图,当然H的完美匹配亦是G的完美匹配,从而完成证明.
注:定理“任意 r 正则二部图(r≥1)均有一个完美匹配.”之证明详见Gary Chartrand等著的《图论导引》第八章“匹配与分解”.
生成子图的定义是:如果图G的一个子图与G有相同的顶点集,那么该子图是图G的一个生成子图.
注:定理“任意 r 正则二部图(r≥1)均有一个完美匹配.”之证明详见Gary Chartrand等著的《图论导引》第八章“匹配与分解”.
生成子图的定义是:如果图G的一个子图与G有相同的顶点集,那么该子图是图G的一个生成子图.