Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 5: Q3E (page 161)

Design a linear-time algorithm for the following task.

Input: A connected, undirected graphG.

Question:Is there an edge you can remove fromGwhile still leavingGconnected?

Can you reduce the running time of your algorithm toO(V)?

Short Answer

Expert verified

The linear-time algorithm to find an edge in a graph removing which the graph remains connected can be implemented by finding if the graph contains a cycle. And the running time of the algorithm can be reduced toO(|V|)by keeping the track of the visited vertices in the graph.

Step by step solution

01

Define Linear-time algorithm 

A linear-time algorithm is one in which the method's execution time is proportional to the amount of the input.The aim of the questions is to determine whether or not there is a cycle in the graph G(V,E).

Here, V is the vertex set and E is the edge set of the graph G .

If there is no cycle in the graph, there is only one route from one vertex to the other vertex. So, deleting an edge will result in unconnected components.

02

Determine an algorithm to check if graph contains a cycle

The only way to remove an edge from a graph without disconnecting it is if the graph has a cycle. In such instance, one of the cycle's edges can be deleted without causing the graph to be disconnected. The number of edges in a graph with no cycle is equal to one less than the number of vertices. The algorithm return 1, if deleting an edge does not disconnects the graph. Otherwise, the algorithm return 0. The algorithm is as follows:

  1. Calculate the number of vertices in the graph and store it in a variablecv.
  2. Calculate the number of edges in the graph and store it in a variablece.
  3. If the value ofceis higher than or equal tocv, return 1
  4. Else return 0

Calculating the number of vertices and edges in the graph takes the linear time.

03

Reduce the running time toO(V) 

Run the recursive graph traversal. While traversing the graph, the visited nodes are marked. Whenever the already visited node is encountered, the graph traversal return true. The whole graph is traversed if it does not contain cycle. The cycle is found in the graph after traversing edges equal to the number of vertices. The run time of the algorithm can be reduced toOV.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

The following table gives the frequencies of the letters of the English language (including the blank for separating words) in a particular corpus.

blank

18.3%

r

4.8%

y

1.6%

e

10.2%

d

3.5%

p

1.6%

t

7.7%

l

3.4%

b

1.3%

a

6.8%

c

2.6%

v

0.9%

o

5.9%

u

2.4%

k

0.6%

i

5.8%

m

2.1%

j

0.2%

n

5.5%

w

1.9%

x

0.2%

s

5.1%

f

1.8%

q

0.1%

h

4.9%

g

1.7%

z

0.1%

  1. What is the optimum Huffman encoding of this alphabet?
  2. What is the expected number of bits per letter?
  3. Suppose now that we calculate the entropy of these frequencies

H=∑t=026ptlog1pt

(see the box in page 143). Would you expect it to be larger or smaller than your answer above? Explain.

d. Do you think that this is the limit of how much English text can be compressed? What features of the English language, besides letters and their frequencies, should a better compression scheme take into account?

Suppose you implement the disjoint-sets data structure usingunion-by-rank but not path compression. Give a sequence ofm union and find operations onnelements that take Ω(mlogn)time.

Let T be an MST of graph G. Given a connected subgraph H of G, show that T∩H is contained in some MST of H

Graphs with prescribed degree sequences. Given a list of n positive integers d1,d2,…,dn, we want to efficiently determine whether there exists an undirected graphG=(V,E) whose nodes have degrees preciselyd1,d2,…,dn . That is, if V={v1,…,vn}, then the degree of vi should be exactly di. We call (d1,…,dn) the degree sequence of G. This graph G should not contain self-loops (edges with both endpoints equal to the same node) or multiple edges between the same pair of nodes.

(a) Give an example of d1,d2,d3,d4 where all the di≤3 and d1+d2+d3+d4 is even, but for which no graph with degree sequence(d1,d2,d3,d4) exists.

(b) Suppose that d1≥d2≥d3≥dn and that there exists a graph G=(V,E) with degree sequence (d1,…,dn). We want to show that there must exist a graph that has this degree sequence and where in addition the neighbors of v1 are v2,v3,…,vdi+1 . The idea is to gradually transform G into a graph with the desired additional property.

i. Suppose the neighbors ofv1 in Gare not v2,v3,…,vdi+1. Show that there exists i<j≤n and u∈V and such that {v1,vi},{u,vj}∉Eand {v1,vj},{u,vi}∈E

ii. Specify the changes you would make to G to obtain a new graph G'=(V,E') with the same degree sequence as G and where (v1,vi)∈E'.

iii. Now show that there must be a graph with the given degree sequence but in which v1 has neighbors v2,v3,…,vdi+1.

c) Using the result from part (b), describe an algorithm that on input d1,…,dn (not necessarily sorted) decides whether there exists a graph with this degree sequence. Your algorithm should run in time polynomial in n and in m=∑i=1ndi .

Consider an undirected graph G=(V,E)with nonnegative edge weights role="math" localid="1658915178951" we≥0. Suppose that you have computed a minimum spanning tree of G, and that you have also computed shortest paths to all nodes from a particular node role="math" localid="1658915296891" s∈V. Now suppose each edge weight is increased by 1: the new weights are w0e=we+1.

(a) Does the minimum spanning tree change? Give an example where it changes or prove it cannot change.

(b) Do the shortest paths change? Give an example where they change or prove they cannot change.
See all solutions

Recommended explanations on Computer Science Textbooks

Issues in Computer Science

Read Explanation

Big Data

Read Explanation

Data Structures

Read Explanation

Theory of Computation

Read Explanation

Computer Organisation and Architecture

Read Explanation

Computer Systems

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free