给定一个整数N,它表示顶点的数量。任务是在N个顶点的二部图中找到最大可能的边数。
二分图是一个具有2组顶点的图。
该集合使得同一集合中的顶点之间永不共享边。
如果N = 10,则总共有25条边-
两个集合都将包含5个顶点,并且第一集合的每个顶点都将具有第二集合的每个其他顶点的边
因此,总边将为5 * 5 = 25
当给定集合的每个顶点都具有另一集合的每个其他顶点的边缘时,边缘的数量将最大,即edges = m * n其中m和n是两个集合中的边缘数量
为了最大化边的数量,m必须等于或尽可能接近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