การตรวจสอบกราฟดาว (Check for Star Graph)

กราฟดาว (Star Graph) คือกราฟที่มีโหนดกลาง (Center) เชื่อมต่อกับโหนดอื่นๆ ทั้งหมดโดยตรง และโหนดอื่นๆ ไม่เชื่อมต่อกัน

การตรวจสอบ: นับจำนวนโหนดที่มีองศา (Degree) เท่ากับ 1 และจำนวนโหนดที่มีองศาเท่ากับ n-1 (n = จำนวนโหนดทั้งหมด) หากมีโหนดองศา 1 จำนวน n-1 ตัว และโหนดองศา n-1 จำนวน 1 ตัว แสดงว่าเป็นกราฟดาว

การรับค่าและแสดงผล

Input: เมทริกซ์ตyacency
0 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0

Output: It is a star graph.

อัลกอริทึม

checkStarGraph(graph)

Begin
  degOneVert := 0, degNminOneGraph := 0
  
  if กราฟมี 1 โหนด then
    return true ถ้าไม่มี self-loop
  else if กราฟมี 2 โหนด then
    return true ถ้ามีเส้นเชื่อมระหว่างกันเพียงเส้นเดียว
  else
    for ทุกโหนด i do
      degree := 0
      for ทุกโหนด j ที่ติดกับ i do degree++
      done
      
      if degree = 1 then degOneVert++
      else if degree = n-1 then degNminOneGraph++
    done
    
    if degOneVert = n-1 และ degNminOneGraph = 1 then return true
    else return false
  end if
End

ตัวอย่างโค้ด (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;
  
  if (NODE == 1) 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++) {
    int degree = 0;
    for (int j = 0; j < NODE; j++)
      if (graph[i][j]) degree++;
    
    if (degree == 1) degOneVert++;
    else if (degree == NODE-1) degVert++;
  }
  
  return (degOneVert == (NODE-1) && degVert == 1);
}

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

ผลลัพธ์

It is a star graph.