Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.1.1.
Input 
2.1.2.
Output
2.1.3.
Input 
2.1.4.
Output
2.2.
Explanation
3.
Approach
4.
Implementation in C++
4.1.
Output
5.
Implementation in Java
5.1.
Output
6.
Implementation in Python
6.1.
Output
7.
Complexity
7.1.
Time Complexity
7.2.
Space complexity
8.
Frequently Asked Questions
8.1.
What specific point distinguishes a tree from a graph?
8.2.
What are storage structures for graphs?
8.3.
What use cases does graph DS have?
8.4.
What purpose do graph algorithms serve?
8.5.
What is a tree, and what is its type?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check whether given degrees of vertices represent a Graph or Tree

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

In this article, we will check whether given degrees of vertices represent a Graph or Tree.

Before that, I will take you to the introduction of graph and tree.

Introduction

tree is a discrete structure depicting the interactions between different parts or nodes in a hierarchy. Each parent has no more than two offspring in a binary tree.

graph is a visual representation of a collection of things where some object pairs are linked together. Vertices are the points used to depict related items, while edges are the connections between them.

Problem Statement

Given that there are n vertices, each of which has a degree of 1, 2, 3, etc., Identifying a graph or tree is the problem at hand. The graph might be thought of as connected.

tree and graph

Example

Input 

5
1 1 1 3 2

Output

Tree

Input 

3
3 3 3

Output

Graph

Explanation

Vertex one has a degree of 2, while vertex two has a degree of 3, vertices 1, 3, and 2 have a degree 1, and so on.

Explanation tree

In the other hand, vertex one, two and three all have 2 so,           

Explanation graph

Approach

The number of edges entering or exiting a vertex determines its degree. The characteristics of trees make it easy to accomplish this.
 

  • While graphs can contain cycles, trees are connected and do not.
     
  • There is no such restriction for a graph, but a tree has exactly n-1 edges.
     
  • The input graph is taken to be connected. It takes at least n-1 edges to connect n nodes. Each edge will be tallied twice if all the degrees are added.
     

If we add all the degrees, each edge will be counted twice. As a result, The total of all degrees for a tree with n vertices and n - 1 edge should equal 2 *(n – 1). For further information, please see Handshaking Lemma.

In essence, we must determine whether the sum of all degrees is 2*(n-1) or not.

Implementation in C++

// Checks whether the input degree sequence is a graph or a tree in C++. 
#include<iostream> 
using namespace std; 
  
// The function returns either true for trees or false for graphs. 
bool check(int degree[], int n) 
{ 
    // Fetching sum of all degrees 
    int sum = 0; 
    for (int i = 0; i < n; i++) 
        sum += degree[i]; 
  
    // If the sum is 2(n-1), the graph is a tree 
    return (2*(n-1) == sum); 
} 
  
// programme for testing the above functionality
int main() 
{ 
    int n = 5; 
    int degree[] = {1, 1, 1, 3, 2}; 
  
    if (check(degree, n)) 
        cout << "Tree"; 
    else
        cout << "Graph"; 
  
    return 0; 
}

Output

Tree

Implementation in Java

// Checks whether the input degree sequence is a graph or a tree in java.   
class Fetch  
{ 
  
    // The function returns either true for trees or false for graphs. 
    static boolean check(int degree[], int n) 
    { 
        // Fetching sum of all degrees 
        int sum = 0; 
        for (int i = 0; i < n; i++)  
        { 
            sum += degree[i]; 
        } 
  
        // If the sum is 2(n-1), the graph is a tree   
        return (2 * (n - 1) == sum); 
    } 
  
    // programme for testing the above functionality 
    public static void main(String[] args) 
    { 
        int n = 5; 
        int degree[] = {1, 1, 1, 3, 2}; 
  
        if (check(degree, n)) 
        { 
            System.out.println("Tree"); 
        }  
        else 
        { 
            System.out.println("Graph"); 
        } 
    } 
}

Output

Tree  

Implementation in Python

#  Checks whether the input degree sequence is a graph or a tree in C++. 
def check(degree, n): 
      
    # Fetching sum of all degrees 
    sum = sum(degree) 
      
    # If the sum is 2(n-1), the graph is a tree   
    if (2*(n-1) == sum): 
        return True
    else: 
        return False
      
#programme for testing the above functionality
n = 5
degree = [1, 1, 1, 3, 2]; 
if (check(degree, n)): 
    print "Tree"
else: 
    print "Graph"

Output

Tree

Complexity

Time Complexity

O(N): where n is the size of array.

Reason: As we are fetching the sum of degrees in the program so, we are using for loop, which iterates from 0 to n.

Space complexity

O(N): where n is the size of array.

Reason: As we are fetching the sum of degrees in the program so, we are using for loop, which requires an array of size n.
Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

What specific point distinguishes a tree from a graph?

There are vertices/nodes and edges in a graph. There are many nodes and edges in a tree. There is no single node in the graph that is the root. There is a special node in a tree called the root.

What are storage structures for graphs?

A graph is a type of data structure where information is stored among numerous groups of connected edges (paths) and vertices (nodes). Many Nodes and Edges make up the graph data structure. Vertices and nodes must both be finite.

What use cases does graph DS have?

Application in defining the software applications' computational flow. It is used to create transportation systems in Google Maps. In Google Maps, the node is the intersection of two or more roads, and the edge is the route that connects two nodes.

What purpose do graph algorithms serve?

In order to depict graphs as networks, such as flights, the Internet's connectivity, or Facebook's social network connectedness, graph algorithms are utilised. They are frequently used to create networks in NLP and machine learning.

What is a tree, and what is its type?

A particular kind of data structure used to represent hierarchical data is a tree. Nodes and edges make up the nonlinear structure. The complexity rises with the size of the data for the different kinds of data structures that carry out operations in a linear data structure.

Conclusion

We have checked whether given degrees of vertices represent a Graph or Tree by implementation with three different programming languages. If you want to master Graph and Tree, please check the following articles:

If you face any doubt, please comment, and we will love to answer your questions.

Want expertise in Python for your next web development project? Check out our course.
Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass