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) {
            
        BipartiteGraph task = new BipartiteGraph();
        // Test Case
        task.maxEdges(8); 
        task.maxEdges(11); 
    }
}

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()
{
	BipartiteGraph *task = new BipartiteGraph();
	// Test Case
	task->maxEdges(8);
	task->maxEdges(11);
	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)
	{
		BipartiteGraph task = new BipartiteGraph();
		// Test Case
		task.maxEdges(8);
		task.maxEdges(11);
	}
}

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()
{
	$task = new BipartiteGraph();
	// Test Case
	$task->maxEdges(8);
	$task->maxEdges(11);
}
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()
{
	var task = new BipartiteGraph();
	// Test Case
	task.maxEdges(8);
	task.maxEdges(11);
}
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() :
	task = BipartiteGraph()
	#  Test Case
	task.maxEdges(8)
	task.maxEdges(11)

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() 
	task = BipartiteGraph.new()
	#  Test Case
	task.maxEdges(8)
	task.maxEdges(11)
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
		task.maxEdges(8);
		task.maxEdges(11);
	}
}

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()
{
	let task: BipartiteGraph = BipartiteGraph();
	// Test Case
	task.maxEdges(8);
	task.maxEdges(11);
}
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
{
	val task: BipartiteGraph = BipartiteGraph();
	// Test Case
	task.maxEdges(8);
	task.maxEdges(11);
}

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.

New Comment