Bipartiteness

• A graph is bipartite if it is possible to break a graph G into two independent sets (of vertexes), where every edge between the two sets is connected to from set 1 to set 2 or vise versa. So a single vertical cut can go through all the edges of the bipartite graph.

• If such a rearrangement of graph $G$ exists, then the graph is bipartite.

Visually

• The two independent sets $U$ and $V$ can be thought of having as a coloring of a graph using only two colors (a chromatic number of 2) with the restriction no two adjacent vertices share the same color. If such a property can exist in the graph, then the graph is bipartite.

For example, the following Peterson graph can be shown to have a minimumal coloring of 3.

• Additionally, a graph is bipartite if and only if it does not contain an odd cycle (a cycle with an an odd number of vertices). Consider a triangle, for example.

Self Notes

• Assumptions

  • Implementation from undirected weighted hashlist (from Book A)

  • Input graph $G$ is a single connected component.

• Basically what I have done is alternate between two colors (red, and blue) and run a DFS on the graph, alternating colors as I go. As DFS backtracks, it will ensure that all nodes adjacent to some node $S$ will be a different color, otherwise the algorithm seizes and false is returned.

Implementation

enum Color {
    Blue, Red
};

//...

bool isBipartite()
{
    // assuming A exists in graph, as arbitrary starting vertex
    const Node *start = &graph.find(Node("A"))->first;
    Color cur_color = Blue;
    bool rec_stop = false;
    return isBipartite_rec(start, cur_color, rec_stop);
}

bool isBipartite_rec(const Node *cur_node, Color cur_color, bool &rec_stop)
{
    if (rec_stop) return false;

    const_cast<Node&>(*cur_node).color = cur_color;
    const_cast<Node&>(*cur_node).state = Visited;

    unordered_set<Node> adjNodes = findAdj(*cur_node);

    if (cur_color == Blue)
        cur_color = Red;
    else cur_color = Blue;

    for (auto i : adjNodes) {
        const Node *the_real_node = &graph.find(i)->first;
        if (the_real_node->state == Visited &&
            the_real_node->color == cur_node->color) {
            rec_stop = true;
            return false;
        }

        if (the_real_node->state == UnVisited) {
            isBipartite_rec(the_real_node, cur_color, rec_stop);
        }
    }

    return true;
}

int main()
{
    // usage
    const string filepath = "../infiles/is_bipartite1.txt";
    Graph g(filepath);
    cout << boolalpha << g.isBipartite() << endl << endl;
}

Test Files

Non-bipartite graphs:

5
A : B-0, C-0
B : D-0, C-0
C : D-0, E-0
D : E-0
E :

3
A : B-0
B : C-0
C : A-0

Bipartite Graphs

9
A : E-0, F-0, I-0
B : G-0
C : H-0
D : H-0

6
A : F-0, E-0, D-0
B : F-0, E-0, D-0
C : F-0, E-0, D-0

8
A : H-0, B-0, D-0
B : A-0, G-0, C-0
D : A-0, C-0, E-0
E : F-0, H-0 
F : G-0, E-0
G : F-0, H-0
H : G-0, E-0

Python Implementation

Same idea, except this time the input is more transparent as to what is going on and we're going with a BFS. Initially, all colors are set as NONE, which will also be used to indicate whether it is visited or not. Then for every node, we check if the neighbors have the same color as the parent. Otherwise, map between RED and BLUE depending on the color of the parent.

import enum
import queue
from collections import defaultdict


class Color(enum.Enum):
    NONE = (0,)
    RED = (1,)
    BLUE = 2


def is_bipartite(edges):
    """
    :param edges: List[[char]] implicitly undirectly list of edges
    :return: Boolean
    """

    if not edges:
        return False

    # use colors to determine whether graph is visited
    g = defaultdict(set)
    g_cols = {}

    # build the graph undirected graph
    for (a, b) in edges:
        g[a].add(b)
        g[b].add(a)
        g_cols[a] = Color.NONE
        g_cols[b] = Color.NONE

    # commence the bipartite algorithm
    # check for maximum of 2 color matching
    q = queue.Queue()
    start = edges[0][0]
    g_cols[start] = Color.RED
    q.put(start)

    while not q.empty():
        frnt = q.get()
        col_frnt = g_cols[frnt]

        for neighbor in g[frnt]:
            if g_cols[neighbor] == col_frnt:
                return False
            elif g_cols[neighbor] == Color.NONE:
                q.put(neighbor)
                if col_frnt == Color.RED:
                    g_cols[neighbor] = Color.BLUE
                else:
                    g_cols[neighbor] = Color.RED
    return True


# bipartite graph test
t1 = [['A', 'E'], ['A', 'F'], ['A', 'I'], ['B', 'G'], ['C', 'H'], ['D', 'H']]
t2 = [['A', 'F'], ['A', 'E'], ['A', 'D'], ['B', 'F'], ['B', 'E'], ['B', 'D'], ['C', 'F'], ['C', 'E'], ['C', 'D']]
print(is_bipartite(t1))
print(is_bipartite(t2))

# nonbipartite graph test
t1 = [['A', 'B'], ['A', 'C'], ['B', 'D'], ['B', 'C'], ['C', 'D'], ['C', 'E'], ['D', 'E']]
t2 = [['A', 'B'], ['B', 'C'], ['C', 'A']]
print(is_bipartite(t1))
print(is_bipartite(t2))