作业帮离散数学当中的匹配网络问题,都有什么应用?
来源：学生作业帮 编辑：作业帮 分类：综合作业 时间：2024/11/09 05:18:25
离散数学当中的匹配网络问题,都有什么应用?
课程的内容里面除了介绍了概念以后就什么都没有了.
这个"匹配网络"问题,在实际当中都有什么应用呢?
课程的内容里面除了介绍了概念以后就什么都没有了.
这个"匹配网络"问题,在实际当中都有什么应用呢?
以V1＝｛L1,L2,L3,L4,L5,L6｝和V2＝｛G1,G2,G3,G4,G5,G6｝为顶点组,若Li和Gj互为结婚对象,则在两个顶点之间添加一条边,如此构造出一个二分图（图一）.
V1中任意k个点（k＝1,2,...,6）至少与V2中k个点相邻,V1和V2中顶点个数相同,所以存在从V1到V2的完美匹配.
图一改画为图二,图二中两部分皆有2个完美匹配,由此得图一的完美匹配：
（1）L1－G1,L2－G3,L3－G4,L4－G2,L5－G6,L6－G5
（2）L1－G4,L2－G3,L3－G1,L4－G2,L5－G6,L6－G5
（3）L1－G1,L2－G5,L3－G4,L4－G6,L5－G3,L6－G2
（4）L1－G4,L2－G5,L3－G1,L4－G6,L5－G3,L6－G2
V1中任意k个点（k＝1,2,...,6）至少与V2中k个点相邻,V1和V2中顶点个数相同,所以存在从V1到V2的完美匹配.
图一改画为图二,图二中两部分皆有2个完美匹配,由此得图一的完美匹配：
（1）L1－G1,L2－G3,L3－G4,L4－G2,L5－G6,L6－G5
（2）L1－G4,L2－G3,L3－G1,L4－G2,L5－G6,L6－G5
（3）L1－G1,L2－G5,L3－G4,L4－G6,L5－G3,L6－G2
（4）L1－G4,L2－G5,L3－G1,L4－G6,L5－G3,L6－G2