C++에서 휠 그래프의 지름, 주기 및 모서리를 찾는 프로그램

이 문제에서는 휠 그래프의 정점 수를 나타내는 숫자가 제공됩니다. 우리의 임무는 C++에서 휠 그래프의 지름, 주기 및 모서리를 찾는 프로그램을 만드는 것입니다. .

문제 설명 − 여기에서 n개의 꼭짓점을 갖는 Wheel Graph의 사이클 수, 모서리 수, 지름을 찾아야 합니다.

먼저 Wheel Graph에 대한 몇 가지 기본 사항을 이해하겠습니다 -

새로운 정점을 추가하여 사이클 그래프 Cn-1에서 휠 그래프를 얻습니다. 이 새로운 정점은 Cn의 모든 정점에 연결된 허브라고 합니다.

7개의 꼭짓점이 있는 휠 그래프의 예.

휠 그래프의 지름 는 정점에서 다른 정점으로 이동하기 위해 덮어야 하는 가장자리의 수입니다. 위의 휠 그래프의 경우 직경 2

아니요. 휠 그래프의 주기 주어진 그래프에서 닫을 수 있는 총 사이클 수입니다. 위의 휠 그래프의 경우 no. 주기는 31입니다.

아니요. 휠 그래프의 가장자리 모든 정점을 연결하는 가장자리의 수입니다. 위의 Wheel Graph의 경우 edge의 개수는 12개입니다.

해결 방법

이 문제를 해결하기 위해 그래프 이론에서 주어진 직접 공식을 사용하여 휠 그래프에 필요한 값을 찾습니다.

공식은,

휠 그래프의 지름 ​​=

1, if vertices = 4, else 2.

아니요. 휠 그래프의 주기 =

(No. of vertices )^2 - (3 * (No. of vertices -1) )

아니요. 휠 그래프의 가장자리 수 =

2 * (No. of vertices - 1)

우리 솔루션의 작동을 설명하는 프로그램

예

#include <iostream>
#include <math.h>
using namespace std;
void calcValuesWheelGraph(int V){
   // Calculating the Diameter
   if(V == 4){
      cout<<"The Diameter of the Wheel Graph is 1 "<<endl;
   }
   else {
      cout<<"The Diameter of the Wheel Graph is 2 "<<endl;
   }
   // Calculating the no. of cycles
   cout<<"The number of cycles of the Wheel Graph is "<<(pow(V, 2) - (3 * (V-1)))<<endl;
   // Calculating the no. of Edges
   cout<<"The number of Edges of the Wheel Graph is "<<(2 * (V-1))<<endl;
}
int main(){
   int V = 9;
   calcValuesWheelGraph(V);
   return 0;
}

출력

The Diameter of the Wheel Graph is 2
The number of cycles of the Wheel Graph is 57
The number of Edges of the Wheel Graph is 16