Seld doubt DM

Question

Consider a tree T with n vertices and (n – 1) edges. We define a term called cyclic cardinality of a tree (T) as the number of cycles created when any two vertices of T are joined by an edge. Given a tree with 10 vertices, what is the cyclic cardinality of this tree?

Comments

0??

---

@srestha mam ..they have given 45

@Shaik Masthan @MiNiPanda plz chk once!

---

Add in the title from where you got this question

Answer 1

I assumed it is Undirected TREE., Let N denotes No.of Nodes in the TREE

With N=1 we can't form cycles !

With N=2, If you add one more edge between them, it leads to cycle ==> cyclic cardinality of a tree ( T with 2 Nodes ) = 1

Let analyse from N=3.

N=3 :-

  If i started with B,

              there is one edge which leads to Cycle when we add to the TREE, that is B-C edge

              there is one edge which leads to Cycle when we add to the TREE, that is B-A edge

  If i started with C,

              there is one edge which leads to Cycle when we add to the TREE, that is C-B edge, but it is already counted !

              there is one edge which leads to Cycle when we add to the TREE, that is C-A edge

     cyclic cardinality of a tree ( T with 3 Nodes ) = (2+1) = 3

 

N=4 :-

    cyclic cardinality of a tree ( T with 4 Nodes ) = cyclic cardinality of a tree ( T with 3 Nodes ) + ________________

    Due to all cycles repeated from previous graph !

    Newly ADDED vertex is D

    So, My work is just count how many cycles are formed due to this vertex, then add to the formula !

         Just observe the graph, you will understand that,

    Add edge between D and A, lead to a cycle

    Add edge between D and B, lead to a cycle

    Add edge between D and C, lead to a cycle

     cyclic cardinality of a tree ( T with 4 Nodes ) = 3+3 = 6

 

N=5 :-

    cyclic cardinality of a tree ( T with 5 Nodes ) = cyclic cardinality of a tree ( T with 4 Nodes ) + ________________

    Newly ADDED vertex is E

    So, My work is just count how many cycles are formed due to this vertex, then add to the formula !

         Just observe the graph, you will understand that,

   Add edge between E and A, lead to a cycle

   Add edge between E and B, lead to a cycle

   Add edge between E and C, lead to a cycle

   Add edge between E and D, lead to a cycle

     cyclic cardinality of a tree ( T with 5 Nodes ) = 6+4 = 10

 

N=6 :-

    cyclic cardinality of a tree ( T with 6 Nodes ) = cyclic cardinality of a tree ( T with 5 Nodes ) + ________________

    Newly ADDED vertex is F

    So, My work is just count how many cycles are formed due to this vertex, then add to the formula !

         Just observe the graph, you will understand that,

    Add edge between F and A, lead to a cycle

    Add edge between F and B, lead to a cycle

    Add edge between F and C, lead to a cycle

    Add edge between F and D, lead to a cycle

    Add edge between F and E, lead to a cycle

     cyclic cardinality of a tree ( T with 5 Nodes ) = 10+5 = 15

 

Now you understood what is happening by adding a new vertex to the previous graph,

I mean to say, if i add a new vertex to the graph with number of nodes = x, then it will create x new cycles.

 

cyclic cardinality of a tree ( T with 7 Nodes ) = 15+6 = 21

cyclic cardinality of a tree ( T with 8 Nodes ) = 21+7 = 28

cyclic cardinality of a tree ( T with 9 Nodes ) = 28+8 = 36

cyclic cardinality of a tree ( T with 10 Nodes ) = 10+9 = 45

 

General Recurrance Relation :-

C(N) = C(N-1) + N-1

Solution :-

C(N) = C(N-1) + N-1

       = C(N-1) + (N-1)

       = C(N-2) + (N-2) + (N-1)

       = C(N-3) + (N-3) + (N-2) + (N-1)

       = C(N-k) + (N-k) + .............. + (N-2) + (N-1)

N-k = 2 ==> K = N-2

C(N) = C(N-k) + (N-k) + .............. + (N-2) + (N-1)

       = C(2) + (N-(N-2)) + .............. + (N-2) + (N-1)

       = C(2) + 2 + 3 +.....+ (N-2) + (N-1)

       = 1 + 2 + 3 +.....+ (N-2) + (N-1) = $\frac{N*(N-1)}{2}$

Comments

@Shaik Masthan

Thanks brother!

---

thanks

---

Actually here joining any two vertices will give you a cycle. Number of edges between any two vertices in a graph of n vertices is $_{2}^{n}\textrm{C}$ . Hence the answer!

Answer 2

a node in tree if attached with  [n-deg(node)] other nodes in tree , then it will form cycle

you can try it easily

hence for 10 vertices ,

=[n-deg(vertex1)]+[n-deg(vertex2)]+[n-deg(vertex3)]+[n-deg(vertex4)]+[n-deg(vertex5)]…...10 times

=10n – summation(deg)

=10*10 –  (2*edges)

=100-(2*9)

ans=78