Which graph is/contains a cycle? loop? strongly connected component?
I believe the following is correct in regards to graphs above:
- all cycles are loops
- all graphs contain cycles, but $G_3$ has two cycles: $\{(a,b), (b,c)\}$ and $\{(a,b),(b,c),(c,a)\}$?
- all graphs are considered strongly connected?
But if all graphs above are considered strongly connected and all contains cycles, then what is the difference between a cycle and a strongly connected component?
Update:
- A cycle is a simply closed path $v_1, …, v_k, v_1$ with $v_1, …, v_k$ all distinct, and $k\geq3$
- A cycle is a closed path. That is, we start and end at the same vertex. In the middle, we do not travel to any vertex twice.
- A graph is said to be strongly connected if every vertex is reachable from every other vertex.
For the sake of completeness, I added a graph $G_0$ with a real loop:
- $G_0$: This is a directed graph with a loop since there is an edge going from vertex $a$ to itself.
- $G_1$: This is a directed connected graph with a cycle, and this graph also is a strongly connected component. This is NOT a simple graph because it has a pair of vertices that have edges going in both directions of each other.
- $G_2$: This is a directed simple-connected graph with a simple cycle.
- $G_3$: This is a directed connected graph with multiple strongly connected components.
Best Answer
A loop is commonly defined as an edge (or directed edge in the case of a digraph) with both ends as the same vertex. (For example from $a$ to itself). Although loops are cycles, not all cycles are loops. In fact, none of the above digraphs have any loops.
Cycles are usually defined as closed walks which do not repeat edges or vertices except for the starting and ending vertex. This definition usually allows for cycles of length one (loops) and cycles of length two (parallel edges).
Note that cycles (and walks) do not make any reference to the orientation of the edges in question. Directed cycles (and directed walks) may only travel along the "forward" direction of the edges. In particular, that implies that $G_3$ pictured above has a third cycle, $(\color{blue}{(a,b)},(b,c),(c,a))$ where the $\color{blue}{(a,b)}$ refers instead to the edge pointing from $b$ to $a$.
Technically, all of the graphs above except for $G_2$ are directed multigraphs since in each you have parallel edges. Although in simple graphs (graphs with no loops or parallel edges) all cycles will have length at least $3$, a cycle in a multigraph can be of shorter length. Usually in multigraphs, we prefer to give edges specific labels so we may refer to them without ambiguity.
As for being strongly connected, yes all of them are and your definition is correct.
Your additional question, "what is the difference between a cycle and a connected component"
The above graph contains a cycle (though not a directed cycle) yet is not strongly connected.
One can prove that if a directed multigraph is strongly connected then it contains a cycle (take a directed walk from a vertex $v$ to $u$, then a directed walk from $u$ to $v$. Any closed walk contains a cycle).
One can also show that if you have a directed cycle, it will be a part of a strongly connected component (though it will not necessarily be the whole component, nor will the entire graph necessarily be strongly connected).