PROBLEM 4 26 -oints total : NOTE: this problem is about shortest-paths TREES rooted at a specied source vertex (as opposed to just individual paths)....

please i neeed help with this question,,, please with explanation

• Attachment 1
• Attachment 2

PROBLEM 4 26 -oints total :NOTE: this problem is about shortest-paths TREES rooted at a specified source vertex (as opposed to just individual paths). The following are facts about shortest paths in directed. unweighted graphs andbreadth-first search (B FS): i. BFS works: From a given source vertex 5 , BFS correctly constructs a validshortest-paths tree rooted at 3. (Where path-length is simply the number ofedgestarcs on a path). NOTE: in general. a shortest-paths tree has as itsroot the source vertes and captures valid shortest paths to all verticesreachable from the source (not just a path for one reachable vertex). ii. Multiple Shortest Paths Trees: In general, shortest-paths trees for a givensource vertex are not unique. iii. Vertex ordering and Shortest Paths Tree Discovered by BFS: Theordering of vertices in an adjacency list representation will determine whichexact shortest paths tree is constructed. Assume that outgoing edges from avertex are examined as they are ordered in the list. 4.A (3 points): Give an example of (ii) using a graph of your own construction.Show at least two valid shortest-paths trees for a vertex you have specified. Use"hash-marks" as in the problem 3 to indicate shortest paths trees (draw the graphtwice - once for each distinct shortest paths tree). 4.3 (7 points): Illustrate (iii) through an example -- i.e., for a graph of your ownconstruction (perhaps the same as in 4A), draw two possible adjacency listrepreSentations (i.e.. with different vertex ordering in the lists) and simulate BFS forboth representations (again from some specified source vertex) and show that theresulting shortest-paths trees are distinct. 4.6 (16 points): The following statement turns out to be false! “Consider an arbitrary graph G = (V,E) and a source vertex .9 E V. For each shortest paths tree mated at s , there exists an ordering of the verticesin an aojiacency iist representation of G which results in precisely thisshortest-paths tree when BFS is run from s .” Consider the figure below. Since the statement is false, for some gra hs andsource-vertex combinations, there are valid shortest-paths trees (roote at thespecified source vertex) which cannot be constructed by BFS no matter how thevertices are arranged in an adjacency list data structure -- as represented by thelittle dot. Such a problem instance (graph and source-vertex) is acounter-example showing the statement is false.