グラフのエッジカバーを計算する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