Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hi i have these two problems that are part of a practice set i am doing for exams, i can't seem to get around them. If you can answer any of them thanks in advance.

  1. For a given graph $G=(V,E)$ and an edge $e\in E$, design an $O(n+m)$-time algorithm to find, if it exists, the shortest cycle that contains $e$.

2. (a) Prove that every connected graph $G=(V,E)$ has a node $v\in V$ such that removing $v$ and all its adjacent edges will not disconnect $G$.

(b) For a given connected graph $G=(V,E)$, design an $O(n+m)$-time algorithm to find such a node.

share|improve this question
    
are the graphs directed ? –  Belgi Sep 22 '12 at 15:02
add comment

2 Answers

up vote -1 down vote accepted

For $2$: In order to prove$2.a$ we have to use the fact that the graph is finite (otherwise a graph that looks like a long string from both sides is a counterexample).

Proof is by induction on $|V|$ where the base case is clear (base is for $n=1,2$) .

Assume by negation that the claim is false, then for every $v\in V$ it holds that $G[V\backslash\{v\}]$ have exactly two connected components $L,R$ where both have $>0$ vertices in them and both are connected.

From the induction hypothesis we have a vertex in $L$ s.t removing it and all its adjacent edges will not disconnect $L$, since there is no edge from this vertex to a vertex in $R$ we have it that removing this vertex does not disconnect $G$.

To understand the proof I recommend to do a drawing of a vertex and the left and right side, do this again to the left side etc' untill the left side is too small to divide again in this manner .

For an algorithm: I can only think of a $O(log(n)(n+m))$ time algorithm doing what I wrote in the proof.

share|improve this answer
    
i think i can grasp what you're saying, theres a vertex on a straight line graph such that if that vertex and its edges are removed it doesn't disconnect the graph G. so like, L-x-R => and the middle node(x) is removed? –  AlanTuring Sep 22 '12 at 22:06
    
Almost exactly what I meant - note there can be several edges from $L$ to $x$ and several edges from $x$ to $R$, the key point is that when you are removing $x$ and the edges adjacent you can only disconnect $G$ if there are no edges between $L$ and $R$ since otherwise (since $R,L$ must be connected) $G$ would of been connected (and this would be a contradiction) –  Belgi Sep 22 '12 at 22:19
    
i see thank you so much that makes sense. Could you elaborate a bit about the algorithm? How is it log(n)(n+m) particularly the log(n) part. –  AlanTuring Sep 23 '12 at 3:33
    
For an m+n time do a DFS and take a leaf in any of the DFS trees –  Belgi Sep 23 '12 at 11:48
    
So i think i figured it out using a O(m+n) algorithm. Basically, i am looking for a node in a connected graph G that when removed doesn't disconnect the graph. Using a BFS results in a tree(T) of graph G. This tree can be used in the sense that once a leaf of the tree is found, that node can be removed since it doesn't have any descendants and thus cannot disconnect the graph. This would be O(m+n) since the running time of BFS is O(n+m) and the only extra step would be actually removing the node which would just be another factor of n. –  AlanTuring Sep 25 '12 at 21:00
add comment
  1. If the edge is $uv$, then finding a shortest cycle containing $uv$ is equivalent to finding a shortest path from $u$ to $v$ in $G \setminus uv$. This can be solved by taking breadth first traversal of $G \setminus uv$, starting at $u$, and ending if we hit the vertex $v$. This algorithm requires at most $O(\#\text{edges})$ steps.

    [Note: To actually give the cycle itself, a spanning tree will need to be stored in memory. To construct the cycle, we look at the parent node of $v$ in the tree, it's parent node, and so on, until we reach $u$. This path combined with the edge $uv$ is the shortest cycle in $G$ containing $uv$.]

  2. (a) If $G$ is connected and non-empty, it has a non-empty spanning tree $T$. If we delete one of the leaf nodes in the spanning tree, $w$ say, then $G \setminus w$ is still connected (since $T \setminus w$ is connected).

    [Note: I'm assuming that you already have a proof that connected graphs have spanning trees.]

    (b) A spanning tree of $G$ can be constructed in $O(\#\text{edges})$ steps using breadth first search. The last node this algorithm adds to the spanning tree will be a leaf node of the spanning tree.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.