একটি গ্রাফ দেওয়া আছে; আমাদের কাজ হলো যাচাই করা যে প্রদত্ত গ্রাফটি একটি স্টার গ্রাফ কিনা।
গ্রাফটিকে ট্রাভার্স করে, আমাদের ডিগ্রি ১ دار যেসব ভার্টেক্স এবং ডিগ্রি n-1 دار যেসব ভার্টেক্স তাদের সংখ্যা বের করতে হবে। (এখানে n হলো প্রদত্ত গ্রাফের ভার্টেক্সের সংখ্যা)। যখন ডিগ্রি ১ دار ভার্টেক্সের সংখ্যা n-1 এবং ডিগ্রি (n-1) دار ভার্টেক্সের সংখ্যা ১ হয়, তখন সেটি একটি স্টার গ্রাফ।
ইনপুট এবং আউটপুট
ইনপুট: অ্যাডজেসেন্সি ম্যাট্রিক্স: 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 আউটপুট: এটি একটি স্টার গ্রাফ।
এলগরিদম
checkStarGraph(graph)
ইনপুট: প্রদত্ত গ্রাফ।
আউটপুট: গ্রাফটি স্টার গ্রাফ হলে true।
শুরু
degOneVert := 0 এবং degNminOneGraph := 0
যদি গ্রাফে শুধু একটি ভার্টেক্স থাকে, তবে
return true, যদি কোনো সেলফ-লুপ না থাকে
অন্যথায় যদি গ্রাফে দুটি ভার্টেক্স থাকে, তবে
return true যদি দুটি ভার্টেক্সের মধ্যে শুধু একটি এজ থাকে
অন্যথায়
গ্রাফের সব ভার্টেক্স i এর জন্য, করুন
degree := 0
i-র সাথে সন্নিহিত সব ভার্টেক্স j এর জন্য, করুন
degree := degree + 1
শেষ লুপ
যদি degree = 1, তবে
degOneVert := degOneVert + 1
অন্যথায় যদি degree = n-1, তবে
degNminOneGraph := degNminOneGraph + 1
শেষ লুপ
যদি degOneVert = n-1, এবং degNminOneGraph = 1, তবে
return true
অন্যথায় return false
শেষ
উদাহরণ (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;
// প্রাথমিকভাবে ডিগ্রি ১ এবং ডিগ্রি n-1 دار ভার্টেক্স ০
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++) // ভার্টেক্স i-এর ডিগ্রি গণনা করুন
if (graph[i][j])
degree++;
if (degree == 1)
degOneVert++;
else if (degree == NODE-1)
degVert++;
}
// যখন শুধু একটি ভার্টেক্স ডিগ্রি n-1, এবং বাকি সব ডিগ্রি ১, তবে এটি একটি স্টার গ্রাফ
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.
