3

I know that in an undirected graph you have to have at least three vertices to form a cycle. My question is, in a directed graph, is it considered a cycle if two vertices have two edges pointing to each other?

Here is an example:

enter image description here

Is this a cyclic graph?

Related questions:

Suragch
  • 484,302
  • 314
  • 1,365
  • 1,393
  • I would say that is a cycle, but I’m not aware of any graph police that gets to decide what’s a cycle and what’s not. It would be silly, though, to call it a cycle in an undirected graph, since then any graph with at least one edge is cyclic and the term loses all meaning. – Thomas Mailund Dec 11 '21 at 05:32

4 Answers4

5

A graph has a cycle if there is a non-empty path that originates at some vertex and ends at the same vertex. In your graph above, you have a cycle on path A -> C -> A. Similarly, let's imagine a directed graph with 2 vertices A and B and 2 edges AB and BA (where the first letter is the source vertex). This means that there is a cycle A -> B -> A, thus you can have a cycle in a directed graph of 2 vertices.

Nick Clark
  • 1,414
  • 2
  • 16
  • 24
  • You use the term "graph" and not "directed graph". Are you extending this explanation to undirected graphs? – Suragch Dec 12 '21 at 00:02
  • Correct. This extends to directed graphs. I'll update my answer to be clearer. Thank you! – Nick Clark Dec 12 '21 at 03:41
  • Thanks for your explanation here. +1. I'm trying to write a formal explanation for other people like me who are new to graph theory. Do you know of any official references that say what you are saying? I was having trouble finding any. – Suragch Dec 12 '21 at 05:35
  • I don't have my old college textbook lying around, but the Wikipedia definition of a cycle leads to that logic. – Nick Clark Dec 12 '21 at 07:12
2

I would say it (A-C-A) is a cycle. But I am from a different perspective: you may know that for a directed acyclic graph (dag), there is a topological sorting on it; otherwise, there isn't.

Topological sorting is indeed the linear extension of a partial order <=. Thus, dag is the graphical representation of a partial order <=. Be aware that according to the anti-symmetry property of a partial order <= (i.e., if a<=b and b<=a, then a=b), there is no possibility that two edges (a,b) and (b,a) simultaneously exist between two distinct vertices a and b.

In summary, no cycle => exists topological sorting, since no topological sorting on your digraph, thus there must be a cycle (A-C-A).

Pat_Guangtailang
  • 31
  • 3
0

No,it is not considered a cycle if two vertices have two edges pointing to each other in directed graph. They are called Parallel Edges.

Abhishek kumar
  • 1
  • 1
  • 1
    Parallel edges (or multiple edges) on directed graphs have the same source and destination vertices. You can construct a graph such that there is an edge and back edge creating a cycle. – Nick Clark Dec 11 '21 at 17:16
0

According to this definition 1:

A circuit is a closed trail with at least one edge

A-C is considered a circuit.
A-C also complies with this definition2:

A cycle is a circuit in which no vertex except the first (which is also the last) appears more than once.

so it is also a cycle.

1 source: https://proofwiki.org/wiki/Definition:Circuit
2 source: https://proofwiki.org/wiki/Definition:Cycle_(Graph_Theory)

c0der
  • 18,467
  • 6
  • 33
  • 65