liuy
  • Joined on Jun 01, 2022
Loading Heatmap…

liuy opened issue liuy/yy自控#56

运筹学

8 hours ago

liuy pushed to master at liuy/yy自控

10 hours ago

liuy closed issue liuy/yy自控#54

操作系统

13 hours ago

liuy commented on issue liuy/yy自控#54

操作系统

由增广轨的定义可以推出下述三个结论: 1-P的路径长度必定为奇数,第一条边和最后一条边都不属于M。 2-不断寻找增广轨可以得到一个更大的匹配M’,直到找不到更多的增广轨。 3-M为G的最大匹配当且仅当不存在M的增广轨。 4-最大匹配数M+最大独立数N=总的结点数 增广轨主要应用于匈牙利算法中,用于求二分图最大匹配。

13 hours ago

liuy commented on issue liuy/yy自控#54

操作系统

增广轨的定义(也称增广路或交错轨): 若P是图G中一条连通两个未匹配顶点的路径,并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广轨(举例来说,有A、B集合,增广路由A中一个点通向B中一个点,再由B中这个点通向A中一个点……交替进行)。

13 hours ago

liuy closed issue liuy/yy自控#55

运筹学

13 hours ago

liuy commented on issue liuy/yy自控#55

运筹学

下面的证明提供了一种从最大匹配构造最小顶点覆盖的方法。 设G=(V,E)是一个二部图,设L,R是顶点集V的两个部分。假设M是G的一个最大匹配。在一个顶点覆盖中,没有一个顶点可以覆盖M的一条以上的边(M是一个匹配,所以不存在边的半重叠情况),所以如果可以被构造出一个有|M|个顶点的顶点覆盖,那么它一定是一个最小覆盖。 [1] 下面我们构造一个上述顶点覆盖。设U是顶点集L中未被匹配的顶点的集合(U可能是空集,此时L中的所有顶点都在匹配M中)。设顶点集Z是顶点集U中的顶点通过M交错路相连点的集合。如下关系式取顶点集K: K = ( L \ Z ) ∪ ( R ∩ Z ) 对于边集E中的任意边e , 边e如果不是一个M交错路的一部分,则它的左顶点属于顶点集K。接下来我们证明这一点。如果e是匹配M中的边但不在M交错路中,那么它的左顶点不可能在M交错路中(因为根据匹配的定义,两条同一匹配中的边不能共享一个顶点),也就是说e的左顶点属于L \ Z。在另一种情况中,e既不属于匹配M也不在M交错路中,那么显然e的左端点不能在M交错路中,否则这条M交错路可以通过添加边e进行扩展。因此,K是一个顶点覆盖。 [1] 此外,K中的每个顶点都是一条匹配边的顶点。这是因为L \ Z中的每个顶点都是匹配的。而 R∩Z 中的每个顶点也必须是匹配的,因为如果存在一条与未匹配的顶点交替的M交错路,那么通过删除该路径上匹配的边,在原有位置上添加未匹配的边来改变匹配,会增加匹配的大小。然而,任何匹配中的边都不能有两个端点都在K中。 [1] 因此,K是一个最小的顶点覆盖。

13 hours ago

liuy commented on issue liuy/yy自控#55

运筹学

柯尼希定理由 XDénes Kőnig 于1931年提出的图论领域的定理,用于说明在二分图中最小点覆盖的点数于最大匹配数的相等性。此外Jenő Egerváry在同年同样独立地将其提出,并拓展到了有权图的范围。

13 hours ago

liuy commented on issue liuy/yy自控#53

操作系统

还有,什么是最大匹配?

1 day ago

liuy opened issue liuy/yy自控#54

操作系统

1 day ago

liuy opened issue liuy/yy自控#53

操作系统

1 day ago

liuy opened issue liuy/yy自控#52

运筹学

1 day ago

liuy opened issue liuy/yy自控#51

运筹学

1 day ago

liuy upload dataset a4a7c7d04cdb4b54_0.jpg

2 days ago

liuy upload dataset a3c7b7b1c396490a_1.jpg

2 days ago

liuy upload dataset a03f973bda0f0361_4.jpg

2 days ago

liuy upload dataset a1e31837c89aceb9_1.jpg

2 days ago

liuy upload dataset a1e5db16cc5be0d0_0.jpg

2 days ago

liuy upload dataset a1d48349ee9a9af8_2.jpg

2 days ago

liuy upload dataset a1c5ca9f4ef90269_2.jpg

2 days ago