Tree為connected且不包含任何cycle。
K(1,n)是為star graph。
Acyclic graph可能包含許多components，每個component都為一個acyclic connected subgraph。
因此components也都會為tree。Acyclic graph又稱為forest。
Tree中的任意兩點最多都只存在一個path。Degree為1的點稱為leaf或pendant vertex。
有n個頂點的tree T一定為connected graph，且其edge數量一定等於n-1。
且每個edge都為cut edge。如果我們加入一個edge，那得到的graph會剛好有一個cycle。
Graceful labeling: 給graph中每個vertex都標記一個數字，從0~n，那麼鄰近vertex的差值剛好有1~n且不重複。
考慮path Pn, 那麼Pn的graceful labeling可以用f(vi)來做到:
f(vi) = (i-1)/2 if i is odd
n - i/2 if i is even
Caterpillar graph: 圖中每個點不是位於path P就是和他直接相連。
Eccentricity E(v): v到圖中任意點之間的最長距離。
Center of a graph: eccentricity最小者
Prufer sequence?
Prufer sequence?
留言
張貼留言