In many structured data types, there is an internal structural relationship, or organization, that holds between the components. For example, if we think of an array as a structured type, with each position in the array being a component, then there is a structural relationship of `followed by': we say that component N is followed by component N+1.
The most common organization for components is a linear structure. A structure is linear if it has these 2 properties:
A->B->C->D(this is one value with 4 parts).
Dropping Constraint P1: If we drop the first constraint and keep the second we get a tree structure or hierarchy: no two elements are followed by the same element. This is a very common structure too, and extremely useful. We'll study it in considerable detail.
Counter example 1 is a tree, but counter example 2 is not.
More complex example:
A is followed by B C D, B by E F, C by G. We are not allowed to add any more arcs that point to any of these nodes (except possibly A - see cyclic structures below).
Dropping both P1 and P2:
If we drop both constraints, we get a graph. In a graph, there are no constraints on the relations we can define.
Cyclic Structures: All the examples we've seen are acyclic. This means that there is no sequence of arrows that leads back to where it started. Linear structures are usually acyclic, but cyclic ones are not uncommon.
Example of cyclic linear structure: A B C D A
Trees are virtually always acyclic.
Graphs are often cyclic, although the special properties of acyclic graphs make them an important topic of study.
Example: Add an edge from G to D, and from E to A.