Change Password

Input error
Input error
Input error
Submit

Change Nickname

Current Nickname:
Submit
Search
v2.x
    v4.0

    Bipartite Graph

      Basic  

    Overview

    Bipartite algorithm can judge if the current graph is a bipartite graph and return the result (true or false). The judgement and division of bipartite graph is widely used in scenarios such as resources allocation and grouping optimization.

    Basic Concept

    Bipartite Graph

    Bipartite graph is also known as bigragh. If divides all nodes in a graph into sets A and B, the two endpoints i and j of each edge in the graph belong to each set, i.e. i ∈ A and j ∈ B, or i ∈ B and j ∈ A, then the graph is called a bipartite graph.

    As shown in the above graph, after dividing nodes in the graph into two groups of "yellow, red, purple" and "blue, grey, green", there is no edge in the groups, all edges exist between groups, thus we can say the original graph is a bipartite graph.

    Drawing an open curve to divide nodes in a graph into two parts, meanwhile assuring that all edges in the graph intersect the curve only once, the following can be achieved if the graph is a bipartite graph: when the curve is closed, each edge in the graph still intersects the curve only once.

    Observe the example above, the curve in Graph A meets the requirement of bipartite graph, so Graph A is a bipartite graph; the curve in Graph B intersects one edge twice inevitably, so Graph B is not a bipartite graph.

    A cycle with even nodes is called an Even Cycle, a cycle with odd nodes is called an Odd Cycle. Reasoning from the example above: Cycles in bipartite graph must be even cycles. Because when the curve crosses the edges of an even cycle in turn, the start and end points of the curve are on the same side of the cycle (inside or outside); however, odd cycle causes the start and end points of the curve on different sides of the cycle, the curve has to intersect with one edge twice to close itself.

    Coloring Method

    Coloring is one of the fundamental methods to determine bipartite graph. Since bipartite graph requires that the nodes to be divided into two sets, and no edge may connect two nodes that are in the same set, so all nodes in the graph can be colored in two different colors. The principle of coloring is that the adjacent nodes are colored with different colors. If it is found that same color is used for adjacent nodes, or different colors appear in the multiple neigbors of a node, then it can be concluded that the graph is not a bipartite graph.

    In the example above, Graph A and B are colored successfully, while coloring for Graph C fails. The coloring method proves the previous reasoning of "Even Cycle" from another perspective: When coloring nodes along the cycle, even cycle ensures that the nodes are alternately colored in different colors, while the first and last nodes in odd cycle have to use the same color.

    Special Case

    Lonely Node, Disconnected Graph

    Introducing pure lonely node (without self-loop edge) into graph does not affect the bipartition of the original graph.

    Bipartition is examined for each connected component in disconnected graph, only when all the connected components are bipartite graph, the original graph is bipartite graph.

    Self-loop Edge

    Two endpoints of self-loop edge are the same node, thus graph that involves self-loop edge does not meet the requirement of bipartite graph.

    Directed Edge

    For directed edges, Bipartite algorithm ignores the direction of edges but calculates them as undirected edges.

    Command

    algo(bipartite)

    File Writeback

    (Not supported)

    Property Writeback

    (Not supported)

    Statistics Writeback

    .write() and when executing other writeback operations:

    Name Type Description
    bipartie_result int Result of the bipartite judgement: 0: false; 1: true

    Direct Return

    as <alias> return <alias>

    Alias Number Type Description Column Name
    0 KV Result of the bipartite judgement: 0: false; 1: true bipartite_result

    Streaming Return

    (Not supported)

    Real-time Statistics

    .stats() as <alias> return <alias>

    Alias Number Type Description Column Name
    0 KV Result of the bipartite judgement: 0: false; 1: true bipartite_result
    Please complete the following information to download this book
    *
    公司名称不能为空
    *
    公司邮箱必须填写
    *
    你的名字必须填写
    *
    你的电话必须填写
    *
    你的电话必须填写