Properties of Bipartite Graph

发表于   |   分类于   |  

Basic Knowledge

Vertex Covering

Vertex Covering：
A vertex set and every edge has more one terminal in the set.
Minimal Vertex Covering：
A vertex covering and its any proper subset isn’t a vertex covering.
Minimum Vertex Covering：
A vertex covering who has the minimum vertex.
Vertex Covering Number：
The number of vertexs in the minimum vertex covering.

Edge Covering

Edge Covering：
An edge set and every vertex is adjacent to the edge in the set.
Minimal Edge Covering：
An edge covering and its any proper subset isn’t a edge covering.
Minimum Edge Covering：
An edge coving who has the minimum edge.
Edge Covering Number：
The number of edges in the minimun edge coving.

Independent Set

Independent Set：
A vertex set and every vertex in the set isn’t adjacent to any other vertex in the set.
Maximal Independent Set：
An independent set and the set is no longer an independent set when adding any vertex to it.
Maximum Independent Set：
An independent set who has the maximum vertex.
Vertex Independent Set：
The number of vertexs in the maximum independent set.

Independent set can also be define as a vertex set of a derived subgraph who’s a zero diagram.

Clique

Clique：
A vertex set and every vertex in the set is adjacent to any other vertex in the set.
Maximal Clique：
A clique and the set is no longer a clique when adding any vertex to it.
Maximum Clique：
A clique who has the maximum vertex.
Clique Number：
The number of vertexs in the maximum independent set.

Clique can also be define as a vertex set of a derived subgraph who’s a complete graph.

Edge Independent Set

Edge Independent Set：
An edge set and every edge in the set isn’t adjacent to any other edge in the set.
Maximal Edge Independent Set：
An edge independent set and the set is no longer an edge independent set when adding any edge to it.
Maximum Edge Independent Set：
An edge independent who has the maximum edge.
Edge Independent Set Covering Number：
The number of edges in the maximum edge independent set.

Edge independent set also called matching， corresponding concepts have maximal matching， maximum matching， matching number.

Dominating Set

Dominating Set：
A vertex set and any vertex isn’t in the set has more one adjacent vertex in the set.
Minimal Dominating Set：
A dominating set and it’s any proper subset isn’t a dominating set.
Minimum Dominating Set：
A dominating set who has the minimum vertex.
Dominating Number：
The number of vertexs in the minimum dominating set.

Edge Dominating Set

Edge Dominating Set：
An egde set and any edge isn’t in the set has more one adjacent edge in the set.
Minimal Edge Dominating Set：
An edge dominating set and it’s any proper subset isn’t an edge dominating set.
Minimum Edge Dominating Set：
An edge dominating set who has the minimum edge.
Edge Dominating Number：
The number of edges in the minimum edge dominating set.

Path Covering

Using minimum disjoint edges to cover all the vertexs in the graph.
path covering number = vertexs - edges in path covering

Bipartite Graph

A bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.

Properties

In a bipartite graph：

Property One：
minimum vertex covering = maximum matching

Property Two：
minimum path coverage of DAG = vertexs - maximum matching

Property Three：
maximum independent set = vertexs - maximum matching

Property Four：
maximum matching = matching vertexs in left set + unmatching vertexs in right set

Property Five：
minimum edge covering = maximum independent set

Hungarian Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Module
int find(int x) {
	int i;
	for (i = 1;i <= m;i++) {
		if (bond[x][i] == 1 && march[i] == -1) {
			march[i] = 1;
			if (vis[i] == -1 || find(vis[i]) == 1) {
				vis[i] = x;
				return 1;
			}
		}
	}
	return 0;
}
int main() {
	...
	...
		
	memset(vis, -1, sizeof(vis));
	// Init bond
	for (i = 1;i <= n;i++) {
		for (j = 0;j < MAX;j++)
			march[j] = -1;
		if (find(i) == 1) {
			cnt++;
		}
	}
}