3
$\begingroup$

What is a linear chain in the context of graphs and trees?

For example:

a topological sort forms a linear chain

What does a linear chain mean in the example above?

Another example from Introduction to Algorithms (CH 12):

Basic operations on a binary search tree take time proportional to the height of the tree. For a complete binary tree with $n$ nodes, such operations run in $\Theta(\lg{}n)$ worst-case time. If the tree is a linear chain of $n$ nodes, however, the same operations take $\Theta(n)$ worst-case time.

$\endgroup$
5
  • $\begingroup$ Can you state where this is from, and give some more context? $\endgroup$ Oct 20, 2015 at 4:14
  • $\begingroup$ Sure, I added another example $\endgroup$
    – lucidgold
    Oct 20, 2015 at 4:24
  • $\begingroup$ Looks like you mean the linear chain takes $\Theta(n)$ time. $\endgroup$ Oct 20, 2015 at 4:26
  • $\begingroup$ Typo! Corrected. $\endgroup$
    – lucidgold
    Oct 20, 2015 at 4:28
  • $\begingroup$ en.wikipedia.org/wiki/Path_graph $\endgroup$ Jun 17, 2016 at 15:26

1 Answer 1

3
$\begingroup$

From context, it's clear that this means a graph which is simply a path, like

1--2--3--4--...--n

so that every vertex has degree 2 except the first and last.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .