Ask Question, Ask an Expert


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.


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

1indonesias production function is y akalphal1-alpha

1.Indonesia's production function is Y = AKαL1-α. Assume that A (technology) = 1 and α = .33. Additionally, Indonesia's investment/savings rate is 10%. Indonesia has 50 units of capital per worker and a constant deprecia ...

Describe the difference between soft and hard skills why

Describe the difference between soft and hard skills. Why are both skill sets necessary and beneficial for all health care professionals?

In this assignment you will apply consumer choice theory

In this assignment you will apply consumer choice theory and marginal analysis to business problems.  Consider each of the following products and services: A pair of tickets to a sporting or cultural event that you enjoy ...

Suppose that we want to use the map-reduce framework of

Suppose that we want to use the map-reduce framework of Section 20.2 to compute one iteration of the Page Rank computation. That is, we are given data that represents the transition matrix of the Web and the current esti ...

Network securityresourcesnetwork security scoring

Network SecurityResources Network Security Scoring Guide. Using the required readings and any other resources you might find helpful, write a paper regarding development of an effective approach to network security withi ...

Assignment - marie amp isatask-q1 a digital computer has a

Assignment - MARIE & ISA Task- Q1. A digital computer has a memory unit with 16 bits per word. The instruction set consists of 122 different operations. All instructions have an operation code part (opcode) and an addres ...

Wat are the mission and values of better world books

What are the mission and values of Better World Books? Critically evaluate their usefulness to the company's management in formulating strategy.

The phillips company paid total cash dividends of 166600 on

The Phillips Company paid total cash dividends of $166,600 on 34,000 outstanding common shares. On the most recent trading day, the common shares sold at $89. What is this company's dividend yield?

Let c be a candidate itemset in ck generated by the apriori

Let c be a candidate itemset in Ck generated by the Apriori algorithm. How many length-(k - 1) subsets do we need to check in the prune step? Per your previous answer, can you give an improved version of procedure has in ...

For the matrix of exercise 1114a starting with a vector of

For the matrix of Exercise 11.1.4: (a) Starting with a vector of three 1's, use power iteration to find an approximate value of the principal eigenvector. (b) Compute an estimate the principal eigenvalue for the matrix. ...

  • 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