একটি গ্রাফ দেওয়া হয়েছে; আমাদের প্রদত্ত গ্রাফটি একটি তারকা গ্রাফ কিনা তা পরীক্ষা করতে হবে।
গ্রাফটি অতিক্রম করে, আমাদেরকে খুঁজে বের করতে হবে শীর্ষবিন্দুর সংখ্যার ডিগ্রি এক আছে এবং শীর্ষবিন্দুর সংখ্যা, যার ডিগ্রি n-1। (এখানে n প্রদত্ত গ্রাফে শীর্ষবিন্দুর সংখ্যা)। যখন ডিগ্রী 1 এর সাথে শীর্ষবিন্দুর সংখ্যা n-1 এবং একটি ডিগ্রী (n-1) সহ কয়েকটি শীর্ষবিন্দু এক হয়, তখন এটি একটি তারার গ্রাফ।
ইনপুট এবং আউটপুট
Input: The adjacency matrix: 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 and degNminOneGraph := 0 if graph has only one vertex, then return true, if there is no self-loop else if graph has two vertices, then return true if there is only one vertex between two vertices else for all vertices i in the graph, do degree := 0 for all vertices j, adjacent with i, do degree := degree + 1 done if degree = 1, then degOneVert := degOneVert + 1 else if degree = n-1, then degNminOneGraph := degNminOneGraph + 1 done if degOneVert = n-1, and degNminOneGraph = 1, then return true otherwise return false End
উদাহরণ
#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; //initially vertex with degree 1 and with degree n - 1 are 0
if (NODE == 1) //when there is only one node
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++) { //for graph more than 2
int degree = 0;
for (int j = 0; j < NODE; j++) //count degree for vertex i
if (graph[i][j])
degree++;
if (degree == 1)
degOneVert++;
else if (degree == NODE-1)
degVert++;
}
//when only vertex of degree n-1, and all other vertex of degree 1, it is a star graph
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.
