Given the number of vertices N of a graph. The task is to determine the Edge cover.
Edge Cover: Minimum number of edges required to cover all vertex is known as Edge Cover.
Examples:
Input : N = 5 Output : 3 Input : N = 4 Output : 2
Example 1: For N = 5 vertices,
Edge Cover is: 3 (Choosing the edges marked in Red, all of the vertices will get covered)
Example 2: For N = 8 vertices,
Edge Cover is: 4 (Choosing the edges marked in Red, all of the vertices will get covered)
Formula:
Edge Cover = ceil (no. of vertices / 2)
Implementation:
C++
// C++ program to find Edge Cover#include <bits/stdc++.h>using namespace std;// Function that calculates Edge Coverint edgeCover(int n){ float result = 0; result = ceil(n / 2.0); return result;}// Driver Codeint main(){ int n = 5; cout << edgeCover(n); return 0;} |
Java
// Java program to find Edge Coverimport java.util.*;import java.lang.*;import java.io.*;class GFG{// Function that calculates Edge Coverstatic int edgeCover(int n){ int result = 0; result = (int)Math.ceil((double)n / 2.0); return result;} // Driver Codepublic static void main(String args[]){ int n = 5; System.out.print(edgeCover(n));}} |
Python3
# Python 3 implementation of the above approach.import math# Function that calculates Edge Cover def edgeCover(n): result = 0 result = math.ceil(n / 2.0) return result # Driver code if __name__ == "__main__" : n = 5 print(int(edgeCover(n)))# this code is contributed by Naman_Garg |
C#
// C# program to find Edge Coverusing System;class GFG{// Function that calculates Edge Coverstatic int edgeCover(int n){ int result = 0; result = (int)Math.Ceiling((double)n / 2.0); return result;}// Driver Codestatic public void Main (){ int n = 5; Console.Write(edgeCover(n));}}// This code is contributed by Raj |
PHP
<?php// PHP program to find Edge Cover// Function that calculates// Edge Coverfunction edgeCover($n){ $result = 0; $result = ceil($n / 2.0); return $result;}// Driver Code$n = 5;echo edgeCover($n);// This code is contributed by Raj?> |
Javascript
<script>// javascript program to find Edge Cover// Function that calculates Edge Cover function edgeCover(n) { var result = 0; result = parseInt( Math.ceil(n / 2.0)); return result; } // Driver Code var n = 5; document.write(edgeCover(n));// This code contributed by gauravrajput1</script> |
3
Time Complexity: O(1), As we are doing constant time operations only.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!


… [Trackback]
[…] There you will find 40047 additional Info to that Topic: geeksforgeeks.org/program-to-calculate-the-edge-cover-of-a-graph/ […]