Questions

How to check if a graph is a tree?

0

I want to know the conditions for a graph to become a tree.



asked 1 year, 10 months ago
Reputation: 1





1 Answer

0

Facts:

  • A tree is always a graph but a graph may or may not be a tree.
  • A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree.

Condition for a graph to become a tree

  • A tree with n vertices will always have n-1 edges, so if a graph has n-1 edges it is a tree.
    Total edges = n-1
  • As each edge contributes for 2 degrees, so for a graph to become a tree sum of degrees of all nodes equals 2(n-1).
    Sum of degrees of all nodes = 2(n-1)

Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,sum,num,i;
    //Number of vertices
    cin>>n;

    sum=0;
    for(i=0;i<n;++i){
        // Degrees for all the vertices
        cin>>num;
        sum += num;
    }

    if(sum==2*(n-1)){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

    return 0;
}

answered 1 year, 10 months ago
Reputation: 1





Your Answer

Nothing to preview

Post Answer



Asked:  1 year, 10 months ago
Viewed:  541 times
Active:  1 year, 10 months ago