Graph Algorithms

Study:

1)
Topological Sort

2)
Eulerian Path
is a path in graph that visits every edge exactly once.

We can find whether a given graph has a Eulerian Path or not in polynomial time. In fact, we can find it in O(V+E) time.

An undirected graph has Eulerian Path if following two conditions are true.

a) Same as condition (a) for Eulerian Cycle
b) If zero or two vertices have odd degree and all other vertices have even degree.

Note that only one vertex with odd degree is not possible in an undirected graph (sum of all degrees is always even in an undirected graph)

Eulerian Circuit/Cycle is an Eulerian Path which starts and ends on the same vertex.

An undirected graph has Eulerian cycle if following two conditions are true.

a) All vertices with non-zero degree are connected. We don’t care about vertices with zero degree because they don’t belong to Eulerian Cycle or Path (we only consider all edges).

b) All vertices have even degree.

http://www.geeksforgeeks.org/eulerian-path-and-circuit/

3)

Hamiltonian Path in an undirected graph is a path that visits each vertex exactly once.

Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in graph) from the last vertex to the first vertex of the Hamiltonian Path.

http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s