Reference no: EM13317782
1) Write an algorithm to classify the edges of a directed graph G into the four categories: tree edge, back edge, forward edge and cross edge (de?ned in De?nition 7.14, pages 342-343).
De?nition 7.14 The edges of a directed graph G are classi?ed according to how they are explored (traversed in their forward direction).
1. If w is undiscovered at the time vw is explored, then vw is called a tree edge, and v becomes the parent of w.
2. If w is an ancestor of v, the vw is called a back edge. (this included vw)
3. If w is a descendent of v, but w has been discovered earlier than the time vw is explored, then vw is called a descendant edge (other name is forward edge).
4. If w has no ancestor/descendant relationship to v, then vw is called a cross edge.
2.) Additional Problems, problem 7.46, page 383.
An Euler circuit in an undirected graph is a circuit (i.e, a cycle that may go through some vertices more than once) that includes every edge exactly once. Give an algorithm that ?nd an Euler circuit in a graph, or tells that the graph doesn't have one.
Each of the following program assignments required a graph-loading procedure that reads in a description of a graph from a ?le and sets up adjacency lists. Attached is some sample code that serves as a starter. Assume the input contains the number of vertices on the ?rst line, followed by a sequence of lines, with each
Algorithms
Programming Assignmentsline containing a pair of vertices representing one edge. Write this procedure so that, with small changes, it could be used for any problems. For a fancier interface, arrange for the graph to be loaded from a named ?le so that "queries" that direct the main program (not the graph-loading procedure above) to solve a particular problem or produce a particular output can be entered at the terminal by the user after loading is completed. In this case, don't forget to have a "query" that exits the program. Test data should be chosen so that all aspects of a program are tested. Include some of the examples in the text. Java Program 1 page 385 Write a depth-?rst search algorithm to determine if an undirected graph has a cycle. Java Program 2, page 385 Write a breadth-?rst search algorithm to determine if a directed graph has a cycle.
Attachment:- AppendixCode.tar
|
Calculate total active earth force of wall per linear foot
: A smooth, vertical wall is 25 feet high and retains a cohesionless soil with a unit weight of 115 pcf and an angle of internal friction of 30 degrees. The top of the soil is level with the top of the wall, and the soil carries a uniformly
|
|
What is the distance between two converging lenses
: What is the distance between two converging lenses, each of ofcal length f and used in combination to become a telescope
|
|
Calculate the total active earth force per foot of wall
: Calculate the total active earth force per foot of wall and its point of application from the base of the wall. Use Rankine theory. Calculate the total active earth force per foot of wall if the angle of wall friction between backfill and wall is 2..
|
|
What is the standard deviation of total weekly waiting time
: Suppose your wait time for a shuttle bus in the morning is normally distributed with µ=8 minutes and t1=5 minutes. Due to increased congestion in the afternoon, your wait time for a shuttle bus in the afternoon is normally distributed
|
|
Write a breadth-?rst search algorithm
: Write an algorithm to classify the edges of a directed graph G into the four categories: tree edge, back edge, forward edge and cross edge (de?ned in De?nition 7.14, pages 342-343).
|
|
What is the the net capacitance
: if 5 capacitors each of 5 micro F are connected in series with 4 capacitors each of 4 uF capacitances in parallel. what is the the net capacitance
|
|
Determine the maximum shear stress in the shaft
: The motor A delivers 3000 hp to the shaft at 1500 rev/min, of which 1000 hpis removed by gear B and 2000 hp is removed by gear C. Determine (a) the maximum shear stress in the shaft; and (b) the angle of twist of end D relative to end A.
|
|
Calculate rental fee for different types of borrowable media
: Assume that there is an abstract class called Vehicle, which has two concrete subclasses, Car and Truck. There is also an interface Loadable, which only Truck implements - calculate a rental fee for different types of borrowable media (e.g. books,..
|
|
Find the angle of rotation of the free end of the shaft
: The solid compound shaft, made of three di¤erent materials, carries the two torques shown. (a) Calculate the maximum shear stress in each material. (b) Find the angle of rotation of the free end of the shaft.
|