Posted on by Kalkicode
Code Graph

# Maximum number of edges in a bipartite graph

The problem you're addressing is about finding the maximum number of edges that can exist in a bipartite graph given the number of vertices. A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent. The question aims to determine the maximum number of edges that can be present in such a graph.

## Problem Statement and Example

Given a bipartite graph with a certain number of vertices, you want to calculate the maximum number of edges that can exist in this graph while still satisfying the bipartite property. For instance, consider two examples:

1. If there are 8 vertices in the bipartite graph, the maximum number of edges that can exist is 16.
2. If there are 11 vertices in the bipartite graph, the maximum number of edges that can exist is 30.

## Idea to Solve

``(n^2)/4``

To solve this problem, we need to understand that a bipartite graph can be divided into two sets, each containing half of the vertices. The maximum number of edges is achieved when all vertices from one set are connected to all vertices in the other set.

## Pseudocode

``````function maxEdges(vertices)
edges = floor(vertices * vertices / 4)
print "Given vertices:", vertices
print "Max edges     :", edges``````

## Algorithm Explanation

1. Calculate the number of edges using the formula `(vertices * vertices) / 4`. This formula is derived from the fact that if you divide the vertices into two sets of equal size, you can have an edge between any vertex in the first set and any vertex in the second set.
2. Print the given number of vertices and the calculated maximum number of edges.

## Program List

``````// C program for
// Maximum number of edges in a bipartite graph
#include <stdio.h>
#include <math.h>

void maxEdges(int vertices)
{
int edges = floor((vertices *vertices) / 4);
// Display calculated result
printf("\n Given vertices : %d", vertices);
printf("\n Max edges      : %d\n", edges);
}
int main(int argc, char const *argv[])
{
// Test Case
maxEdges(8);
maxEdges(11);
return 0;
}``````

#### Output

`````` Given vertices : 8
Max edges      : 16

Given vertices : 11
Max edges      : 30``````
``````/*
Java program for
Maximum number of edges in a bipartite graph
*/
public class BipartiteGraph
{
public void maxEdges(int vertices)
{
int edges = (int)Math.floor((vertices * vertices) / 4);
// Display calculated result
System.out.print("\n Given vertices : " + vertices );
System.out.print("\n Max edges : " + edges + "\n");
}
public static void main(String[] args) {

// Test Case
}
}``````

#### Output

`````` Given vertices : 8
Max edges : 16

Given vertices : 11
Max edges : 30``````
``````// Include header file
#include <iostream>
#include <math.h>

using namespace std;
/*
C++ program for
Maximum number of edges in a bipartite graph
*/
class BipartiteGraph
{
public: void maxEdges(int vertices)
{
int edges = (int) floor((vertices *vertices) / 4);
// Display calculated result
cout << "\n Given vertices : " << vertices;
cout << "\n Max edges : " << edges << "\n";
}
};
int main()
{
// Test Case
return 0;
}``````

#### Output

`````` Given vertices : 8
Max edges : 16

Given vertices : 11
Max edges : 30``````
``````// Include namespace system
using System;
/*
Csharp program for
Maximum number of edges in a bipartite graph
*/
public class BipartiteGraph
{
public void maxEdges(int vertices)
{
int edges = (int) Math.Floor((double)(vertices * vertices) / 4);
// Display calculated result
Console.Write("\n Given vertices : " + vertices);
Console.Write("\n Max edges : " + edges + "\n");
}
public static void Main(String[] args)
{
// Test Case
}
}``````

#### Output

`````` Given vertices : 8
Max edges : 16

Given vertices : 11
Max edges : 30``````
``````package main
import "math"
import "fmt"
/*
Go program for
Maximum number of edges in a bipartite graph
*/

func maxEdges(vertices int) {
var edges  =  math.Floor((float64)(vertices * vertices) / 4)
// Display calculated result
fmt.Print("\n Given vertices : ", vertices)
fmt.Print("\n Max edges : ", edges, "\n")
}
func main() {

// Test Case
maxEdges(8)
maxEdges(11)
}``````

#### Output

