1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Nadusha1986 [10]
3 years ago
8

Suppose we are given an arbitrary digraph G = (V, E) that may or may not be a DAG. Modify the topological ordering algorithm so

that given an input G, it outputs one of the two things: a. A topological ordering thus establishing that G is a DAG. b. A cycle in G thus establishing that it is not a DAG. The runtime of your algorithm should be O(m+n) where m = |E| and n = |V|
Computers and Technology
1 answer:
lianna [129]3 years ago
3 0

Answer:

Check the explanation

Explanation:

We can utilize the above algorithm with a little in modification. If in each of the iteration, we discover a node with no inward edges, then we we’re expected succeed in creating a topological ordering.

If in a number of iteration, it becomes apparent that each of the node has a minimum of one inward edge, then there must be a presence of cycle in the graph.

So our algorithm in finding the cycle is this: continually follow an edge into the node we’re presently at (which is by choosing the first one on the adjacency list of inward edges to decrease the running time).

Since the entire node has an inward edge, we can do this continually or constantly until we revisit a node v for the first time.

The set of nodes that we will come across among these two successive visits is a cycle (which is traversed in the reverse direction).

You might be interested in
ISO 400 is twice as sensitive and ISO 100 true or false
beks73 [17]

Answer:

Quite simply, when you double your ISO speed, you are doubling the brightness of the photo. So, a photo at ISO 400 will be twice brighter than ISO 200, which will be twice brighter than ISO 100.

Explanation:

ISO most often starts at the value of ISO 100. This is the lowest, darkest setting, also called the base ISO. The next full stop, ISO 200, is twice as bright, and ISO 400 is twice as bright than that. Thus, there are two stops between ISO 100 and 400, four stops between 100 and 1600, and so on.

4 0
3 years ago
Consider a set of mobile computing clients in a certain town who each
poizon [28]

Answer: answer given in the explanation

Explanation:

We have n clients and k-base stations, say each client has to be connected to a base station that is located at a distance say 'r'. now the base stations doesn't have allocation for more than L clients.

To begin, let us produce a network which consists of edges and vertex

Network (N) = (V,E)

where V = [S, cl-l, - - - -  cl-n, bs-l - - - - - - bs-k, t]

given that cl-l, - - - - - cl-n represents nodes for the clients

also we have that bs-l, - - - - - bs-k represents the nodes for base station

Also

E = [ (s, cl-i), (cl-i,bs-j), (bs-j,t)]

(s, cl-i) = have capacity for all cl-i (clients)

(cl-i,bs-j) = have capacity for all cl-i  clients & bs-j (stations)

⇒ using Fond Fulkorson algorithm we  find the max flow in N

⇒ connecting cl-i clients to  bs-j stations

      like (cl-i, bs-j) = 1

   if f(cl-i, bs-j)  = 0

⇒ say any connection were to produce a valid flow, then

if cl-i (clients) connected                f(s,cl-i) = 1 (o otherwise)

if cl-i (clients) connected  to bs-j(stations)   f(cl-i,bs-j) = 1 (o otherwise)

   f(bs-j,t) = no of clients  (cl-i)  connected to bs-j

⇒ on each node, the max flow value (f) is longer than the no of clients that can be connected.

⇒ create the connection between the client and base station i.e. cl-l to base bs-j iff    f(cl-i, bs-j) = 1

⇒ when considering the capacity, we see that any client cannot directly connect to the base stations, and also the base stations cannot handle more than L clients, that is because the load allocated to the base statsion is L.

from this, we say f is the max no of clients (cl-i) that can be connected if we find the max flow, we can thus connect the client to the base stations easily.

cheers i hope this helps

5 0
3 years ago
What describes Accenture's approach to automation?
kogti [31]

human center because we describe stuff by what we see and obserevs

4 0
3 years ago
Read 2 more answers
Complete the function to return the result of the conversiondef convert_distance(miles):km = miles * 1.6 # approximately 1.6 km
AnnZ [28]

Answer:

The complete program is as follows:

def convert_distance(miles):

   km = miles * 1.6 # approximately 1.6 km in 1 mile

   return km

my_trip_miles = 55

# 2) Convert my_trip_miles to kilometers by calling the function above

my_trip_km =convert_distance(my_trip_miles) #3) Fill in the blank to print the result of the conversion

# 4) Calculate the round-trip in kilometers by doubling the result,

print("The distance in kilometers is " +str(my_trip_km))

# and fill in the blank to print the result

print("The round-trip in kilometers is " + str(my_trip_km * 2))

Explanation:

<em>The program is self-explanatory because I used the same comments in the original question.</em>

5 0
2 years ago
Explain the role of ICT in banks​
vladimir1956 [14]

Answer: ICT help banks improve the efficiency and effectiveness of services offered to customers, and enhances business processes, managerial decision making, and workgroup collaborations, which strengthens their competitive positions in rapidly changing and emerging economies.

Explanation: please give branliest I only need one more to make ace

7 0
2 years ago
Other questions:
  • How can u refer to additional information while giving a presentation
    15·1 answer
  • Which data type uses more memory an integer or an unsigned integer?
    6·1 answer
  • What are 3 websites that talk about density of different gases, density in air, behavior of different gases of earth, convection
    13·1 answer
  • What category of predefined formulas in Excel contains the Boolean functions?
    14·1 answer
  • The syntax for accessing a class (struct) member using the operator -&gt; is ____.
    15·2 answers
  • Downloading files is safe for most types of files except Select one: a. documents. b. pictures. c. executable files. d. music fi
    7·1 answer
  • A(n) ________ operator, such as the greater than or less than symbol, can be used in a query criterion to limits the results pro
    12·2 answers
  • How to use repl.it css
    7·1 answer
  • Design a class named Person and its two subclasses named Student and Employee. Make Faculty and Staff subclasses of Employee. A
    13·1 answer
  • From which country samsung is​
    6·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!