Question

Direct bipartite matching. We’ve seen how to find a maximum matching in a bipartite graph via reduction to the maximum flow problem. We now develop a direct algorithm.

Let $G=(V1\cup V2,E)$be a bipartite graph (so each edge has one endpoint in $V1$and one endpoint in $V2$), and let$M\in E$be a matching in the graph (that is, a set of edges that don’t touch). A vertex is said to be covered by$M$if it is the endpoint of one of the edges in $M$. An alternating path is a path of odd length that starts and ends with a non-covered vertex, and whose edges alternate between $M$and $E-M$.

(a) In the bipartite graph below, a matching $M$is shown in bold. Find an alternating path.

(b) Prove that a matching$M$is maximal if and only if there does not exist an alternating path with respect to it.

(c) Design an algorithm that finds an alternating path in$O\left(\left|V\right|+\left|E\right|\right)$time using a variant of breadth-first search.

(d) Give a direct$O\left(\left|V\right|-\left|E\right|\right)$algorithm for finding a maximal matching in a bipartite graph.

Short answer

a) A matching and an alternating path is shown below.

b) A matching is maximal if and only if there does not exist an alternating path with respect to it is proved.

c) An algorithm that finds an alternating path in$O\left(\left|V\right|+\left|E\right|\right)$ time using a variant of breadth-first search.

d) A direct$O\left(\left|V\right|-\left|E\right|\right)$ algorithm for finding a maximal matching in a bipartite graph.

Step-by-step solution

The bi-partition of the graph G:

In the below answer is given base on numerical base. But to count all above figure alphabet as number like: $A=1,B=2,C=3$same way continue go on. Take be the name of the provided bipartite graph. Figure show that bold lines are different than thin lines. And try to prove about lines which is follow alternating path with respect and proving a matching as maximal details.

Bipartite graph is a graph $G$whose vertices are role="math" localid="1659789971712" $u$and v here u and$v$ are bipartite to each other it means all nodes of graph$u$is connected itself or is not connected with any other node in a same graph as well as with graph$v$. The vertices of$u$are connected by vertices of$v$but the nodes of these graph are not connected with any node of its own graph is known as bipartite graph.

Breadth First Search it traverse the tree from level one to the end level in a horizontal order so it is also called level order traversal.

Queue is used as a data structure inbreadth first search.

Maximum flow from G:

b)

For resolve the maximum matching issue, we'll reduce it to the maximum flow problem in graph H, which may be built from$G$in the following way. It's worth noting that. $V\left(H\right)=V\left(G\right)\cup s,t$That is, a dummy source vertex and a dummy sink vertex t are introduced. All of the vertices in $A,B,C,D,E$are created next to the vertex $s$, and all of the vertices in$1\text{'},2\text{'},3\text{'},4\text{'},5\text{'}$are made adjacent to the vertex $t$.$H$is the new graph we've created, and we're going to give all of the edges unit capacity. Then, to attain the highest$s-t$flow in $H$, either the ford fulkerson or the edmondkarp method might be utilised. The maximum matching size is the same as the maximum flow size.

In addition, in $G$, the maximum flow edges will create a maximum matching.

A simulation is shown below.

Flow Augmented	Maximum matching edges in G
1.$S–1–1’–T$	$1–1’$
2.$S–2–2’–T$	$2–2’$
3.$S–3–4’–T$	$3–4’$
4.$S–4–5’–T$	$4–5’$

Conclusion

Eventually, throughout , the corresponding edges are $1-1\text{'},2-2\text{'},3-4\text{'}$, and $4-5\text{'}$.

Thus greatest flow achieved would result in either a minimal cut that separates the vertices $1,4,5,2\text{'},5\text{'}$, $2,3,1\text{'},3\text{'},4\text{'}$in $G$.

The algorithm's minimum cut is $1,4,5,2\text{'},5\text{'}$,$2,3,1\text{'},3\text{'},4\text{'}$

Step 4: Algorithm that finds an alternating path by using a variant of breadth-first search.

b).

Breadth First Search it traverse the tree from level one to the end level in a horizontal order so it is also called level order traversal. Queue is used as a data structure inbreadth first search.

linear-time algorithm to determine an odd-length cycle in a directed graph with the assumption that the graph is strongly connected this can we done by BFS. or also finding out whether a directed graph is bipartite or not.

Algorithm to determine the given graph isbipartite or not in a directed graph by breadth first search (BFS) is as follows,

1). Consider graph $G$which contain two sets of graphs named as$u$and $v$.

2). Take Red color node as a source vertex and put this vertex in a set $u$. after that color all the vertices blue which are directly connected to the source vertex and put these vertices to another set named $v$.

3). After that the blue vertex is connected with other node, color it red and put into the set of $u$graph.

4). The vertices of blue color and the vertices are in red color are not directly connected to each other. It means take all vertices of graph$u$ is in red color and all vertices of graph $v$is in blue color.

5).Like that, assign red and blue color to all vertices and it satisfies all the constraints of way coloring problem in which $m=2$.

From this it is clear that if any graph has odd length cycle then it cannot be bipartite. And it is also proved that if a graph is bipartite then it always contains even number of cycles are only by using the graph coloring property.

Hence, the algorithm takes $O\left(\left|V\right|+\left|E\right|\right)$time using a variant of breadth-first search.

Algorithm for finding a maximal matching in a bipartite graph.

d).

Here an undirected graph is bipartite if and only if it contains no cycles of odd length. Or if it contains cycle of even length then only it is bipartite graph.

In this diagram shown in fig $2$, there are some edges they are $0,1,2,3,4,5,6$. If$0$is the source vertex so color it red from$0$the two nodes areconnected they are one and three color these both vertex with blue color.

Now, look at the vertex$1$and $3$if any edge is connected to$1$and $3$then color it red.

From$1$again two edges are connected that are$4$and$5$so color these by blue color.

andAgain search the next node is$2$check whether is connected to any red colored node or not, if no then color it red.

Apply this method from each vertices and now the remaining vertex is$6$, which is connected by both $4$and $5$and here both$4$and$5$are colored with blue so there color the number 6 vertex as red. Through this it shows we the undirected graph is bipartite.

Fig:2 Showing undirected bipartite graph.

.

Fig:3 Showing undirected bipartite graph.

Hence, it will take time of $O\left(\left|V\right|-\left|E\right|\right)$for finding a maximal matching in a bipartite graph.