Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Computer Engineering Expert

problem 1: Let G = (V,E) be a graph for which all nodes have degree 5 and where G is 5-edge is connected.

a) Show that the vector x which is indexed by the edges E and for which xe= 1/5 for all e in E is in the Perfect Matching Polytope PPM.

b) Use your result in a) to show that G must have a perfect matching.

c) Show that b) may not be true if G is only 1-edge connected (but still has degree 5 everywhere) by giving an ex of such a graph G which has no perfect matching.
 
problem 2:

a) Find the shortest paths from r to all other nodes in the digraph G = (V,E) shown below using the Bellman-Ford algorithm (as taught in class). Please show your work, and draw the final shortest dipath tree on a copy of a diagram of the digraph.

1186_bellman ford algorithm.jpg

b) Using the potential y found in a), find a new set of costs c* for G which are non-negative, and preserve shortest dipaths.  

problem 3: Demonstrate that Dijkstra’s algorithm does not necessarily work if some of the costs are negative by finding a digraph with negative costs (but no negative cost dicircuits) for which it fails. You must also demonstrate that Dijkstra’s algorithm fails on your ex.
 
problem 4: Find a minimum cost spanning arborescence rooted at r for the digraph shown below, using the final algorithm shown in class. Please show your work, and also give a final diagram which shows your solution on the digraph, and states its final cost.

1162_digraph.jpg


problem 5:

a) Given a digraph G = (V,E), prove that if we add a constant k to the length of every arc coming out from the root node r, the shortest path tree remains the same. Do this by using potentials: 

i) Show there is a potential y* for the new costs for which the paths in the tree to each node v have cost  y*v, and

ii) describe why this proves it. What is the relationship between the shortest path distances of the modified problem and those of the original problem? 
 
b) Can adding a constant k to the length of every arc coming out from a non-root node produce a change in the shortest path tree?  Justify your answer.
 
problem 6: Normally a potential y satisfies yr = 0 and 0  ≥ yw – cvw –yv. Given an integer K ≥ 0, define a K-potential to be an array y that satisfies yr = 0 and K ≥ yw – cvw –yv. Show that for a K-potential y we have that for each node v, yv is within Kn of being the cost of an optimal r-v dipath, i.e. show c(P) + Kn ≥ yv for any r to v dipath P in G.

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M91057

Have any Question? 


Related Questions in Computer Engineering

Modify exercise 1 so that the class can keep track of

Modify Exercise 1 so that the class can keep track of multiple courses. Write a program to test your implementation. Exercise 1 Design and implement a class that allows a teacher to track the grades in a single course. I ...

1 assume a private internet uses a protocol suite totally

1. Assume a private internet uses a protocol suite totally different from the TCP/ IP protocol suite. Can this internet still use the services of UDP or TCP as an end-to-end vehicle of message communication? 2. Can you e ...

Using 5-bit sequence numbers what is the maximum size of

Using 5-bit sequence numbers, what is the maximum size of the send and receive windows for each of the following protocols? a. Stop-and-Wait b. Go-Back-N c. Selective-Repeat

Write a job description for kelvin urich the project

Write a job description for Kelvin Urich, the project manager described in the opening vignette of this chapter. Be sure to identify key characteristics of the ideal candidate, as well as his or her work experience and e ...

Discuss the type of person you consider yourself to be in a

Discuss the type of person you consider yourself to be in a team (from team roles), moreover discuss about special situation that you have had come across in a team and how you had manage the given situation.

Discuss the role of efficiency and effectiveness in the

Discuss the role of efficiency and effectiveness in the creation of value.

Design and implement an algorithm that will convert a

Design and implement an algorithm that will convert a general multiway tree (each node may have more than two successors) to the corresponding ordered binary tree.

To make the initial sequence number a random number most

To make the initial sequence number a random number, most systems start the counter at 1 during bootstrap and increment the counter by 64,000 every half second. How long does it take for the counter to wrap around?

1 what is the difference between law and ethics2 what is

1. What is the difference between law and ethics? 2. What is civil law, and what does it accomplish? 3. What are the primary examples of public law? 4. Which law amended the Computer Fraud and Abuse Act of 1986, and what ...

Composing and using regular expressionsregular expressions

Composing and Using Regular Expressions Regular expressions became popular with the introduction of the UNIX operating system in 1960s and its text processing tools such as  grep  and  ed . Write a two to three (2-3) pag ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro