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
edited | 70 views
0
what is the meaning of a directed tree and undirected tree?
0
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 "

0

Thnaks bro @MiNiPanda

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

0

@jatin khachane 1

Yes you are right..

1
2