Contents

Graph::bipartite

Finds out if a graph is bipartite.

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

Graph::bipartite(G, <Bool | Lists>)

Description

Graph::bipartite(G) finds out whether G is bipartite or not.

Graph::bipartite(G, Sets): If G is bipartite, then a list containing two lists will be returned. Each of the lists contains the vertices belonging to the set. If G is not bipartite, then FAIL will be returned instead of any list.

Graph::bipartite(G, Bool) offers the same result as Graph::bipartite(G). If G is bipartite, then TRUE will be returned, otherwise FALSE.

Examples

Example 1

A small graph containing 3 vertices with 2 edges connecting them is created:

G := Graph([a, b, c], [[a, b], [b, c]]):
Graph::bipartite(G, Lists); 
Graph::bipartite(G, Bool)

Two lists with vertices are shown. Another word for bipartite is two-colorable. This means that the graph above can be colored with only two colors so that no two vertices have the same color if connected with an edge. The bottom output could also be accomplished without using the parameter Bool:

Graph::bipartite(G)

The following example shows what happens when a graph is not bipartite (an edge is added to connect the vertices a and c):

G2 := Graph::addEdges(G, [[a, c]]):
Graph::bipartite(G2, Lists); 
Graph::bipartite(G2, Bool)

Parameters

G

Graph

Options

Lists

If Lists is stated the return value will be a list of two lists containing the (sorted) vertices belonging to each set, or FAIL.

Bool

If Bool is stated the return value will be either TRUE or FALSE. This is the default.

Return Values

Depending on the options either a boolean value or list-sets will be returned.

Was this topic helpful?