By: Prof. Dr. Fazal Rehman | Last updated: March 3, 2022
What is graph?
A graph is a set of nodes and that set must not be empty. The graph contains the following important components.Start node: A set of initial nodes and that set must not be empty.Final node: A set of final nodes and that set must not be empty.Edges: A set of edges. Edge is a link of one node with another node.Figure 1: graphPath : A path is a sequence of nodes.Edge: Each pair of nodes is an edgeLength: The number of edges represents the length of the graph. Note that only one single node is a path of length 0Subpath: A smaller subset path of a big superset path is subpath.Reach: A reach is a subgraph that can be reached from nodes.Figure 2: Reach of a graphExample of Paths:Following are some of the paths in the above-mentioned diagram.[ 0, 3, 7 ], [ 1, 4, 8, 5, 1 ], [ 2, 6, 9 ]Similarly, there are also some more possible paths in figure 2.Example of Reach:Following are some of the reach in the above-mentioned Figure 2.Reach (0) = { 0, 3, 4, 7, 8, 5, 1, 9 }This means that if we starts from node 0 then we can reach 3, we can reach,4 and similarly we can reach 7,8,5,1,9Reach([2,6]) = {2, 6, 9}This means that if we starts from node 0 and then after 0 if we read 6, then we can reach 9 only.