The Gateway to Computer Science Excellence

0 votes

It is valid if we consider Tree as undirected graph ?

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

+2

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

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

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

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.

Anyway it's upto you :)

No need of any further discussions.

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

Please correct if wrong :(

52,315 questions

60,426 answers

201,749 comments

95,226 users