Bipartite Graph

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 V₁ = {A, D, E} and V₂ = {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

UQL
algo(bipartite).params() as result 
return result

Results: result

Stream Return

UQL
algo(bipartite).params().stream() as result 
return result

Results: result

Stats Return

UQL
algo(bipartite).params().stats() as result 
return result

Results: result