A graph is said to be connected if there is a path between any two of its nodes.
A Path from a node to itself is called a Cycle. A rgaph must require at least 3 nodes to form a cycle.
A Tree is a connected graph without cycles.
A Forest may be defined as an acyclic graph which has each nodes having one or no predecessors. A Tree may be defined as a forest in which only one node has no predecessors. A Forest may be a single tree or a collection of trees. A forest is said to be ORDERED if it consists of ordered trees.
A Forest F is said to be a Spanning Forest of a graph G if –
- F is a sub-graph of G containing all nodes of G
- F is an ordered forest consists T1, T2 …… Tn ordered trees
- For some T, of the Spanning Forest F, the nodes contained in it are not contained in some other Tj of the same Spanning Forest.
A Spanning Forest consisting of a single tree is called a Spanning Tree.
Consider a Graph below –
A Spanning Forest could be drawn as shown below –
Dotted lines shows the edges in graph not present in Spanning Forest, solid line shows tree edges.
Tree Edges of a graph are edges present both in gaph and Spanning Forest eg: <A, D>, <A, E>, <A, B>, <B, C>.
Forward edges are arcs of the graph from a node to a spanning forest non-son descendant eg: <E,C>
Back Edges are arcs of the graphs from a spanning forest node to an ancestor eg: <CA>
Cross edges are arcs of the graph from a spanning forest node to a non-descendant , non-ancestor node eg: <D,E>, <E,B>, <B,E>