Overview
The Bipartite algorithm is used to determine whether a given graph is a bipartite graph. By applying the algorithm, it becomes possible to identify and utilize the inherent structure of bipartite graphs in different scenarios, enabling efficient resource allocation, task assignment, and grouping optimization.
Concepts
Bipartite Graph
A bipartite graph, also known as a bigragh, is a graph which the nodes can be divided into two disjoint sets, such that every edge in the graph connects a node from one set to a node from the other set. In other words, there are no edges that connect nodes within the same set.
This example graph is bipartite. The nodes can be partitioned into sets V1 = {A, D, E} and V2 = {B, C, F}.
Coloring Method
To determine if a graph is bipartite, one common approach is to perform a graph traversal and assign each visited node to one of two different sets. This process is often referred to as "coloring" the nodes. During the traversal, if an edge is encountered that connects two nodes within the same set, then the graph is not bipartite. Conversely, if all edges connect nodes from different sets, the graph is bipartite.
In this example, both graph A and graph B are bipartite. Graph C is not bipartite as it contains an odd cycle. An odd cycle is a cycle that has an odd number of nodes. Bipartite graphs cannot contain odd cycles because it is not possible to color all the nodes of an odd cycle using only two colors while still meeting the requirement of bipartiteness. This property, where bipartite graphs never contain any odd cycles, is a fundamental characteristic of bipartite graphs.
Considerations
- Two endpoints of a self-loop are the same node, thus graphs that have any self-loop are not bipartite.
- The Bipartite algorithm ignores the direction of edges but calculates them as undirected edges.
Syntax
- Command:
algo(bipartite) - This algorithm has no parameters.
Examples
The example graph is as follows:
Direct Return
Alias Ordinal |
Type |
Description | Columns |
|---|---|---|---|
| 0 | KV | Whether the graph is bipartite, 0 means false, 1 means true | bipartite_result |
algo(bipartite).params() as result
return result
Results: result
| bipartite_result |
|---|
| 1 |
Stream Return
Alias Ordinal |
Type |
Description | Columns |
|---|---|---|---|
| 0 | KV | Whether the graph is bipartite, 0 means false, 1 means true | bipartite_result |
algo(bipartite).params().stream() as result
return result
Results: result
| bipartite_result |
|---|
| 1 |
Stats Return
Alias Ordinal |
Type |
Description | Columns |
|---|---|---|---|
| 0 | KV | Whether the graph is bipartite, 0 means false, 1 means true | bipartite_result |
algo(bipartite).params().stats() as result
return result
Results: result
| bipartite_result |
|---|
| 1 |