Wikia

Psychology Wiki

Cycle graph

Talk0
34,142pages on
this wiki

Assessment | Biopsychology | Comparative | Cognitive | Developmental | Language | Individual differences | Personality | Philosophy | Social |
Methods | Statistics | Clinical | Educational | Industrial | Professional items | World psychology |

Psychology: Debates · Journals · Psychologists


C6graph

A cycle graph of length 6.

In graph theory, a cycle graph, is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called C_n. The number of vertices in a C_n equals the number of edges, and every vertex has degree two, that is, every vertex has exactly two edges incident with it.

A note on terminologyEdit

There are many synonyms for "cycle-graph." These include simple cycle graph and cyclic graph, although the latter term appears to be used more often by non-graph theorists. Among graph theorists, cycle, polygon, or n-gon are also often used. More specifically, a cycle with an even number of vertices is called even cycle, a cycle with an odd number of vertices is called odd cycle.

PropertiesEdit

A cycle graph is:

In addition:

  • Any graph with a subgraph that is a cycle is not a tree.
  • Cycles with an even number of vertices are bipartite, cycles with an odd number are not. More generally, a graph is bipartite if and only if it has no odd cycles as subgraphs.
  • Cycles with an even number of vertices can be decomposed into a minimum of 2 independent sets (that is, \alpha(n)=2), whereas cycles with an odd number of vertices can be decomposed into a minimum of 3 independent sets (that is, \alpha(n)=3).

Directed cycle graph Edit

DC8

A directed cycle graph of length 8.

A directed cyclic graph is a directed version of a cyclic graph, with all the edges being oriented in same direction.

In a directed graph, a set of edges which contains at least one edge (or arc) from each directed cycle is called a feedback arc set. Similarly, a set of vertices containing at least one vertex from each directed cycle is called a feedback vertex set.

There is a directed cycle through any two vertices in a strongly connected component.

External linkEdit

This page uses Creative Commons Licensed content from Wikipedia (view authors).

Around Wikia's network

Random Wiki