Số cạnh tối đa trong biểu đồ Bipartite trong C ++

Tuyên bố vấn đề

Cho một số nguyên N đại diện cho số Đỉnh. Nhiệm vụ là tìm số cạnh tối đa có thể có trong đồ thị Bipartite gồm N đỉnh.

Biểu đồ lưỡng cực

• Biểu đồ hai bên là biểu đồ có 2 tập hợp các khe.
• Tập hợp sao cho các đỉnh trong cùng một tập hợp sẽ không bao giờ có chung một cạnh giữa chúng.

Ví dụ

Nếu N =10 thì sẽ có tổng số 25 cạnh -

• Cả hai tập hợp sẽ chứa 5 đỉnh và mọi đỉnh của tập hợp đầu tiên sẽ có một cạnh đối với mọi đỉnh khác của tập hợp thứ hai
• Do đó, tổng số cạnh sẽ là 5 * 5 =25

Thuật toán

• Số cạnh sẽ là lớn nhất khi mọi đỉnh của một tập hợp đã cho đều có cạnh đối với mọi đỉnh khác của tập hợp khác, tức là các cạnh =m * n trong đó m và n là số cạnh trong cả hai tập
• để số cạnh lớn nhất, m phải bằng hoặc gần bằng n nhất có thể
• Do đó, số lượng cạnh tối đa có thể được tính bằng công thức -

(n * n) / 4

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Maximum edges = 12