Kiểm tra đồ thị sao (Star Graph)

Một đồ thị được cho; ta phải kiểm tra xem đồ thị đã cho có phải là đồ thị sao (star graph) hay không.

Bằng cách duyệt đồ thị, ta phải tìm số lượng đỉnh có bậc là 1, và số lượng đỉnh có bậc là n-1 (n là số đỉnh trong đồ thị cho trước). Khi số đỉnh bậc 1 là n-1 và số đỉnh bậc (n-1) là 1, thì đó là đồ thị sao.

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

Đầu vào: Ma trận kề:
0 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0
Đầu ra: Đây là đồ thị sao.

Thuật toán

checkStarGraph(graph)
Đầu vào: Đồ thị cho trước.
Đầu ra: True khi đồ thị là đồ thị sao.
Bắt đầu
  degOneVert := 0 và degNminOneGraph := 0
  nếu đồ thị chỉ có một đỉnh thì
    trả về true, nếu không có khuyên
  ngược lại nếu đồ thị có hai đỉnh thì
    trả về true nếu chỉ có một cạnh giữa hai đỉnh
  ngược lại
    với mọi đỉnh i trong đồ thị, thực hiện
      degree := 0
      với mọi đỉnh j kề với i, thực hiện
        degree := degree + 1
      kết thúc
      nếu degree = 1 thì
        degOneVert := degOneVert + 1
      ngược lại nếu degree = n-1 thì
        degNminOneGraph := degNminOneGraph + 1
    kết thúc
  nếu degOneVert = n-1 và degNminOneGraph = 1 thì
    trả về true
  ngược lại trả về false
Kết thúc

Ví dụ (C++)

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

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

bool checkStarGraph() {
  int degOneVert = 0, degVert = 0;
  // ban đầu đỉnh bậc 1 và đỉnh bậc n-1 đều là 0
  
  if (NODE == 1) // khi chỉ có một nút
    return (graph[0][0] == 0);
  
  if (NODE == 2)
    return (graph[0][0] == 0 && graph[0][1] == 1 && graph[1][0] == 1 && graph[1][1] == 0);
  
  for (int i = 0; i < NODE; i++) {
    // cho đồ thị nhiều hơn 2 nút
    int degree = 0;
    for (int j = 0; j < NODE; j++) // đếm bậc cho đỉnh i
      if (graph[i][j])
        degree++;
    if (degree == 1)
      degOneVert++;
    else if (degree == NODE-1)
      degVert++;
  }
  
  // khi chỉ có một đỉnh bậc n-1, và tất cả đỉnh khác bậc 1, đó là đồ thị sao
  return (degOneVert == (NODE-1) && degVert == 1);
}

int main() {
  if(checkStarGraph())
    cout << "It is a star graph.";
  else
    cout << "It is not a star graph.";
}

Đầu ra

It is a star graph.