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

Crossing disciplines at the end of the chapter we

Crossing disciplines At the end of the chapter, we speculated on how the Wolf Sheep Simple model might be construed as, or converted into, a model of companies moving around in a marketplace searching for resources. Deve ...

Assume that you have a cache designed as specified in the

Assume that you have a cache designed as specified in the last problem. Explain how the function of a TLB can be integrated into this cache; in other words, explain how to use just this cache, with no TLB, to achieve the ...

Q1 identify and provide definitions of the major components

Q1: Identify and provide definitions of the major components of object oriented database modeling? Q2: Identify tools used to develop object oriented data model? Q3: Define its differences between object oriented data mo ...

How can us companies protect their digital assets

How Can U.S. Companies Protect their Digital Assets Overseas? Prepare a 3 to 5 paragraph briefing statement that can be used to answer the above question. Your audience will be attendees at a conference for small busines ...

Write a program that experimentally demonstrates the

Write a program that experimentally demonstrates the comple-mentation property for DES. This program should take as input a key K and a plaintext P and demonstrate that the DES complementation property holds for this key ...

Assignment apple versus samsungapple ipads continue to be

Assignment : Apple versus Samsung Apple iPads continue to be successful. The Samsung Galaxy Tab is one (1) of iPad's competitors. Use the Internet and Strayer Library to research the advantages and disadvantages of these ...

In computer science when we encounter an algorithm we often

In computer science, when we encounter an algorithm, we often need to ask about the complexity of that algorithm (how many computations we need to do). To find the complexity of the distance vector's algorithm, find the ...

Your task is to design a general program for managing board

Your task is to design a general program for managing board games with two players. Your program should be flexible enough to handle games such as tic-tac-toe, chess, or the Game of Nim of Project 6.2. Design an interfac ...

Make a class employee with a name and salary make a class

Make a class Employee with a name and salary. Make a class Manager inherit from Employee. Add an instance variable, named department, of type String. Supply a method to String that prints the manager's name, department, ...

1 for a single-level page table how many page table entries

1. For a single-level page table, how many page table entries (PTEs) are needed? How much physical memory is needed for storing the page table? 2. Using a multilevel page table can reduce the physical memory consumption ...

  • 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

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

Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen