How will you answer these questions?

From: blandet (blandet_at_gmail.com)
Date: 03/13/05 

Date: 13 Mar 2005 13:16:16 -0800

Consider an undirected and connected graph G =(V,E) with at least two
vertices.
We assume that G is given by an adjacency-list representation. An
orientation of G is an assignment of directions to the (undirected)
edges in G so as to produce a directed graph. A balanced orientation
is an orientation of G for which every vertex has at least one
in-going and at least one out-going edge (this condition only applies
to vertices that have at least two incident edges).

In this exercise we develop a O(V+E) time algorithm that constructs a
balanced
orientation of G. The algorithm is as follows:

1. Pick a vertex r in G that either has degree 1 or is part of some
cycle in G.

2. Perform a depth-first search from r in G. The orientation of G is
obtained as
follows. A tree edge (u,v) is oriented from u to v (v was first
discovered by
exploring edge (u,v)). A back edge (u,v)is oriented from u to v if v
is an ancestor of u in the depth-first tree.

Exercise 1
Prove that a vertex with the given properties always exists, and give
a O(V) time algorithm to find such a vertex.

Exercise 2
Prove that the output of the proposed algorithm is a balanced
orientation, and that the algorithm runs on O(V+E). Hint: Handle r as
a special case when proving that the output is a balanced orientation.

Exercise 3
Show that the algorithm could fail if r is an arbitrary vertex in G.

Relevant Pages

  • how will you solve these questions ?
    ... Consider an undirected and connected graph G =with at least two ... orientation of G is an assignment of directions to the ... balanced orientation of G. ... The algorithm is as follows: ...
    (comp.lang.prolog)
  • Re: Oriented Hough Transform
    ... are part of the actual shutter border. ... So if I take into account the orientation of the edges, ... out the results of the algorithm and hence am using matlab, ... final code needs to be in c++ so I cant rely too much on matlab inbuilt ...
    (sci.image.processing)
  • Re: mid-line algorithm please
    ...  I am looking for an algorithm to calculate and detect the mid-line or center of two edge detection lines, ... this algorithm will as an input to my vehicla robot to control the orientation of the robot ... A more complicated option ...
    (comp.soft-sys.matlab)