Cycle Ontology

FLOW ALGEBRA
TITLE: Cycle Ontology
DOMAIN: Discrete Mathematics / Graph Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/cycle-ontology.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
SOURCE_STATUS: Mathematical reference model; live source page not independently verified.

1. PURPOSE
Represent graph cycles as typed, verifiable structures; distinguish closed walks, closed trails and simple cycles; support graph reasoning, traversal, detection and semantic retrieval.

2. TYPED ENTITIES
Graph := (V:Set[Vertex], E:Set[Edge], directed:Boolean)
Vertex := identifier
Edge := (source:Vertex, target:Vertex, identifier?:String)
Walk := (vertices:Sequence[Vertex], edges:Sequence[Edge])
Trail <: Walk where all edge identifiers are distinct
Path <: Walk where vertices are distinct (except closure for a cycle)
ClosedWalk <: Walk where first(vertices)=last(vertices)
Cycle := closed walk of positive length with no repeated internal vertices and, for multigraphs, no repeated edges
CycleLength := NaturalNumber
CycleGraph := Graph with edges forming one cycle
AcyclicGraph := Graph with no cycles under its directedness convention

3. FORMAL SEMANTICS
valid_walk(G,w) := all consecutive vertex pairs are connected by their corresponding edges, respecting direction when G.directed=true.
closed(w) := length(w.edges)>0 AND first(w.vertices)=last(w.vertices).
simple_cycle(G,w) := valid_walk(G,w) AND closed(w) AND all internal vertices are pairwise distinct AND all edges are distinct.
Undirected simple graph: cycle length >= 3.
Directed simple graph: cycle length >= 2; self-loops count as cycles only if loops are permitted by the graph model.
Undirected multigraph: two parallel edges can form a length-2 cycle; loops can form length-1 cycles when permitted.

4. RELATIONSHIPS
Cycle IS_A ClosedWalk.
Cycle HAS_VERTEX Vertex.
Cycle HAS_EDGE Edge.
Cycle BELONGS_TO Graph.
Cycle HAS_LENGTH CycleLength.
AcyclicGraph EXCLUDES Cycle.
Tree IS_A connected undirected acyclic graph.
DirectedAcyclicGraph (DAG) IS_A directed graph without directed cycles.

5. OPERATIONS
cycle_detect(G) -> Set[Cycle] or Boolean (implementation-specific).
cycle_enumerate(G,limit?) -> Sequence[Cycle].
cycle_length(c) := number of edges in c.
cycle_vertices(c) := set of vertices in c.
cycle_edges(c) := set of edges in c.
remove_edge(G,e) -> Graph.
add_edge(G,e) -> Graph.
rotate_cycle(c,k) -> equivalent cyclic representation.
reverse_cycle(c) -> valid traversal for undirected cycles; for directed cycles only when reversed arcs exist.

6. GRAPH LAWS AND INVARIANTS
For a finite undirected graph G, G is a forest iff G has no undirected cycles.
For a finite connected undirected graph G, G is a tree iff |E|=|V|-1.
For any finite undirected graph, cycle_rank(G)=|E|-|V|+components(G), counting loops and parallel edges in the usual multigraph convention.
An undirected edge is a bridge iff it lies on no cycle.
A finite directed graph is acyclic iff it admits a topological ordering.
Any finite directed graph with a directed cycle has no topological ordering.
An undirected graph with all vertex degrees even has an Eulerian circuit in each nontrivial connected component; an Eulerian circuit need not be a simple cycle.

7. INFERENCE RULES
IF simple_cycle(G,c) THEN closed(c).
IF simple_cycle(G,c) THEN all edges of c belong to G.
IF G is an undirected forest THEN NOT exists c: simple_cycle(G,c).
IF G is a finite directed graph AND topological_sort(G) succeeds THEN G is acyclic.
IF undirected_edge(G,e) AND e lies on a cycle THEN e is not a bridge.
IF connected_undirected(G) AND acyclic(G) THEN tree(G).

8. VALIDATION
CHECK graph endpoints belong to V.
CHECK edge identifiers distinguish parallel edges when supported.
CHECK walk incidence and direction at each step.
CHECK first and last vertices coincide for a closed walk.
CHECK internal vertices are unique for a simple cycle.
CHECK edges are not reused in a simple cycle.
CHECK minimum cycle length according to simple graph/multigraph/loop conventions.
CHECK directed-cycle tests do not mistake undirected backtracking for a cycle.
CHECK algorithmic claims are scoped to finite graphs where required.

9. SEMANTIC_EQUIVALENCE
cycle ~ simple_closed_path [under declared graph conventions].
cyclic_graph ~ graph_containing_cycle [when 'cyclic' means at least one cycle].
DAG ~ directed_acyclic_graph.
NOT_EQUIVALENT: cycle != arbitrary_closed_walk.
NOT_EQUIVALENT: cycle != Eulerian_circuit.
NOT_EQUIVALENT: cycle != Hamiltonian_cycle (Hamiltonian cycles are a specialised subset).
NOT_EQUIVALENT: directed_cycle != undirected_cycle.

10. CONFIDENCE
formal_definitions: 1.00 (within declared conventions)
validated_graph_instances: 1.00 when checks pass and input is complete
unverified_external_graph_claims: unknown until provenance and evidence assessed
Confidence is evidence-dependent, not a substitute for formal verification.

11. FLOW_HASH
algorithm: SHA-256
scope: canonical UTF-8 normalised flow content excluding the FLOW_HASH value itself
value: COMPUTE_ON_PUBLICATION

12. UPDATE_MODEL
trigger: new graph convention, source correction, ontology revision, or validation counterexample
procedure: preserve prior version; update definitions and dependent rules; rerun tests; recompute FLOW_HASH; record provenance.

13. AI_CONSUMPTION
input: graph structure, directedness, edge multiplicity, loop policy, query
pipeline: parse -> type-check -> validate -> infer -> compute -> explain
output: cycle_exists, cycle_examples, proofs_or_witnesses, validation_status, provenance, confidence
constraints: never conflate cycles with general closed walks; explicitly state graph conventions; do not infer missing edges.

14. EXAMPLES
Undirected simple triangle: V={a,b,c}, E={{a,b},{b,c},{c,a}} -> cycle a-b-c-a of length 3.
Undirected simple path: V={a,b,c}, E={{a,b},{b,c}} -> acyclic.
Directed triangle: E={(a,b),(b,c),(c,a)} -> directed cycle a->b->c->a.
Directed acyclic example: E={(a,b),(b,c),(a,c)} -> no directed cycle.

END FLOW ALGEBRA