图论支配集、点独立集、点覆盖集

朴灿烈づ我的快乐病毒、 2023-05-28 06:59 165阅读 0赞

例图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2htX18yMDE2_size_16_color_FFFFFF_t_70]

*  点支配集：（个人理解就是**点覆盖所有点**）  
    给定无向图G =（V , E）,其中V是点集， E是边集， 称V的一个子集S称为支配集当且仅当对于V-S中任何一个点v, 都有S中的某个点u, 使得(u, v) ∈E。  
    举个例子：下图的极小支配集为\{V1,V5\}，\{V3，V6\}，\{V2,V4,V6\}  
    PS:极小指如果再减小集合的任一一个顶点都不能构成支配集  
    该图的支配数为2，即至少需要两个顶点才能构成支配集
    
        {V1,V5}构成点支配集的图

![在这里插入图划横线的片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2htX18yMDE2_size_16_color_FFFFFF_t_70_pic_center]

*  点独立集  
    给定无向图G =（V , E）,其中V是点集， E是边集， 称V的一个子集S称为点独立集当且仅当对于S中任何一对顶点(a,b), 都有不存在边（u,v） 使得(u, v) ∈E。（即点独立集中任一两个顶点不相邻）  
    上图的极大点独立集为\{V1,V5\}，\{V2,V3,V7\},\{V3,V6\}  
    PS：极大指再添加任何一个顶点都不构成独立集  
    点独立数为3，即至多可以有3个顶点构成的点独立集
    
        {V1,V6}构成的点独立集图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2htX18yMDE2_size_16_color_FFFFFF_t_70_pic_center 1]

*  点覆盖集（个人理解就是**点覆盖所有边**）  
    给定无向图G =（V , E）,其中V是点集， E是边集， 称V的一个子集S称为点覆盖集当且仅当对于G中任何一边e∈E都有至少一个端点u∈S。（即点覆盖集覆盖所有边）  
    例如上图中的一个极小点覆盖集\{V1,V2,V5,V6\}  
    PS:极小指再添加其中的任一个顶点都不构成点覆盖集  
    点覆盖数为4，即至少需要4个顶点才能构成点覆盖集
    
        {V1,V2,V5,V6}构成的点覆盖集图
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2htX18yMDE2_size_16_color_FFFFFF_t_70_pic_center 2]  
    这几个概念实在很容易混乱，希望这几个图能帮助大家理解~  
    有些定义是按照自己定义去写的，非标准定义，如果有错误，欢迎大家批评指正!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2htX18yMDE2_size_16_color_FFFFFF_t_70]: /images/20230528/624910231f1444f0be98f26fcc5db6f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2htX18yMDE2_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/0f3d06467b394c80adde562bd2bce536.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2htX18yMDE2_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/60a4e9cf97cb419794168fbcaf3adfd0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2htX18yMDE2_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230528/599e0456799d498dacb4ea0b90aeda10.png