Check whether given degrees of vertices represent a Graph or Tree
Given the number of vertices and the degree of each vertex where vertex numbers are 1, 2, 3,…n. The task is to identify whether it is a graph or a tree. It may be assumed that the graph is Connected.
Examples:
Input : 5 2 3 1 1 1 Output : Tree Explanation : The input array indicates that vertex one has degree 2, vertex two has degree 3, vertices 3, 4 and 5 have degree 1. 1 / \ 2 3 / \ 4 5 Input : 3 2 2 2 Output : Graph 1 / \ 2 - 3
The degree of a vertex is given by the number of edges incident or leaving from it. This can simply be done using the properties of trees like –
- Tree is connected and has no cycles while graphs can have cycles.
- Tree has exactly n-1 edges while there is no such constraint for graph.
- It is given that the input graph is connected. We need at least n-1 edges to connect n nodes.
If we take the sum of all the degrees, each edge will be counted twice. Hence, for a tree with n vertices and n – 1 edges, sum of all degrees should be 2 * (n – 1). Please refer Handshaking Lemma for details. So basically we need to check if sum of all degrees is 2*(n-1) or not.
Implementation:
C++
// C++ program to check whether input degree // sequence is graph or tree #include<bits/stdc++.h> using namespace std; // Function returns true for tree // false for graph bool check( int degree[], int n) { // Find sum of all degrees int deg_sum = 0; for ( int i = 0; i < n; i++) deg_sum += degree[i]; // Graph is tree if sum is equal to 2(n-1) return (2*(n-1) == deg_sum); } // Driver program to test above function int main() { int n = 5; int degree[] = {2, 3, 1, 1, 1}; if (check(degree, n)) cout << "Tree" ; else cout << "Graph" ; return 0; } |
Java
// Java program to check whether input degree // sequence is graph or tree class GFG { // Function returns true for tree // false for graph static boolean check( int degree[], int n) { // Find sum of all degrees int deg_sum = 0 ; for ( int i = 0 ; i < n; i++) { deg_sum += degree[i]; } // Graph is tree if sum is equal to 2(n-1) return ( 2 * (n - 1 ) == deg_sum); } // Driver code public static void main(String[] args) { int n = 5 ; int degree[] = { 2 , 3 , 1 , 1 , 1 }; if (check(degree, n)) { System.out.println( "Tree" ); } else { System.out.println( "Graph" ); } } } // This code has been contributed // by 29AjayKumar |
Python
# Python program to check whether input degree # sequence is graph or tree def check(degree, n): # Find sum of all degrees deg_sum = sum (degree) # It is tree if sum is equal to 2(n-1) if ( 2 * (n - 1 ) = = deg_sum): return True else : return False #main n = 5 degree = [ 2 , 3 , 1 , 1 , 1 ]; if (check(degree, n)): print "Tree" else : print "Graph" |
C#
// C# program to check whether input // degree sequence is graph or tree using System; class GFG { // Function returns true for tree // false for graph static bool check( int [] degree, int n) { // Find sum of all degrees int deg_sum = 0; for ( int i = 0; i < n; i++) { deg_sum += degree[i]; } // Graph is tree if sum is // equal to 2(n-1) return (2 * (n - 1) == deg_sum); } // Driver code public static void Main() { int n = 5; int [] degree = {2, 3, 1, 1, 1}; if (check(degree, n)) { Console.WriteLine( "Tree" ); } else { Console.WriteLine( "Graph" ); } } } // This code has been contributed // by Akanksha Rai |
PHP
<?php // PHP program to check whether input // degree sequence is graph or tree // Function returns true for tree // false for graph function check(& $degree , $n ) { // Find sum of all degrees $deg_sum = 0; for ( $i = 0; $i < $n ; $i ++) $deg_sum += $degree [ $i ]; // Graph is tree if sum is // equal to 2(n-1) return (2 * ( $n - 1) == $deg_sum ); } // Driver Code $n = 5; $degree = array (2, 3, 1, 1, 1); if (check( $degree , $n )) echo "Tree" ; else echo "Graph" ; // This code is contributed by // Shivi_Aggarwal ?> |
Javascript
// JS program to check whether input degree // sequence is graph or tree // Function returns true for tree // false for graph function check(degree, n) { // Find sum of all degrees const deg_sum = degree.reduce((a, b) => a + b, 0); // Graph is tree if sum is equal to 2(n-1) if (2 * (n - 1) === deg_sum) { return true ; } else { return false ; } } // Driver code const n = 5; const degree = [2, 3, 1, 1, 1]; if (check(degree, n)) { console.log( "Tree" ); } else { console.log( "Graph" ); } |
Output
Tree
Time Complexity:O(N)
Space Complexity:O(1),since no extra space being used.