CODEWITHSUNDEEP
graphtheorygraph-theorycycle
Simone
Simone

Reputation: 2311

Definition of cycle in undirected graph

I can't find a formal definition of cycle in an undirected graph. The CLRS only reports a definition of symple cycles that i can't manage to generalize for a generic cycle.

This is the CLRS definition: a symple cycle in a undirected graph is a path <v0,v1,..,vk> so that:

  1. k >= 3
  2. v0 = vk
  3. v1,..,vk are distincts

So i tried to remove the 3 condition to define a generic cycle but this can't work because we can have something like this: <a, b, c, b, a> that is obviously not a cycle.

Upvotes: 2

Views: 2195

Answers (2)

Ante
Ante

Reputation: 5448

Path in graph theory means list of edges or/and vertices satisfying some connectivity conditions. Cycle is closed path, first and last list element are same. Wikipedia article

Path or cycle is called simple if there are no repeated vertices or edges other than the starting and ending vertices. Your example is cycle, but not simple cycle.

Upvotes: 0

Mike Sokolov
Mike Sokolov

Reputation: 7044

I think you can generalize 3 as follows:

  1. Either v1,...,vk are distinct or they contain a simple cycle (a contiguous list of vertices satisfying 1,2,&3).

Upvotes: 1

Related Questions