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

An ip datagram has arrived with the following partial

An IP datagram has arrived with the following partial information in the header (in hexadecimal): 45000054 00030000 2006... a. What is the header size? b. Are there any options in the packet? c. What is the size of the d ...

1 we said that tcp provides a connection-oriented service

1. We said that TCP provides a connection-oriented service between the two application programs. A connection in this case needs a connection identifier that distinguishes one connection from another. What do you think t ...

Now calculate the relative performance of adders assume

Now calculate the relative performance of adders. Assume that hardware corresponding to any equation containing only OR or AND terms, such as the equations for pi and gi on page B-40, takes one time unit T. Equations tha ...

Abm for education and understanding abm provides us with a

ABM for education and understanding ABM provides us with a new way of understanding the world around us. ABM has many uses in research. But ABM also has great potential as a tool for education. For instance, molecules in ...

Describe two types of variables or methods that can be used

Describe two types of variables or methods that can be used to exchange data between web pages and give example code of both types.

Consider the following binary treea show the order the

Consider the following binary tree (a) Show the order the nodes will be visited in a: (b) Identify all of the leaf nodes. (c) Identify all of the interior nodes. (d) List all of the nodes on level 4. (e) List all of the ...

A show that the normalized uniform periodic b -splines

a. Show that the normalized uniform periodic B -splines satisfy b. If an object of uniform density is approximated by the polygon obtained by joining the adjacent control points by straight lines, find the expressions fo ...

You are designing a controller for a tiny cache that is

You are designing a controller for a tiny cache that is fully associative but has only three words in it. The cache has an LRU replacement policy. A reference record module (RRM) monitors references to the cache and alwa ...

This exercise examines deterministic packet selection

This exercise examines deterministic packet selection. Assume that the packet header contains spaces for routers to enter their IP addresses. a. Suppose the header contains space for 30 router addresses. Initially, these ...

The original us income tax of 1913 was quite simple the tax

The original U.S. income tax of 1913 was quite simple. The tax was • 1 percent on the first $50,000. • 2 percent on the amount over $50,000 up to $75,000. • 3 percent on the amount over $75,000 up to $100,000. • 4 percen ...

  • 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