Dado el número de vértices N de un gráfico. La tarea es determinar la cobertura de Edge.
Cobertura de borde: la cantidad mínima de borde requerida para cubrir todos los vértices se conoce como cobertura de borde.
Ejemplos:
Input : N = 5 Output : 3 Input : N = 4 Output : 2
Ejemplo 1: Para N = 5 vértices,
Edge Cover es: 3 (Al elegir los bordes marcados en rojo, todos los vértices se cubrirán)
Ejemplo 2: Para N = 8 vértices,
Edge Cover es: 4 (Al elegir los bordes marcados en rojo, todos los vértices se cubrirán)
Fórmula:
Edge Cover = ceil (no. of vertices / 2)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find Edge Cover #include <bits/stdc++.h> using namespace std; // Function that calculates Edge Cover int edgeCover(int n) { float result = 0; result = ceil(n / 2.0); return result; } // Driver Code int main() { int n = 5; cout << edgeCover(n); return 0; }
Java
// Java program to find Edge Cover import java.util.*; import java.lang.*; import java.io.*; class GFG{ // Function that calculates Edge Cover static int edgeCover(int n) { int result = 0; result = (int)Math.ceil((double)n / 2.0); return result; } // Driver Code public 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 Cover using System; class GFG { // Function that calculates Edge Cover static int edgeCover(int n) { int result = 0; result = (int)Math.Ceiling((double)n / 2.0); return result; } // Driver Code static 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 Cover function 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>
Producción:
3
Publicación traducida automáticamente
Artículo escrito por Naman_Garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA