Study note: Bipartite Graph

14-1Bipartite Graphs 

• Bipartite graph is one with two sets of nodes. Edges can exist between the sets, but not among a set.
• Algorithm to identify if a Graph is Bipartite: given 2 colors, traverse nodes color them color them and color the neighbor nodes with different colors. If a node has a conflicted color with earlier color decision, the graph is not a Bipartite graph.

14-2 Bipartite Graph Matching

• Define Matching: pairing nodes from two sets in a Bipartite graph, without using repeating elements. (two nodes cannot share the same partner node)
• Max-cardinality Bipartite Matching - include as many pairs as possible.
• Greedy algorithm: iterate through nodes in one side, and find one partner node. (Skip the node if no partner can be found)
• Convert Matching problem into Network Flow
• By connecting a source node to 1 set and connecting a sink to the other set. Then find network that could flow through from source to sink
• assign each edge with 1 weight.
• Solve the network flow problem by Ford-Fulkerson algorithm, and the result paths gave the optimized matching.

14-3 Maximum-Weight Bipartite Matching

• Let edges between 2 sets of nodes to be a matrix. Each edge has a weight. The goal is to find the matching with the max total weights.
• Hungarian Algorithm can solve this by finding the minimum weight.
• prerequisite: the cardinality of  of the two sets must be the same. That means the number of nodes must be the same.
• Time complexity: O(n**3)
• Negating the weights converts the algorithm from finding the minimum total weight to maximum total weight.