`````` Given vertices : 8
Max edges : 16

Given vertices : 11
Max edges : 30``````
``````<?php
/*
Php program for
Maximum number of edges in a bipartite graph
*/
class BipartiteGraph
{
public	function maxEdges(\$vertices)
{
\$edges = (int) floor(((\$vertices * \$vertices) / 4));
// Display calculated result
echo("\n Given vertices : ".\$vertices);
echo("\n Max edges : ".\$edges."\n");
}
}

function main()
{
// Test Case
}
main();``````

#### Output

`````` Given vertices : 8
Max edges : 16

Given vertices : 11
Max edges : 30``````
``````/*
Node JS program for
Maximum number of edges in a bipartite graph
*/
class BipartiteGraph
{
maxEdges(vertices)
{
var edges = Math.floor((vertices * vertices) / 4);
// Display calculated result
process.stdout.write("\n Given vertices : " + vertices);
process.stdout.write("\n Max edges : " + edges + "\n");
}
}

function main()
{
// Test Case
}
main();``````

#### Output

`````` Given vertices : 8
Max edges : 16

Given vertices : 11
Max edges : 30``````
``````import math
#  Python 3 program for
#  Maximum number of edges in a bipartite graph
class BipartiteGraph :
def maxEdges(self, vertices) :
edges = math.floor((vertices * vertices) / 4)
#  Display calculated result
print("\n Given vertices : ", vertices, end = "")
print("\n Max edges : ", edges )

def main() :
#  Test Case

if __name__ == "__main__": main()``````

#### Output

`````` Given vertices :  8
Max edges :  16

Given vertices :  11
Max edges :  30``````
``````#  Ruby program for
#  Maximum number of edges in a bipartite graph
class BipartiteGraph
def maxEdges(vertices)
edges = ((vertices * vertices) / 4). floor()
#  Display calculated result
print("\n Given vertices : ", vertices)
print("\n Max edges : ", edges ,"\n")
end

end

def main()
#  Test Case
end

main()``````

#### Output

`````` Given vertices : 8
Max edges : 16

Given vertices : 11
Max edges : 30
``````
``````/*
Scala program for
Maximum number of edges in a bipartite graph
*/
class BipartiteGraph()
{
def maxEdges(vertices: Int): Unit = {
var edges: Int = Math.floor((vertices * vertices) / 4).toInt;
// Display calculated result
print("\n Given vertices : " + vertices);
print("\n Max edges : " + edges + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BipartiteGraph = new BipartiteGraph();
// Test Case
}
}``````

#### Output

`````` Given vertices : 8
Max edges : 16

Given vertices : 11
Max edges : 30``````
``````import Foundation;
/*
Swift 4 program for
Maximum number of edges in a bipartite graph
*/
class BipartiteGraph
{
func maxEdges(_ vertices: Int)
{
let edges: Int = Int(floor(Double(vertices * vertices) / 4));
// Display calculated result
print("\n Given vertices : ", vertices, terminator: "");
print("\n Max edges : ", edges );
}
}
func main()
{
// Test Case
}
main();``````

#### Output

`````` Given vertices :  8
Max edges :  16

Given vertices :  11
Max edges :  30``````
``````/*
Kotlin program for
Maximum number of edges in a bipartite graph
*/
class BipartiteGraph
{
fun maxEdges(vertices: Int): Unit
{
val edges: Int = Math.floor(
((vertices * vertices) / 4).toDouble()
).toInt();
// Display calculated result
print("\n Given vertices : " + vertices);
print("\n Max edges : " + edges + "\n");
}
}
fun main(args: Array < String > ): Unit
{
// Test Case
}``````

#### Output

`````` Given vertices : 8
Max edges : 16

Given vertices : 11
Max edges : 30``````

## Resultant Output Explanation

It calculates the maximum number of edges in a bipartite graph given the number of vertices using the formula and prints the results for the provided test cases.

## Time Complexity

The time complexity of the algorithm is O(1), which means it runs in constant time regardless of the input size. The calculation of the maximum number of edges is a simple mathematical operation that doesn't depend on the number of vertices.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post