# CS代考程序代写 algorithm Algorithms 3027/3927 Assignment 1 v2 The University of Sydney 2019 Semester 1 School of Computer Science

Algorithms 3027/3927 Assignment 1 v2 The University of Sydney 2019 Semester 1 School of Computer Science
Description
Consider the following variant of the MST problem. We are given an undirected, complete graph G = (V, E) with n vertices and m = 􏰠n􏰡 edges, a positive (not necessarily unique) edge cost ce for each edge
2
in E. We are also given a subset of vertices A 􏰥 V . The goal is to find a minimum cost set of edges F ⊆ E such that (V, F ) is connected, and degF (u) = 1 for each u ∈ A (i.e. every u ∈ A has degree 1 in the graph (V, F )).
Show that simply computing the MST does not work. In particular, show that there is a graph G = (V, E) with edge costs ce and a subset of vertices A 􏰥 V such that the minimum spanning tree X for this graph has degX(u) > 1 for some u ∈ A. Your task is to give such a graph on three vertices x,y,z. You need to specify:
1. the edge weights c(x,y), c(y,z), c(z,x),
2. thesubsetA􏰥V,
3. a minimum spanning tree X, and
4. avertexu∈AsuchthatdegX(u)>1.