Design a linear-time algorithm which, given an undirected graph G and a particular edge e in...

Design a linear-time algorithm which, given an undirected graph G and a particular edge e in it, determines whether G has a cycle containing e. Your algorithm should also return the length (number of edges) of the shortest cycle containing e, if one exists. Just give the algorithm, no proofs are necessary. Hint: you can use BFS to solve this.

Expert Solution

SOLUTION:

FROM THE GIVEN PROBLEM

This can be reduced to Shortest Path Problem:

Find the shortest path from v to u, then the shortest cycle that contains (u,v), is v->...->u->v, where v->...->u is the shortest path from v to u as found by the shortest path algorithm.

It can be solved efficiently using Dijkstra's Algorithm, since there are no negative weights in the graph.

Correctness Proof:

Assume there is a cheaper cycle v1->v2->...vi->u->v->v_i+1->...->vn->v1. Let's say it weights x < d(v,u) + w(u,v)
Since it's a cycle, we can look at it as v->v_i+1->....->vn->v1->...->vi->u->v.
The weight of the cycle didn't change, and is still x. This means x=w(v,v_i+1) + ... + w(vn,v1) + ... + w(v_i-1,vi) + w(vi,u) + w(u,v)
But this gives us w(v,v_i+1) + ... + w(vn,v1) + ... + w(v_i-1,vi) + w(vi,u) + w(u,v) - w(u,v) < d(v,u), and we have found a shorter path from v to u, than d(v,u), which is contradicting correctness of Dijkstra's Algorithm.

Colby Messinger answered 1 year ago

You are given an undirected graph G = ( V, E ) in which the edge...

You are given an undirected graph G = ( V, E ) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight from 1 to W, where W is a constant (independent of the number of edges or vertices). Show that it is possible to compute the single-source shortest paths in such a graph in O(E+V) time.

Given an undirected graph G=(V, E) with weights and a vertex , we ask for a...

Given an undirected graph G=(V, E) with weights and a vertex , we ask for a minimum weight spanning tree in G where is not a leaf (a leaf node has degree one). Can you solve this problem in polynomial time? Please write the proof.

Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph...

Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph contains a cycle, then your algorithm should output one. (It should not output all cycles in the graph, just one of them.) The running time of your algorithm should be O(m + n) for a graph with n nodes and m edges.

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each...

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each edge labeled from the set {0,1}. Describe and analyze the worst-case time complexity of an efficient algorithm to find any cycle consisting of edges whose labels alternate 0,1.

# Problem Description Given a directed graph G = (V,E) with edge length l(e) > 0...

# Problem Description Given a directed graph G = (V,E) with edge length l(e) > 0 for any e in E, and a source vertex s. Use Dijkstra’s algorithm to calculate distance(s,v) for all of the vertices v in V. (You can implement your own priority queue or use the build-in function for C++/Python) # Input The graph has `n` vertices and `m` edges. There are m + 1 lines, the first line gives three numbers `n`,`m` and `s`(1 <=...

Consider an unweighted, undirected graph G = <V, E>. The neighbourhood of a node v ∈...

Consider an unweighted, undirected graph G = <V, E>. The neighbourhood of a node v ∈ V in the graph is the set of all nodes that are adjacent (or directly connected) to v. Subsequently, we can define the neighbourhood degree of the node v as the sum of the degrees of all its neighbours (those nodes that are directly connects to v). (a) Design an algorithm that returns a list containing the neighbourhood degree for each node v ∈...

Give an algorithm that constructs an undirected connected graph, which allows for labeling of the n...

Give an algorithm that constructs an undirected connected graph, which allows for labeling of the n vertices u - v <= k for every edge (u,v), where k is some constant. All nodes have a unique label.

Let G be a connected graph and let e be a cut edge in G. Let...

Let G be a connected graph and let e be a cut edge in G. Let K be the subgraph of G defined by: V(K) = V(G) and E(K) = E(G) - {e} Prove that K has exactly two connected components. First prove that e cannot be a loop. Thus the endpoint set of e is of the form {v,w}, where v ≠ w. If ṽ∈V(K), prove that either there is a path in K from v to ṽ, or...

Prove or disprove: If G = (V; E) is an undirected graph where every vertex has...

Prove or disprove: If G = (V; E) is an undirected graph where every vertex has degree at least 4 and u is in V , then there are at least 64 distinct paths in G that start at u.

Given a connected graph G with n vertices. We say an edge of G is a...

Given a connected graph G with n vertices. We say an edge of G is a bridge if the graph becomes a disconnected graph after removing the edge. Give an O(m + n) time algorithm that finds all the bridges. (Partial credits will be given for a polynomial time algorithm.) (Hint: Use DFS)

Question