White Vertex

In a graph coloring problem, a white vertex refers to a vertex that is uncolored or “white”. Algorithms will aim to color vertices while maintaining certain constraints, leaving some vertices potentially white or uncolored.

Some examples:

Vertex coloring - Each vertex should be colored differently than its neighbors. Some vertices may remain white if no valid color is available.
Bipartite matching - Finding a matching from one partition to the other. Unmatched vertices remain white.
Map coloring - Assign colors to regions with no adjacent same-colored regions. More colors may be needed to color the entire graph.

Java - Bipartite matching:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
boolean hasPerfectMatching(Graph graph) {
  HashSet<Integer> whiteVertices = new HashSet<>();

  for (int u : graph.leftSide) {
    whiteVertices.add(u); 
  }

  while (!whiteVertices.isEmpty()) {
    int u = whiteVertices.iterator().next();
    for (int v : graph.neighbors(u)) {
      if (color(v) == WHITE) {
        color(u, v); // Add edge 
        whiteVertices.remove(u);
        break; 
      }
    }
  }

  return whiteVertices.isEmpty();
}

C++ - Map coloring:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
bool isFourColorable(Graph graph) {
  vector<bool> colored(graph.size(), false); 
 
  for (int u = 0; u < graph.size(); u++) {
    if (!colored[u]) {
      if (!dfsColorNode(graph, u, colored, 1)) {
        // Four colors exceeded
        return false;  
      } 
    }
  }

  return true;
}

Python - Vertex coloring:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def isTwoColourable(graph):

  color = {}
  
  for u in range(len(graph)):  
    if u not in color:
      stack = [u]
      color[u] = WHITE # Initial white vertex

      while stack:
        v = stack.pop()
        for neighbor in graph[v]:
          if neighbor in color:
            if color[neighbor] == color[v]:
              return False
          else:
            color[neighbor] = not color[v]
            stack.append(neighbor)

  return True

Tracking white vertices helps model unprocessed elements in constraints satisfaction and graph problems.

In graph theory, particularly in the context of traversal algorithms like Depth-First Search (DFS), a “white vertex” refers to an unvisited or undiscovered node. When you begin the traversal, all vertices are initially white. As the traversal progresses, vertices change their color to represent their states. A white vertex turns “gray” when it is discovered but not yet fully explored, and “black” when it and its adjacent vertices are completely explored.

In the context of Depth-First Search (DFS) in graph theory, a white vertex is one that has not been visited yet. During DFS, vertices go through three states: white (unvisited), gray (visited but not finished), and black (visited and finished).

Visual Representation:

Let’s consider a simple graph with vertices A, B, C, and D.

 A----B
 |    |
 |    |
 D----C

Initially, all vertices are white (unvisited):

(White) A----B (White)
        |    |
        |    |
(White) D----C (White)

Starting DFS at A, A becomes gray:

(Gray) A----B (White)
        |    |
        |    |
(White) D----C (White)

After visiting B, B becomes gray while A remains gray:

(Gray) A----B (Gray)
        |    |
        |    |
(White) D----C (White)

Eventually, after visiting all neighbors, vertices turn black:

(Black) A----B (Black)
         |    |
         |    |
(Black) D----C (Black)

Key Takeaway:

White vertices are those that have yet to be visited in the DFS process. Understanding the state of each vertex at different stages of DFS helps in graph traversal, path finding, and cycle detection.

Solution

Below are code examples that demonstrate the concept of a white vertex in the context of DFS in Java, C++, and Python.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.*;

public class WhiteVertex {
    private List<Integer>[] graph;
    private int[] color; // 0: white, 1: gray, 2: black

    public WhiteVertex(int vertices) {
        graph = new LinkedList[vertices];
        color = new int[vertices];
        for (int i = 0; i < vertices; ++i) {
            graph[i] = new LinkedList<>();
        }
    }

    public void addEdge(int u, int v) {
        graph[u].add(v);
    }

    public void dfs(int vertex) {
        color[vertex] = 1; // gray
        for (int neighbor : graph[vertex]) {
            if (color[neighbor] == 0) { // white
                dfs(neighbor);
            }
        }
        color[vertex] = 2; // black
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
#include <list>

class WhiteVertex {
private:
    std::vector<std::list<int>> graph;
    std::vector<int> color; // 0: white, 1: gray, 2: black
public:
    WhiteVertex(int vertices) : graph(vertices), color(vertices, 0) {}

    void addEdge(int u, int v) {
        graph[u].push_back(v);
    }

    void dfs(int vertex) {
        color[vertex] = 1; // gray
        for (int neighbor : graph[vertex]) {
            if (color[neighbor] == 0) { // white
                dfs(neighbor);
            }
        }
        color[vertex] = 2; // black
    }
};

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class WhiteVertex:
    def __init__(self, vertices):
        self.graph = [[] for _ in range(vertices)]
        self.color = [0] * vertices  # 0: white, 1: gray, 2: black

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def dfs(self, vertex):
        self.color[vertex] = 1  # gray
        for neighbor in self.graph[vertex]:
            if self.color[neighbor] == 0:  # white
                self.dfs(neighbor)
        self.color[vertex] = 2  # black

Key Takeaways

A white vertex in the DFS context means an undiscovered or unvisited node.
The color array in the code keeps track of the state of each vertex: white, gray, or black.
As DFS proceeds, vertices transition from white to gray and finally to black.