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

Do cmmi standards support iterative software development

Do CMMI standards support iterative software development? How are SDLC processes supported in CMMI? How are ISO standards different compared to other standards like CMM or IEEE? Do IEEE standards support iterative softwa ...

Powerenergy quantification a server farm has most of its

Power/Energy quantification. A server farm has most of its servers operating at only 50% capacity. The problem is that the power draw from these servers does not scale linearly with the reduced load; that is, when the se ...

For each of the schedules of transactions t1 t2 and t3

For each of the schedules of transactions T1, T2, and T3 below: do each of the following: i. Insert shared and exclusive locks, and insert unlock actions. Place a shared lock immediately in front of each read action that ...

Consider the organization of a unix file as represented by

Consider the organization of a UNIX file as represented by the inode (Figure 12.14). Assume that there are 12 direct block pointers, and a singly, doubly, and triply indirect pointer in each inode. Further, assume that t ...

Writenbspa 1050- to 1400-word paper in which you articulate

Write  a 1,050- to 1,400-word paper in which you articulate the difference between leadership and management using the following criteria: Define leadership and management. Differentiate between leadership and management ...

Is it possible to dynamically generate javascript or css

Is it possible to dynamically generate JavaScript or CSS files for webpages? If so, how would you code a myjs.php or a mycss.php file? What HTTP header is needed in each case?

List all the kinds of risks that can occur on a project

List all the kinds of risks that can occur on a project. What strategy is adopted to minimize the impact of any risk on the project? Describe in detail the steps taken in preparing a risk management strategy.

Look at these two pieces of codea clc b for loop 1 to 4

Look at these two pieces of code:A: CLC B: FOR Loop = 1 TO 4 LDX #0 INPUT Number1, Number2 loop: LDA A,X Sum = Number1 + Number2 ADC B,X PRINT Sum STA C,X NEXT INX CPX #16 BNE loop (a) Which of these pieces of code is wr ...

Suppose that the table employee has a 1n relationship to

Suppose that the table EMPLOYEE has a 1:N relationship to the table PHONE_NUMBER. Further suppose that the primary key of EMPLOYEE is Employee ID and the columns of PHONE_NUMBER are Phone Number ID (a surrogate key), Are ...

Write a one-page summary of a networked application of your

Write a one-page summary of a networked application of your choosing. Conciseness is more important than comprehensiveness, although you should strive for a balance between both. The definition of a networked application ...

  • 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

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate