Kiểm tra đồ thị hai phần (Bipartite Graph)

Một đồ thị được gọi là đồ thị hai phần (bipartite) khi các đỉnh của đồ thị đó có thể chia thành hai tập hợp độc lập sao cho mọi cạnh trong đồ thị hoặc bắt đầu từ tập thứ nhất và kết thúc ở tập thứ hai, hoặc bắt đầu từ tập thứ hai và kết nối đến tập thứ nhất. Nói cách khác, không có cạnh nào nằm trong cùng một tập hợp.

Kiểm tra đồ thị hai phần có thể thực hiện bằng cách tô màu đỉnh. Khi một đỉnh thuộc cùng một tập hợp, nó có cùng màu, với tập kia thì màu sẽ thay đổi.

Đầu vào và Đầu ra

Đầu vào: Ma trận kề.
0 1 1 1 0 0
1 0 0 1 1 0
1 0 0 1 0 1
1 1 1 0 1 1
0 1 0 1 0 1
0 0 1 1 1 0
Đầu ra: Đồ thị là hai phần.

Thuật toán

isBipartite(source)
Đầu vào: Đỉnh nguồn.
Đầu ra: True khi đồ thị là hai phần.
Bắt đầu
  định nghĩa hàng đợi rỗng qu, và danh sách màu colorArray
  ban đầu không nút nào được tô màu
  tô đỉnh nguồn là màu đỏ
  thêm nguồn vào qu
  khi qu không rỗng, thực hiện
    lấy phần tử từ qu gán vào u
    nếu có khuyên (self-loop) thì
      trả về false
    với mọi đỉnh v kết nối với u, thực hiện
      nếu v chưa có màu thì
        nếu colorArray[u] = đỏ thì
          colorArray[v] := xanh
        ngược lại nếu colorArray[u] = xanh thì
          colorArray[v] := đỏ
        thêm v vào hàng đợi
      ngược lại nếu colorArray[v] = colorArray[u] thì
        trả về false
    kết thúc
  kết thúc
  trả về true
Kết thúc

Ví dụ (C++)

#include <iostream>
#include <string>
#include <queue>
#define NODE 6
using namespace std;

/* int graph[NODE][NODE] = {
  {0, 1, 1, 1, 0, 0},
  {1, 0, 0, 1, 1, 0},
  {1, 0, 0, 1, 0, 1},
  {1, 1, 1, 0, 1, 1},
  {0, 1, 0, 1, 0, 1},
  {0, 0, 1, 1, 1, 0}
}; */

int graph[NODE][NODE] = {
  {0, 1, 0, 0, 0, 1},
  {1, 0, 1, 0, 0, 0},
  {0, 1, 0, 1, 0, 0},
  {0, 0, 1, 0, 1, 0},
  {0, 0, 0, 1, 0, 1},
  {1, 0, 0, 0, 1, 0}
};

bool isBipartite(int source) {
  queue<int> qu;
  string colorArray[NODE];
  for(int i = 0; i < NODE; i++)
    colorArray[i] = "No Color"; // ban đầu không màu nào được đặt cho tất cả đỉnh
  
  colorArray[source] = "Red"; // gán đỏ cho đỉnh nguồn
  qu.push(source); // thêm nguồn vào hàng đợi
  
  while(!qu.empty()) {
    int u = qu.front();
    qu.pop();
    
    if(graph[u][u] == 1) // có khuyên
      return false;
    
    for(int v = 0; v < NODE; v++) {
      if(graph[u][v] != 0 && colorArray[v] == "No Color") {
        if(colorArray[u] == "Red") // gán danh sách kề với màu thay thế
          colorArray[v] = "Blue";
        else if(colorArray[u] == "Blue")
          colorArray[v] = "Red";
        qu.push(v); // nút kề mới thêm vào hàng đợi
      } else if(graph[u][v] != 0 && colorArray[v] == colorArray[u]) {
        return false; // khi u và đỉnh kề cùng màu
      }
    }
  }
  return true;
}

int main() {
  bool check;
  check = isBipartite(0);
  if(check)
    cout << "The graph is bipartite." << endl;
  else
    cout << "The graph is not bipartite." << endl;
}

Đầu ra

The graph is bipartite.