Question

In: Computer Science

Graph theory unit. 1. List important computing algorithms in Computer Networking based on application of graph...

Graph theory unit.

1. List important computing algorithms in Computer Networking based on application of graph theory.

2. Explain following using an example. a. graph, edges and vertices of the graph, directed graph, in-degree and outdegree of vertex, incident, a path, a distance

3. What is the worst – case memory usage of DFS?

4. Does DFS find the shortest path from start node to some node w ?

Solutions

Expert Solution

answer 1

some important computing algorithms in networking based on graph theory

  • ford fulkerson algorithm for calculating maximum flow in network
  • djisktra algorithm to calculate the route in link state routing algorithm
  • bellman ford algorithm to find the route in distance vector

Answer 2 3 4 given below

i have given calling seq of dfs for a vertex so that you can trace dfs tree execution in question 4

Path from a to c is 4 in graph but in resultant dfs tree path from a to c is 5

Clearly path in dfs tree is not shortest path

If you are having any doubts please ask i will answer asap


Related Solutions

This is a C++ based question that involves Data Structures and Algorithms. Q. Application: Linked List...
This is a C++ based question that involves Data Structures and Algorithms. Q. Application: Linked List of Bus Transit and Passengers You are to implement a C++ program for City Bus Transit using linked list data structure to maintain record of passengers. Specifically, you are to implement the following methods/functions: For Passenger: o A function which can create a new node of the linked list using new for each newpassenger o A function that prints the time of single passenger...
Discus one application of graph theory.
Discus one application of graph theory.
A email application is an instance of a client-server model of computer networking. T/F Which of...
A email application is an instance of a client-server model of computer networking. T/F Which of the following command is used to list out process details in Unix system. mkdir process_a ls -;a bg ps -l -u $(whoami) Which of the file is used to sink the output of a process to Null. /dev/null /dev/tty /dev /dev/empty What does a pipe operator do? performs an OR operation takes input form a file and fees as input to other command it...
give one of the major application of graph theory in real life
give one of the major application of graph theory in real life
Analyze the application of the transcultural theory for evidence based practice
Analyze the application of the transcultural theory for evidence based practice
1. The problem of multiples. Rashid Phumbhra has made important contributions to astrological computing based on...
1. The problem of multiples. Rashid Phumbhra has made important contributions to astrological computing based on the theory of multiples. In this problem you must design an algorithm to identify whether a number is multiple of 3, 5 and / or 7. That is, the algorithm receives a number and must tell the user if the number is: • only multiple of 3 • only multiple of 5 • only multiple of 7 • only multiple of 3 and 5...
What are important insights about the application of ethical theory in your healthcare?
What are important insights about the application of ethical theory in your healthcare?
An important application of regression in manufacturing is the estimation of cost of production. Based on...
An important application of regression in manufacturing is the estimation of cost of production. Based on DATA (see chart below) from Ajax Widgets relating cost (Y) to volume (X), what is the cost per widget? A: 8.75 B. 7.54 C: None of the answers are correct D: 8.21 E. 7.38 Production volume (units) Total cost ($) 400 450 550 600 700 750 425 475 575 625 725 775 5424 5657 5759 7294 7583 8603 5311 6093 6662 7380 7784 8588
1.In computing terminology, the method of opening an application program and then creating a document is...
1.In computing terminology, the method of opening an application program and then creating a document is known as the ____-centric approach. a.data b.application c.document d.user 2.When you save a WordPad document, it is stored in the main memory (____) of the computer. a.RAM b.REM c.RIM d.ROM 3.The method of first creating a blank document directly in the Documents library and then use the WordPad program to enter data into the document is called the ____- centric approach. a.data b.application c.document...
1) Discuss the complexity of building efficient algorithms in Game Theory (+150 words)
1) Discuss the complexity of building efficient algorithms in Game Theory (+150 words)
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT