C++のグラフの最大および最小の孤立した頂点

エッジの数Noeと頂点の数が11月に与えられます。目標は、エッジがなく、頂点が数えられないようなグラフで可能な、孤立した頂点の最小数と最大数を見つけることです。

孤立した頂点とは、エッジが接続されていない頂点です。

• 最小の孤立した頂点の場合

すべてのエッジが分離されていることを確認します。 （2つのエッジに共通の頂点はありません）各エッジに必要な頂点は2つだけです。だから、

分離されていない頂点の数=2*いいえ。エッジの

孤立した頂点の数=合計頂点-孤立していない頂点の数。

いいえの場合。頂点の数は<=2*noです。エッジの場合、すべての頂点にエッジが接続されていることを意味します。孤立した頂点の数は0です。

• 最大の孤立した頂点の場合

このために、すべてのエッジが最小の頂点で接続されるようにポリゴンを作成しようとします。これは、各頂点ペアがそれらの間に対角線を持つようなポリゴンがある場合に可能です。

与えられた5つの頂点と6つのエッジの場合、正方形は2つの対角線を持つ6つのエッジを持つポリゴンであるため、4つの頂点のみが占有されます。 1つの頂点が孤立し、最大になります。

n辺のポリゴンの1つの頂点から別の頂点への対角線の数はn*（n-3）/2です。合計エッジ=n*（n-1）/ 2

入力

No. of vertices 5, edges 6

出力

Minimum isolated vertices 0. Maximum isolated vertices 1.

説明

上図のように。

入力 −いいえ。頂点2のエッジ=1

出力 −最小孤立頂点0。最大孤立頂点0。

説明 −少なくとも2つの頂点の間にエッジが形成されます。

以下のプログラムで使用されているアプローチは次のとおりです

• 整数noeとnovにはnoが含まれます。エッジと頂点の。

• 関数findisolatedvertices（int v、int e）は、エッジと頂点をパラメーターとして受け取り、可能な最小および最大の分離頂点を出力します。

• いいえの場合。頂点の数は<=2* eであり、孤立した頂点がないことを意味します。それ以外の非分離頂点は2*e（最大）であるため、最小分離はv-2*eになります。

• 最大孤立頂点を計算するには、i=1からnoまで開始します。頂点の数（i *（i --1）/ 2> =e）が壊れた場合、eエッジにはi個の頂点だけで十分です。

• 可能な限り最大の孤立した頂点を格納します。

例

#include <bits/stdc++.h>
using namespace std;
void findisolatedvertices(int v, int e){
   //one edge has 2 vertices
   if (v <= 2 * e) //means all veritces have a connected edge
      cout << "Minimum no. of isolated vertices: " << 0 << endl;
   else {
      int niso=2*e; //maximum non isolated vertices
      cout << "Minimum no. of isolated vertices: " << v - niso << endl;
   }
   // To find out maximum number of isolated
   // vertices
   // Loop to find out value of number of
   // vertices that are connected
   int i;
   for (i = 1; i <= v; i++) {
      if (i * (i - 1) / 2 >= e)
         break;
   }
   cout <<endl<< "Maximum no. of isolated vertices: " <<v-i;
}
int main(){
   // Number of vertices
   int nov = 5;
   // Number of edges
   int noe = 2;
   // Calling the function to maximum and
   // minimum number of isolated vertices
   findisolatedvertices(nov, noe);
   return 0;
}

出力

Minimum no. of isolated vertices: 1
Maximum no. of isolated vertices: 2