Skip to main content

Show that a tree has either one or two centers.

pf : No need to consider any trees on fewer than 3 vertices (WHY?). If the radius of the tree on n ≥ 3 vertices is one, then there is a vertex with eccentricity 1, which means it is connected to all other points. Claim: this center is unique. Assume otherwise, then another point is connected to all other points as well, including the known center. Taking an edge from this point to the known center, another edge out to a third distinct point, and finally an edge back to this point gives a cycle. That contradicts that this graph is a tree. Now let T be a tree with radius r > 1. Remove all vertices of degree 1 and their associated edges. This creates a graph of radius r − 1, which we can assume by induction has either 1 or 2 centers, which would obviously be the centers T.



Reference:
[1] 9.1 Introduction to Trees ,Available: click_me 

Comments

Post a Comment

Popular posts from this blog

PCP & MPCP

PCP(Post's Correspondence Problem) MPCP(Modified PCP) PCP consists of two lists A=w1,....,wk and B=x1,....,xk , of strings over some alphabets SIGMA. This instance of PCP has a solution if there is any sequence of integers i1,i2,.....,im,with m>=1. Such that wi1,wi2,....,wim=xi1,xi2,....,xim. The sequence i1,....,im is a solution to this instance of PCP. MPCP  Lists A & B of k strings each from Sigma*.say A=w1,w2,...,wk and B=x1,x2,.....,xk does there exist a sequence of integers i1,i2,....,ir. such that w1 wi1 wi2 .... wir=x1 xi1 xi2 ..... xir ? Difference between PCP and MPCP is that in the MPCP, a solution is required to start with the first string on each list.
Post a Comment
Read more

DESIGN TM FOR {a^n b^n c^n | n>=1}

Concept:- General_idea: click_me L={a^n b^n c^n | n>=1} w={abc,aabbcc,aaabbbccc,....} a a a b b b c c c  X a a Y b b Z c c X X a Y Y b Z Z c Step_1: Replace a by X and go right side. TM tape can move any side. It has infinite memory in both side. And it can remember previous states details. Step_2: Replace b by Y and go right side of tape. Step_3: Replace c by Z and turn left till X .  Step_4: After seeing X(capital X) replace next a by X and do same loop. Step_5: X portions finished. Step_6: Move to Y states. Denote it for one move first and after that notate self loops. Goto final state Z in self loop. Finally stop turing machine. Success. Next step: How to add self loop states? Ok listen me... For that we are taking two steps X a a Y b b Z c c X X a Y Y b Z Z c  Just understand in between symbols. And make it as self loops. If any doubt please post comments..I can explain it. Small editing...This one...
Post a Comment
Read more

Counter Machines

Counter machine has the same structure as the multi-stack machine  but in place of each stack is a counter. Counters hold any non-negative integer,but we can only distinguish between zero and nonzero counters. That's the move of the counter machine depends on its state,input symbol and which if any of the counters are zero. In one move,the counter machine can a)change state b)Add or subtract 1 from any of its counters,independently. However a counter is not allowed to become negative,so it cant subtract from a counter that is currently 0. Counter Machine may also be regarded as a restricted multi-stack machine. The restrictions are as follows, a)There are only two stack symbols,which we shall refer to as Z0(the bottom of stack marker) and X. b)Z0 is initially on each stack. c)We may replace Z0 only by a string of the form X^iz0 for some    i >=0. d)We may replace X only by X^i for some i >= 0. That's Z0 appears   only on the bottom of each stack and...
Post a Comment
Read more