Graphs Assignment Hints

1. Bridge Connected Components

   Let G= (V, E) be an undirected graph. An edge e E is a bridge if the removal of e increases the number of connected components in G. If E' is the set of bridges in G then each connected component in G' = (V, E-E') is said to be a bridge connected component of G. Design an algorithm to determine the bridge connected components and the bridges in an undirected graph. Analysize the time complexity of your algorithm.

   Observations: <x,y> = e is a bridge => x OR y are articulation point(s)    except for base case (only one edge)

   The converse is not true (articulation points do not imply bridges)

   However, I claim <x,y> = e is a bridge iff e is on no cycle of G.

   (1) Consider the validity of this statement (2) consider the algorithm

2. Euler partition

   An Euler partition of a graph G = (V, E) is a partition of E into a set of edge disjoint paths and circuits such that every node of odd degree is at the endpoint of exactly one path. Write an O(|V| + |E|) algorithm to compute the Euler partition.

   Example:

   Graph	Euler partition

   Assuming the problem is solvable (i.e., that there exists an Euler Partition), then all paths must start with an odd node - or become a loop. Capitalize on this...

Uses: I found links to these when I did google on Euler Partitions
Using euler partitions to edge color bipartite multigraphs and here too
Resources say similar idea used to do:
Avoiding memory contention on tightly coupled multiprocessors
Cycles in Wavelength Routed Optical Networks - Lightwave