'Cycles between two vertices in a directed graph
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:
Is this a cyclic graph?
Related questions:
Solution 1:[1]
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.
Solution 2:[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).
Solution 3:[3]
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.
Solution 4:[4]
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)
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | |
| Solution 2 | Pat_Guangtailang |
| Solution 3 | Abhishek kumar |
| Solution 4 | c0der |