Đồ thị Biconnected (Biconnected Graph)

Giới thiệu

Đồ thị vô hướng gọi là biconnected (hai liên thông đỉnh) nếu giữa hai đỉnh bất kỳ tồn tại hai đường đi không chia sẻ đỉnh trung gian. Tức là mọi cặp đỉnh đều nằm trên một chu trình.

Đồ thị G là biconnected khi: (1) liên thông, (2) không có điểm khớp (articulation point / cut vertex).

Dùng DFS để tìm điểm khớp và kiểm tra liên thông.

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

Đầu vào: Ma trận kề:
0 1 1 1 0
1 0 1 0 0
1 1 0 0 0
1 0 0 0 1
0 0 0 1 0
Đầu ra: The Graph is a biconnected graph.

Thuật toán

isArticulation(start, visited, disc, low, parent)

Đầu vào: Đỉnh bắt đầu, mảng visited, disc, low, parent.

Đầu ra: True nếu tìm thấy điểm khớp.

Begin
  time := 0 (static)
  dfsChild := 0
  đánh dấu start đã thăm
  disc[start] := low[start] := ++time
  với mọi đỉnh v trong G làm:
    nếu có cạnh (start, v) thì
      nếu v chưa thăm thì
        tăng dfsChild
        parent[v] := start
        nếu isArticulation(v, visited, disc, low, parent) thì return true
        low[start] := min(low[start], low[v])
        nếu parent[start] = ∅ VÀ dfsChild > 1 thì return true
        nếu parent[start] ≠ ∅ VÀ low[v] >= disc[start] thì return true
      ngược lại nếu v ≠ parent[start] thì
        low[start] := min(low[start], disc[v])
  done
  return false
End

isBiconnected(graph)

Begin
  đặt tất cả đỉnh chưa thăm, parent = ∅
  nếu isArticulation(0, visited, disc, low, parent) thì return false
  với mỗi nút i làm: nếu i chưa thăm thì return false
  return true
End

Ví dụ (C++)

#include <iostream>
#define NODE 5
using namespace std;

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

int min(int a, int b) { return (a < b) ? a : b; }

bool isArticulation(int start, bool visited[], int disc[], int low[], int parent[]) {
  static int time = 0;
  int dfsChild = 0;
  visited[start] = true;
  disc[start] = low[start] = ++time;
  for(int v = 0; v < NODE; v++) {
    if(graph[start][v]) {
      if(!visited[v]) {
        dfsChild++;
        parent[v] = start;
        if(isArticulation(v, visited, disc, low, parent)) return true;
        low[start] = min(low[start], low[v]);
        if(parent[start] == -1 && dfsChild > 1) return true;
        if(parent[start] != -1 && low[v] >= disc[start]) return true;
      } else if(v != parent[start]) {
        low[start] = min(low[start], disc[v]);
      }
    }
  }
  return false;
}

bool isBiConnected() {
  bool *vis = new bool[NODE];
  int *disc = new int[NODE], *low = new int[NODE], *parent = new int[NODE];
  for(int i = 0; i < NODE; i++) { vis[i] = false; parent[i] = -1; }
  if(isArticulation(0, vis, disc, low, parent)) return false;
  for(int i = 0; i < NODE; i++) if(!vis[i]) return false;
  return true;
}

int main() {
  if(isBiConnected()) cout << "The Graph is a biconnected graph.";
  else cout << "The Graph is not a biconnected graph.";
}

Kết quả đầu ra

The Graph is a biconnected graph.