Fandom

Psychology Wiki

Cycle graph

Redirected from Directed cycle

34,203pages on
this wiki
Add New Page
Talk0 Share

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).

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Also on Fandom

Random Wiki