`算法知识` 二分图Biparitite-Graph

算法 {染色法判定二分图,点覆盖,独立集}

二分图

定义

二分图Bipartite Graph;

#前言#: 点集$L,R$; 无向边集$E$;
#条件#: 任意E中的无向边 都形如$(l_i,r_j)$的形式(即两个端点 各属于$L,R$);
#结论#: 无向图$(L\cup R,E)$为二分图;

#等价描述#: 二分图中的所有点 可以分为2类: $L,R$, 任意无向边的两个端点 一定横跨$L,R$;

相关定义

A Match (匹配) is a set of edges $\{(l1,r1),(l2,r2),...\}$ such that $li\ne lj$ and $ri\ne rj$.

Given a match $\{(l1,r1),...\}$, a point $a$ is called Matched-Point (匹配点) if $a=li$ or $a=rj$; otherwise, it is called Unmatched-Point (非匹配点);

--

A Point-Coverage (点覆盖) $S$ is a set of points which involves all edges; (i.e., for any edge $a1-a2$, at least one point $ai\in S$)

The Minimum Point Coverage (最小点覆盖) is a Point-Coverage with the minimal $|S|$;
__. (it usually occurs in the context of Bipartite-Graph)

--

A Independent-Set (独立集) $S$ is a set of points such that $(a-b)\notin E,\forall a,b\in S$.

The Maximum Independent Set (最大独立集) is a Independent-Set with the maximal $|S|$;

算法

二分图的存储

假如题意是: 左集合所有点为[1, ..., NL], 右集合所有点为[1, ..., NR], 然后(l, r)表示一条无向边;
#算法#:

G.Initialze( NL + NR);
for( `(l,r)` : 所有边){
	-- l, -- r, r += NL;
	G.Add_edge( l, r), G.Add_edge( r, l);
}
1
2
3
4
5

即左集合所有点是[0, NL), 右集合所有点是[NL, NL+NR);

染色法判定二分图

namespace ___Check_BipariteGraph{
vector Flag; // 所有點都染色為`0/1`;

bool Work( const ___Graph & _unDiG){
//< 確保`_unDiG`是*無向圖*;  如果是*二分圖* 則返回值為`true`;
    Flag.resize( _unDiG.PointsCount);  memset( Flag.data(), -1, sizeof(Flag[0]) * Flag.size());

    function Dfs = [&](int _cur, int _flag){
        Flag[ _cur] = _flag;
        for( int nex, e = _unDiG.Head[ _cur]; ~e; e = _unDiG.Next[ e]){
            nex = _unDiG.Vertex[ e];
            if( Flag[ nex]==-1 && false==Dfs( nex, _flag^1)){ return false;}
            if( Flag[ nex] == _flag){ return false;}
        }
        return true;
    };
    for( int i = 0; i < _unDiG.PointsCount; ++i){
        if( Flag[ i]==-1 && false==Dfs( i, 0)){ return false;}
    }
    return true;
}
} // namespace ___Check_BipariteGraph
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

@DELI;

点覆盖

+ A Point-Coverage $S$, its complementary-set $V-S$ is always be a Independent-Set;
. If not, then there is a contradiction: $\exists (a-b)\in E,a\in (V-S)\wedge b\in (V-S)\to \exists (a-b)\in E,a\notin S\wedge b\notin S\to S\text{ is not a Point-Coverage}$
. As a consequence, the complementary-set $V-S$ of a Minimum-Point-Coverage $S$, is always be a Maximum-Independent-Set;

在二分图中

let $m$ be the maximal-match, cuz these $m$ edges are disjoint, $|S|$ must $\ge m$.
Conclusion: $|S|=m$ where $S$ is the Minimum-Point-Coverage; and the process for constructing $S$ showed below:

ASSUME( `(l1-r1),...,(ln-rn)` are the Maximum-Matches); //< i.e., `l1,...,ln; r1,...,rn` are all Matched-Points;
ASSUME( `ll1,...,llm; rr1,...,rrk` are all Unmatched-Points);
vector ans := the Minimum-Point-Coverage;
set lef := see below;
for( l : {ll1,...,llm}){
	for( r : the adjacent-points of `l`){
		ASSERT( `r` is a Matched-Point);
		ans.push_back( r);
		lef.insert( $(the corresponding Left-Point of `r` in the Maximum-Matchs));
	}
}
for( l : {l1,...,ln}){
	if( l \in lef){
		continue;
	}
	ans.push_back( l);
}
ASSERT( ans.size() == n);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

例题

+ link

独立集

+ A Independent-Set $S$, its complementary-set $V-S$ is always be a Point-Coverage;
. If not, then there is a contradiction: $\exists (a-b)\in E,a\notin (V-S)\wedge b\notin (V-S)\to \exists (a-b)\in E,a\in S\wedge b\in S\to S\text{ is not a Independent-Set}$
. As a consequence, the complementary-set $V-S$ of a Maximum-Independent-Set $S$, is always be a Minimum-Point-Coverage;
+ $\forall a\in S$, $a$ may have a adjacent-edge $(a-b)$ ($b$ must $\notin S$);
. $\forall a,b\in S$, although there is no edge (not path) between them, they maybe accessible by a path, e.g., a path $a-c-b$ where $c\notin S$ is possible;

二分图中

Let the Bipartite $(L,R,E)$, $m$ be its maximal-match; for the theorem of Minimum-Point-Coverage, we have $m=|S|$ where $S$ is the Minimum-Point-Coverage; therefore, we have $|L|+|R|-m$ is the size of Maximum-Independent-Set; (that is, once you got the Minimum-Point-Coverage, its complementary-set is the answer)

例题

+ link

延伸阅读

+ DAG的(最小路径点覆盖) link