Graphs Assignment

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.

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