Pages

Friday, August 14, 2009

Works have done in this week (10/08-14/08)

  1. Coded the Kosaraju's algorithm to find the strongly connected components
  2. Coded Graph's operations
  3. Understood the Becker's et al paper


A path with no repeated vertices is called a simple path, and cycle with no repeated vertices aside from the start/end vertex is a simple cycle. In modern graph theory, most often "simple" is implied; i.e., "cycle" means "simple cycle" and "path" means "simple path", but this convention is not always observed, especially in applied graph theory. Some authors (e.g. Bondy and Murty 1976) use the term "walk" for a path in which vertices or edges may be repeated, and reserve the term "path" for what is here called a simple path.

A path such that no graph edges connect two nonconsecutive path vertices is called an induced path.

A simple cycle that includes every vertex of the graph is known as a Hamiltonian cycle.

No comments:

Post a Comment