第8章 匹配问题.ppt

1、第8章匹配问题，Matching Problem，澳大利亚员工方坤，匹配定义，匹配最大匹配点曝光点完全匹配交错增量，查找最大匹配，rema 1设置P是网络N中匹配M的增量，M和P的对称差分MMP (MP) (Theorem 1) 如果网络没有以P为起点的扩展路径，则n具有最大匹配M，因此P信息M*也是曝光点；如果具有外部点和内部点，并且道路上的胡歌匹配圆弧和自由胡歌交替出现，则P称为隔行道；隔行道和起点距离为偶数的节点称为外部点，距离为奇数的节点称为内部点，Example，定义，查找最大匹配-扩展路径算法，根据Theorem 2，如果在曝光点P中找不到扩展路径，则可以从n中删除节点P和相关圆弧

2、。不影响最大匹配标准。For example V2，A)中的任意匹配M(例如M)，标记所有N的节点I标签(I)=Null。如果STEP 1 V1没有曝光点，则M为最大匹配，结束。否则，在N处选择曝光点P。节点P的标签为标签(P)=Outer，List=P.step3 2。List=时，由于没有从P开始的加宽道路，因此请从N移除节点P和关联的弧，并移至Step1。否则，请执行步骤4。如果步骤3对I中的每个相邻节点j: j是曝光点，请转至步骤5:q=j，pred(q)=i。如果j是匹配点，label(j)=null，则pred (j)=I，label (j)=inner，list=listj。St

3、ep2。(注：)到了尽头了吗？)Step4机I的匹配点是j 3360 label(j)=null，则pred (j)=I，label (j)=outer，list=listj，Step否则stepStep5使用阵列pred中记录的信息确定p-q增量为P-Q增量(从节点Q到回溯)，并执行扩展操作MMP。在所有N中，将节点I标记为label(i)=null。在郑智薰第2部分基数匹配问题、增广路算法的失败案例、花Flower、网络N的匹配M和曝光点P的情况下，由满足以下条件的交错和奇数圆组成的子图形称为花：(1)此子图的交错是P到Q的交错，Q是此交错中的单点。(2)在此子图中，奇数圆和交错道路的唯一

4、交点是Q，圆的自由圆弧与重合圆弧交替出现，与圆上的Q关联的两个圆弧都是自由圆弧。p-q交错的路被称为花茎，q-q齿圈被称为花，P是根，q是花蒂。For example，花的收缩，对于网络N的匹配M和花W，网络N的W的收缩(用N/W表示)定义为：(1)使用人工节点W代替花W。也就是说，添加人工节点W，删除花W的所有节点。(2)修改原始网络的圆弧。也就是说，与原始W的节点相邻的所有节点都与W相邻。For example，非冗馀图形的匹配算法(1)，Step0在网络n中选择匹配m之一，所有n中节点I的标签为label(i)=null。指定Step1。如果n没有曝光点，则m为最大匹配，结束否则，在N处

5、选择曝光点P。节点P的标签为(I)=Outer，list=P.Step3 2。list=时，由于没有从P开始的加宽道路，因此请从N移除节点P和关联的弧，并移至Step1。否则，Step4 .如果与Step3对I相邻的每个节点j: label(j)=outer，请转至Step5。如果j是曝光点，请启用q=j，pred(q)=i，Step6。如果j是匹配点，label(j)=null，则pred (j)=I，label (j)=inner，list=listj。Step2。非对角图的匹配算法(2)，Step4机I的匹配点是j:如果label(j)=inner，请切换到Step5。Label(j)=null时，pred (j)=I，label (j)=outer，list=listj，Step2否则，Step2 .直接转到Step5，找到相应的花，缩小到人工节点，然后修改网络和列表。将此手动节点标记为outer，将此手动节点添加到list，然后将Step2 .转到Step6，使用记录为pred数组的信息通过节点Q上的回溯确定p-q扩展路径P。展开P的手动节点，查看不包含手动节点的扩展路径P。执行扩展操作M