As I can see the graph for Question 3 , the first thing that comes to my mind is to make a adjacency Matrix which will simplify the graph the graph and can see each vertex clearly , this will also help us to reverse the graph.
So the adjacency Matrix for the graph is
in this , as you can see that (A,C)=1 that means Edge A points to C
and this is same for all edges where 1 is filled.
so now as we have this Matrix we can easily fill Adjacency List for G graph
E{A}={C}
E{B}={A,D}
E{C}={B}
E{D}={C,G}
E{G}={C,H}
E{H}={S}
E{S}={B}
So till here we have filled the adjacency table for G graph now we to make a function that will take Adjacency matrix and give us Gr(G reversed graph).
Pseudo Code:-
1) Function will be taking the 2 dimentional Matrix which is our Adjacency matrix as a parameter with a return type of 2D matrix so that it can return the reversed graph adjacency matrix .
Adjacency Matrix with Index
2)Initialise the 2D matrix for reversed graph adjacency matrix of exactly same size as original matrix.
3)Now we have to traverse the whole Matrix using 2 'for' Nested Loop or any method of your choice.
4)In the Inner loop we will be checking for the value 1 and as we get the value 1 then we just have to exchange the x and y coordinates with each other and store 1 on that coordinates in Matrix that we have made for Reverse graph. Like this we will get the adjacency matrix for reversed graph.
G-Original Graph Matrix
RG-Reversed Graph Matrix - Initially RG will have all 0 values
suppose in this example we will get 1 at G[1][0] So we have to store 1 at RG[0][1].
G[0][2] is 1 therefore we to store 1 at GR[2][0]
5)After the nested are done traversing each matrix address, we will have our adjacency matrix for reversed graph done.
6)Now we just have to return this reversed Grap Matrix.
7) End of function
So Now we got our adjacency Matrix for reversed Graph so now we can easily fill the table for Reversed graph
E{A}={B}
E{B}={C,S}
E{C}={A,D,G}
E{D}={B}
E{G}={D}
E{H}={G}
E{S}={H}
Here is the Reversed Graph:-
I have also added Programming in JAVA it will help you to understand it better.
CODE:-
OUTPUT:- Adjacency Matrix for reversed Graph
Help with Q3 please! 3 (9 pts) For the graph G (VE) in question 2 (above),...
3. Given a directed graph G < V E >, we define its transpose Gr < V.E1 > to be the graph such that ET-{ < v, u >:< u, v >EE). In other words, GT has the same number of edges as in G, but the directions of the edges are reversed. Draw the transpose of the following graph: ta Perform DFS on the original graph G, and write down the start and finish times for each vertex in...
Problem 3 (15 points). Let G (V,E) be the following directed graph. a. 1. Draw the reverse graph G of G. 2. Run DFS on G to obtain a post number for each vertex. Assume that in the adjacency list representation of G, vertices are stored alphabetically, and in the list for each vertex, its adjacent vertices are also sorted alphabetically. In other words, the DFS algorithm needs to examine all vertices alphabetically, and when it traverses the adjacent vertices...
Show how depth-first search works on the graph of Figure 22.6. Assume that the for loop of lines 5–7 of the DFS procedure considers the vertices in reverse alphabetical order, and assume that each adjacency list is ordered alphabetically. Show the discovery and finishing times for each vertex, and show the classification of each edge. DIJKSTRA(G,w,s) 1INITIALIZE-SINGLE-SOURCE(G,s) 2 S ?? 3 Q ? V[G] 4 while Q =? 5 do u ? EXTRACT-MIN(Q) 6 S ? S?{u} 7 for each...
Exercise 3 (35 points) Depth-First Search Consider the following graph G=(V,E): a) Complete V= {z, ....) (Fill in the blanks. Sort V alphabetically in reverse z–a) b) Complete E = {(zz), ...} c) Complete the adjacency list as a table {sort Adiſul alphabetically in reverse zna} Vertices u Adj[u] {z, } y d) Execute Depth-First Search (DFS(G)) on Graph G. Respect the order of the adjacency list as completed in the previous question. Show all figures (a) through (p) just...
Exercise 2 Given the following graph: a. Write the formal description of the graph, G=(V,E) b. Show the Adjacency Matrix representation C. Show the Adjacency List representation d. Calculate step by step the shortest paths from a e. Show the DFS tree/forest from a f. Show the BFS tree/forest from a g MST using Prim h. MST using Kruskal
Below is the Graph file that needs to be modified(using Python3) : #!/usr/bin/python3 # Simple Vertex class class Vertex: """ Lightweight vertex structure for a graph. Vertices can have the following labels: UNEXPLORED VISITED Assuming the element of a vertex is string type """ __slots__ = '_element', '_label' def __init__(self, element, label="UNEXPLORED"): """ Constructor. """ self._element = element self._label = label def element(self): """ Return element associated with this vertex. """ return self._element def getLabel(self): """ Get label assigned to...
Please answer question 2. Introduction to Trees Thank you 1. Graphs (11 points) (1) (3 points) How many strongly connected components are in the three graphs below? List the vertices associated with each one. 00 (2) (4 points) For the graph G5: (a) (0.5 points) Specify the set of vertices V. (b) (0.5 points) Specify the set of edges E. (c) (1 point) Give the degree for each vertex. (d) (1 point) Give the adjacency matrix representation for this graph....
Question 1 part a, d, e, f, g, h Construct and plot the network using the igraph package http://igraph.org/redirect.html and the adjacency list you wrote. To assign vertex names you can write it as g = graph(edges = c("a", "b", "b", "c"), directed = FALSE) or g = graph(edges = c(1, 2, 2, 3), directed = FALSE) V(g)$name = c("a", "b", "c") 1. Answer the following questions about this graph. a. What is the degree distribution for th graph? b....
Explain ur working 4. [6 marks] Using the following graph representation (G(VE,w)): V a, b,c, d,e, fh E -la, b, [a, fl,la,d, (b,ej, [b,d, c,fl,fc,d],Id,el, sd, f) W(a, b) 4, W(a, f)-9, W(a, d)-10 W(b, e) 12, W (b, d)7, W(c,d) 3 a) [3 marks] Draw the graph including weights. b) [2 + 1-3 marks] Given the following algorithm for finding a minimum spanning tree for a graph: Given a graph (G(V,E)) create a new graph (F) vith nodes (V)...
please help me make this into a contradiction or a direct proof please. i put the question, my answer, and the textbook i used. thank you also please write neatly proof 2.5 Prove har a Simple sraph and 13 cdges cannot be bipartite CHint ercattne gr apn in to ertex Sets and Court tne忤of edges Claim Splitting the graph into two vertex, Sets ves you a 8 Ver ices So if we Change tne书 apn and an A bipartite graph...