What is a "linear chain" in Graph Theory?

2.4k Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.