C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++の2部グラフのエッジの最大数

問題の説明

頂点の数を表す整数Nが与えられます。タスクは、N個の頂点の2部グラフで可能な最大数のエッジを見つけることです。

2部グラフ

  • 2部グラフは、2セットの頂点を持つグラフです。
  • このセットは、同じセット内の頂点がそれらの間でエッジを共有しないようになっています。

例

N =10の場合、合計25個のエッジがあります-

  • 両方のセットに5つの頂点が含まれ、最初のセットのすべての頂点には、2番目のセットの他のすべての頂点へのエッジがあります
  • したがって、エッジの合計は5 * 5=25になります

アルゴリズム

  • エッジの数は、特定のセットのすべての頂点が他のセットの他のすべての頂点に対してエッジを持っている場合に最大になります。つまり、edges =m * nここで、mとnは両方のセットのエッジの数です
    • >
  • エッジの数を最大化するには、mがnと等しいか、可能な限りnに近い必要があります
  • したがって、エッジの最大数は次の式で計算できます-

（n * n）/ 4

例

#include <bits/stdc++.h>
using namespace std;
int getMaxEdges(int n) {
   return floor((n * n) / 4);
}
int main() {
   int n = 7;
   cout << "Maximum edges = " << getMaxEdges(n) << endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Maximum edges = 12

  1. 最大ベンド数のC++パス長

    二分木が与えられる問題を解決するため。次に、曲がりの数が最大のパスを見つける必要があります。つまり、パスの方向が左から右に、またはその逆に変化する場合、たとえば、曲がりが考慮されます 入力- 出力- 6 このアプローチでは、ツリーをトラバースして、以前の動きを追跡します。方向が変わった場合は、曲げカウントを更新するだけで、最大値が見つかります。 解決策を見つけるためのアプローチ このアプローチでは、すべてのパスをトラバースし、回答を更新するベンドの最大数を見つけます。 例 #include <bits/stdc++.h> using namespace std; s

  2. C++の無向グラフのエッジの数を数えます

    与えられたタスクは、無向グラフのエッジの数を数えることです。無向グラフは、すべてのエッジが双方向であるグラフを形成するために互いに接続されている頂点のセットです。無向グラフは、あるノードから別の接続されたノードへと任意の方向に移動できます。 以下は、無向グラフの視覚的表現です。 ここで、問題に応じて、無向グラフのエッジの数を見つける必要があります。 グラフのエッジは、2つの頂点が結合されている線です。 入力 − insert(graph_list, 0, 1); insert(graph_list, 0, 2); insert(graph_list, 1, 2); insert