The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
70 views

Leaf Nodes =[ Internal nodes with degree 2 ] + 1

It is valid if we consider Tree as undirected graph ?

Or is it valid only for Tree when considered as directed graph

in DS by Loyal (6.8k points)
edited by | 70 views
0
what is the meaning of a directed tree and undirected tree?
0

@

see my comment what I ask to you, please defined both terms?

0
Actually I mean to say Tree as directed graph and Tree as undirected graph
0
tree and graph both are same?
0
in question it is not clear?
0

See this

+1

@Lakshman Patel RJIT

He meant that is that formula true when take tree as directed graph or undirected graph.

@jatin khachane 1

Tree by default is a directed graph so minimum degree is 0 i.e.  deg of leaf. But if we treat in as undirected graph then min deg becomes 1.

But the above formula holds for tree as directed graph.

leaf nodes = internal nodes+1 (for full binary tree)

leaf node=internal nodes with deg2 + 1 (for all trees)

 

0

@jatin khachane 1

i suggest you to " Don't remember the formulas, derive them whenever those are required "

it may help you https://gateoverflow.in/8059/gate2015-2-10?show=283868#c283868

0

Thnaks bro @MiNiPanda

Answer m expecting

One more doubt

In undirected : 
A graph is TREE IFF It is connected and has n-1 edges

But this may not be true in directed case right

 

0

@Shaik Masthan

I didn't remember it ..i found it one answer ..so i found it may not work for directed case so I put question

0
you didn't provide any explanation of your approach then how can i think you are not remembering it ?

Anyway it's upto you :)

No need of any further discussions.
0

@jatin khachane 1

But this may not be true in directed case right

Why so..?

0

In directed Case : degrees possible 0,1,2
Let

I = nodes with degree 2

L = nodes with degree 0

X = nodes with degree 1

Sum of degrees = Number of edges [since directed]

I(2) + L(0) + X(1) = [I+L+X] - 1

2I + X = I + L + X -1

I = L - 1 ==> L = I +1

@Shaik Masthan

Please correct if wrong :(

0

@jatin khachane 1

Yes you are right..

And please check the edit i did in my comment..i misread your question at that time..

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,807 questions
54,713 answers
189,261 comments
79,698 users