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.
1) List the four most important hardware components of a computer (in your opinion or based...
1) List the four most important hardware components of a computer (in your opinion or based on a source) and detail what their function is. You can use the slides or conduct your own research. Make sure you cite any external sources appropriately. (Approximately 300 words) 2) In class, we talked about different protocols that are used to transfer data across networks. Pick two protocols and detail how they work, then compare and contrast them. Finally, discuss when each protocol...
Computer Networking Proxy Server Related Question: Please explain the caching algorithms of a web proxy server...
Computer Networking Proxy Server Related Question: Please explain the caching algorithms of a web proxy server and include following concepts: Greedy Dual Size, least recently used, and least frequently used.
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
Write one Java application based on the following directions and algorithms. Make sure the results from...
Write one Java application based on the following directions and algorithms. Make sure the results from each of the bulleted items is separate and easy to read/understand. Create an array that will hold 4 string values. Write three separate statements to store your favorite color, your favorite song, and your favorite restaurant in the array elements. I do not want you to use a loop in this logic; use hard-coded index values instead. Print *ALL FOUR* of the values of...
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?
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT