admin 管理员组

文章数量: 1086019

图论

二部图

文章目录

  • 二部图
    • 二部图
      • 定义
      • 定理
    • 匹配
      • 定义
      • 寻找最大匹配
      • 定理
      • 寻找最大匹配的一般方法

二部图

定义

  1. 二部图（二分图）：有无向图G=<V,E>,若能将V分成V1和V2，V1和V2并集为点集V，交集为空，是的G的每一条边的两个端点，一段属于V1，另一端属于V2，记作<V1,V2,E>,V1,V2为互补顶点子集
  2. 若G是简单图，若V1中的每个顶点均与V2中每个顶点都相邻，则称G为完全二部图，记作 K r , s K_r,s Kr​,s,其中r-|V1|,s=|V2|

定理

  1. 二部图的判定：当且仅当G中没有奇数边的回路，

匹配

定义

  1. 设G=<V,E>是二部图，且 M ⊆ E M\subseteq E M⊆E,若M中任意两条边都不相邻，即没有公共点，则称M为G的匹配

  2. 如果M是G的匹配，且M中再加入任何一条边就不匹配了，则称M为极大匹配

  3. 匹配数：极大匹配的边数，记作 β 1 \beta_1 β1​

  4. a i 与 b j 被 M 匹 配 ： ( a i , b j ) ∈ M a_i与b_j被M匹配：(a_i,b_j)\in M ai​与bj​被M匹配：(ai​,bj​)∈M

  5. a i a_i ai​为M的饱和点：M中有边与 a i a_i ai​关联,反之为非饱和点。

  6. M为完美匹配：G的每个顶点都是M饱和点

  7. 完备匹配：若 G = < v 1 , V 2 , E > , ∣ V 1 ∣ ≤ ∣ V 2 ∣ G = <v_1,V_2,E>,|V_1|\leq|V_2| G=<v1​,V2​,E>,∣V1​∣≤∣V2​∣,M 是G中最大匹配，若 V 1 V_1 V1​中顶点全是M饱和点，则称M为G中 V 1 到 V 2 V_1到V_2 V1​到V2​的完备匹配。

  8. 寻找

寻找最大匹配

  1. 为了寻找最大匹配，引入交替通路和增长通路两个概念

    假设 G = < V 1 , V 2 , E > G = <V_1,V_2,E> G=<V1​,V2​,E>是二部图，M是G的匹配，P是G中的一条通路，

    1. 如果P是由G中属于M的边和不属于M的边交替组成，则称P为G的M交替通路
    2. 如果交替通路的起始点和终点都是M的非饱和点，则称为G的M增长通路。

定理

  1. 把增长通路中所有属于M的边从M中去掉，不属于M的边添加到M中，得到的新边集M1也是一个匹配，并且包含边数比M多1
  2. $G =<V_1,V_2,E> $是二部图，M为G的急打匹配的充要条件是G中不存在M增长通路

寻找最大匹配的一般方法

设G=<V1,V2,E>是二部图，通常先作G的一个匹配M，再看V1中有没有M的非饱和点。如果没有，那么M肯定是最大匹配；如果有，就从这些点出发找M增长通路。由M增长通路作出一个更大的匹配。所以，在G中求最大匹配的关键是寻找M增长通路

本文标签： 图论

版权声明：本文标题：图论 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1686716037a28597.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。