그래프의 에지 커버를 계산하는 C++ 프로그램

그래프의 n개의 정점이 주어지면 작업은 그래프의 가장자리 덮개를 계산하는 것입니다. 에지 커버는 그래프의 모든 정점을 덮는 데 필요한 최소 에지 수를 찾는 것입니다.

n =5

그러면 그래프는 다음과 같을 것입니다 -

따라서 가장자리 덮개는 3입니다.

n이 8인 다른 예를 들어보겠습니다.

가장자리 덮개는 다음과 같습니다.4

예시

Input: n= 5
Output: 3
Input: n= 8
Output: 4

아래에 사용된 접근 방식은 다음과 같습니다. -

• 사용자로부터 입력 받기
• 꼭짓점 개수의 결과를 2.0으로 나누어 상한값을 구합니다.
• 결과를 반환하고 인쇄합니다.

알고리즘

Start
Step 1-> declare function to calculate the edge cover of a graph
   int edge(int n)
      set float val = 0
      set val = ceil(n / 2.0)
      return val
step 2-> In main()
   set int n = 10
   call edge(n)
Stop

예시

#include <bits/stdc++.h>
using namespace std;
// Function to calculates Edge Cover
int edge(int n) {
   float val = 0;
   val = ceil(n / 2.0);
   return val;
}
int main() {
   int n = 10;
   cout<<"minium number of edges required are :"<<edge(n);
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다.

minium number of edges required are :5