Trees and Graphs

Here are definitions of some of the common terms you would often encounter in the context of trees and graphs.

Trees

Tree: A set of nodes and edges connecting the nodes such that there is exactly one path between any 2 nodes.

Rooted tree: A tree where a distinguished node is identified as a root. The nodes share a parent-child relationship. Every node except the root has exactly one parent. The root node does not have any parent.

Path: Connected sequence of edges.

Leaf: A node with no children.

Siblings: Nodes with the same parent.

Ancestor of a node n: Nodes on the path from n to the root (including n itself and the root).

Length of a path: Number of edges on the path.

Depth of a node: Length of path from the node to the root. Depth of root = 0.

Height of a node: Length of path from the node to its deepest descendent. height of a leaf node = 0. Height of tree = Height of root.

Subtree rooted at a node: Tree formed by the node and its descendents.

Binary tree: A tree with no node having more than 2 children.

Graphs

Graph: A set of nodes (or vertices) and edges connecting the nodes. A tree is a particular kind of graph.

Graph representation: G = (V,E), an ordered pair, where V and E are a set of nodes and edges respectively.

Digraph (Directed Graph): A graph where every edge is directed. An edge, e = (u, v) is an ordered pair of nodes, where u and v are referred to as source/origin and sink/destination respectively.

Undirected graph: A graph where an edge e = (u,v) is an unordered pair, i.e., e = (u, v) = (v, u).

Path: A sequence of nodes with an adjacent pair connected by an edge. In a digraph, the edges on the path must be aligned with the direction of the path.

Length of path: Number of edges on the path.

Strongly connected graph: A graph where there is a path from every node to every other node. For an undirected graph, a strongly connected graph is simply called a connected graph.

Degree of a node: Number of edges incident on the node. For a directed graph, indegree of a node refers to the number of edges directed toward the node, and outdegree of a node refers to the number of edges directed away from the node.

This entry was posted in Data-structures. Bookmark the permalink.

Comments are closed.