graph algorithms multigraph is graph in which multiple edges are allowed between pairs of vertices which of the algorithms in this work without modification for multigraphswhat modifications need to be done for the others let (vebe an undirected graph use depth-first search to design linear algorithm to convert each edge in to directed edge such that the resulting graph is strongly connectedor determine that this is not possible you are given set of stickswhich are lying on top of each other in some configuration each stick is specified by its two endpointseach endpoint is an ordered triple giving its xyand coordinatesno stick is vertical stick may be picked up only if there is no stick on top of it explain how to write routine that takes two sticks and and reports whether is abovebelowor unrelated to (this has nothing to do with graph theory give an algorithm that determines whether it is possible to pick up all the sticksand if soprovides sequence of stick pickups that accomplishes this graph is -colorable if each vertex can be given one of colorsand no edge connects identically colored vertices give linear-time algorithm to test graph for two-colorability assume graphs are stored in adjacency-list formatyou must specify any additional data structures that are needed give polynomial-time algorithm that finds  / vertices that collectively cover at least three-fourths ( / of the edges in an arbitrary undirected graph show how to modify the topological sort algorithm so that if the graph is not acyclicthe algorithm will print out some cycle you may not use depth-first search let be directed graph with vertices vertex is called sink iffor every in such that vthere is an edge (vs)and there are no edges of the form (svgive an (nalgorithm to determine whether or not has sinkassuming that is given by its adjacency matrix when vertex and its incident edges are removed from treea collection of subtrees remains give linear-time algorithm that finds vertex whose removal from an vertex tree leaves no subtree with more than / vertices give linear-time algorithm to determine the longest unweighted path in an acyclic undirected graph (that isa tree consider an -by- grid in which some squares are occupied by black circles two squares belong to the same group if they share common edge in figure there is one group of four occupied squaresthree groups of two occupied squaresand two individual occupied squares assume that the grid is represented by two-dimensional array write program that does the followinga computes the size of group when square in the group is given computes the number of different groups lists all groups section described the generating of mazes suppose we want to output the path in the maze assume that the maze is represented as matrixeach cell in the matrix stores information about what walls are present (or absent