Tutorialspoint.dev

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 –



  1. Tree is connected and has no cycles while graphs can have cycles.
  2. Tree has exactly n-1 edges while there is no such constraint for graph.
  3. 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) ore not.

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 [tabby title="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
?>


Output:

Tree

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

tags:

Graph Graph

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter