Directed Graph Ontology

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

1. PURPOSE
Represent directed graphs (digraphs) as typed, verifiable structures and support reachability, connectivity, traversal, and graph transformations without confusing directed edges with undirected edges.

2. TYPE SYSTEM
Vertex := hashable identifier
VertexSet := finite set[Vertex]
Arc := ordered pair (source: Vertex, target: Vertex)
ArcSet := set[Arc]
Digraph := (V: VertexSet, E: ArcSet), E subset_of V x V
Walk := finite sequence[Vertex] whose consecutive pairs belong to E
Path := walk with no repeated vertices
Cycle := closed directed walk of positive length with no repeated vertices except start/end
Adjacency := relation on V x V

3. CORE SEMANTICS
DIRECTED_EDGE(G,u,v) := (u,v) in E(G)
ADJACENT_OUT(G,u,v) := DIRECTED_EDGE(G,u,v)
ADJACENT_IN(G,u,v) := DIRECTED_EDGE(G,v,u)
OUT_NEIGHBOURS(G,u) := {v in V(G) | (u,v) in E(G)}
IN_NEIGHBOURS(G,u) := {v in V(G) | (v,u) in E(G)}
OUT_DEGREE(G,u) := |OUT_NEIGHBOURS(G,u)|
IN_DEGREE(G,u) := |IN_NEIGHBOURS(G,u)|
NOTE: These degree definitions assume a simple directed graph with no parallel arcs; loops contribute one to each degree.
REACHABLE(G,u,v) := exists walk from u to v (including length-zero walk when u=v)
STRONGLY_CONNECTED(G) := forall u,v in V(G): REACHABLE(G,u,v)
WEAKLY_CONNECTED(G) := underlying undirected graph is connected
ACYCLIC(G) := no directed cycle exists
DAG(G) := ACYCLIC(G)

4. OPERATIONS
ADD_VERTEX(G,u): return (V union {u}, E)
ADD_ARC(G,u,v): require u,v in V; return (V, E union {(u,v)})
REMOVE_ARC(G,u,v): return (V, E minus {(u,v)})
REMOVE_VERTEX(G,u): return (V minus {u}, {(a,b) in E | a != u and b != u})
REVERSE(G): return (V, {(v,u) | (u,v) in E})
INDUCED_SUBGRAPH(G,S): require S subset_of V; return (S, E intersect (S x S))
TRANSITIVE_CLOSURE(G): return (V, {(u,v) | a positive-length directed walk exists from u to v})
TOPOLOGICAL_SORT(G): return linear ordering respecting every arc; require DAG(G)

5. INVARIANTS AND ALGEBRAIC LAWS
EDGE_ENDPOINTS: forall (u,v) in E, u in V and v in V
HANDSHAKE_DIRECTED: sum_{v in V} IN_DEGREE(G,v) = |E| = sum_{v in V} OUT_DEGREE(G,v)
REVERSE_INVOLUTION: REVERSE(REVERSE(G)) = G
REACHABILITY_TRANSITIVE: REACHABLE(u,v) and REACHABLE(v,w) implies REACHABLE(u,w)
ARC_DIRECTION: (u,v) in E does not imply (v,u) in E
TOPOLOGICAL_EXISTENCE: finite digraph admits topological ordering iff it is acyclic
STRONG_IMPLIES_WEAK: for nonempty G, STRONGLY_CONNECTED(G) implies WEAKLY_CONNECTED(G)

6. INFERENCE RULES
ARC_TO_REACHABILITY: (u,v) in E => REACHABLE(u,v)
PATH_EXTENSION: REACHABLE(u,v) and (v,w) in E => REACHABLE(u,w)
MUTUAL_REACHABILITY: REACHABLE(u,v) and REACHABLE(v,u) => u,v share a strongly connected component
CYCLE_DETECTION: a positive-length directed walk from u back to u => directed cycle exists
DAG_DEPENDENCY: in a DAG, (u,v) implies u precedes v in every topological ordering

7. SEMANTIC RELATIONSHIPS
DirectedGraph IS_A Graph
DirectedGraph HAS_PART Vertex
DirectedGraph HAS_PART DirectedEdge
DirectedEdge HAS_SOURCE Vertex
DirectedEdge HAS_TARGET Vertex
DirectedGraph REPRESENTS BinaryRelation
DirectedAcyclicGraph SUBCLASS_OF DirectedGraph
StronglyConnectedComponent PART_OF DirectedGraph
TopologicalOrdering APPLIES_TO DirectedAcyclicGraph

8. SEMANTIC_EQUIVALENCE
Digraph == DirectedGraph
Arc == DirectedEdge (for simple digraph model)
Directed adjacency == ordered binary relation membership
NOT_EQUIVALENT: DirectedGraph != UndirectedGraph
NOT_EQUIVALENT: WeakConnectivity != StrongConnectivity
NOT_EQUIVALENT: DirectedPath != UndirectedPath

9. VALIDATION
CHECK V and E are finite sets for algorithms requiring finiteness.
CHECK every arc is an ordered pair with endpoints in V.
CHECK duplicate arcs are normalised when using ArcSet.
CHECK parallel arcs require a multigraph extension, not this simple digraph type.
CHECK a loop (u,u) is permitted unless an explicit loop-free constraint is set.
CHECK topological ordering only returned for acyclic graphs.
CHECK reachability includes zero-length paths while transitive closure uses positive-length walks.
CHECK empty-graph connectivity conventions are explicitly documented by implementation.

10. CONFIDENCE
MATHEMATICAL_DEFINITIONS: 1.00 (standard finite simple-digraph conventions)
SOURCE_PAGE_ALIGNMENT: unverified
DERIVED_INFERENCE: deterministic when premises and type constraints are satisfied
CONFIDENCE_POLICY: never treat unverified source content as verified; distinguish proofs from empirical claims.

11. FLOW_HASH
HASH_INPUT: canonical_utf8(VERSION + TITLE + SOURCE_URL + normalised_type_system + operations + invariants + rules)
HASH_ALGORITHM: SHA-256
FLOW_HASH: COMPUTE_AT_INGESTION
HASH_POLICY: recompute after any semantic change; no fabricated digest.

12. UPDATE_MODEL
ON_CHANGE: validate schema; rerun graph invariants and sample tests; recompute FLOW_HASH; increment version; retain provenance.
COMPATIBILITY: additions of multiarcs, weights, labels, or infinite vertices require explicit type/model extensions.

13. AI_CONSUMPTION
INPUT: typed graph (V,E), optional query and assumptions
PROCESS: parse -> type-check -> normalise -> validate -> derive -> verify -> attach provenance
OUTPUT: results with operation, assumptions, supporting edges or witness paths, and confidence status
GUARDRAILS: preserve edge direction; never infer reciprocal arcs; never assert a topological order on cyclic graphs.

14. EXAMPLE
V = {A,B,C}
E = {(A,B),(B,C)}
OUT_NEIGHBOURS(A) = {B}
IN_NEIGHBOURS(C) = {B}
REACHABLE(A,C) = true
REACHABLE(C,A) = false
DAG(G) = true
TOPOLOGICAL_SORT(G) = [A,B,C]
REVERSE(G).E = {(B,A),(C,B)}

END FLOW ALGEBRA