Graph Algorithms Ontology

FLOW ALGEBRA
GRAPH ALGORITHMS ONTOLOGY
Version: 1.0
Canonical URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/discrete-ai-mathematics/graph-algorithms-ontology-2.html
Domain: Discrete AI Mathematics / Graph Algorithms
Authors: Mark Higgins — Sky (Recursive AI)
Site: https://kirethresearch.org
Status: Formal ontology synthesis; source-page content not independently verified.

1. PURPOSE
Represent graph algorithms as typed, verifiable transformations of graph states and queries, with explicit preconditions, invariants, complexity bounds, and output certificates.

2. TYPES
Vertex := hashable identifier
Edge := (source:Vertex, target:Vertex, id:Identifier?)
Weight := finite real number
Graph := (V:set[Vertex], E:multiset[Edge], directed:bool)
WeightedGraph := (Graph, w:E -> Weight)
Path := finite vertex sequence (v0,...,vk) with consecutive edges
Walk := Path allowing repeated vertices and edges
SimplePath := Path with no repeated vertices
Cycle := closed walk with no repeated internal vertices
Component := maximal connected vertex subset (undirected)
SCC := maximal mutually reachable vertex subset (directed)
TraversalState := (frontier, visited, predecessor)
ShortestPathResult := (distance:V -> ExtendedReal, predecessor:V -> Vertex?)
SpanningForest := acyclic subgraph spanning all vertices
TopologicalOrder := bijection V -> {1,...,|V|}
FlowNetwork := directed graph with capacities c:E -> Real>=0 and source != sink

3. GRAPH WELL-FORMEDNESS
WF(G) iff finite(V) and finite(E) and forall (u,v) in E: u in V and v in V.
An undirected edge is an unordered endpoint pair; parallel edges are distinguished by edge ID where needed.
NonnegativeWeight(G) iff forall e in E: w(e) >= 0.
DAG(G) iff G.directed and no directed cycle exists.
Connected(G) iff every pair of vertices has an undirected path.

4. RELATIONSHIPS
HAS_VERTEX(Graph,Vertex)
HAS_EDGE(Graph,Edge)
INCIDENT_TO(Edge,Vertex)
ADJACENT_TO(Vertex,Vertex)
REACHABLE_FROM(Vertex,Vertex)
PRECEDES_IN_TRAVERSAL(Vertex,Vertex)
BELONGS_TO_COMPONENT(Vertex,Component)
BELONGS_TO_SCC(Vertex,SCC)
HAS_PATH(Graph,Path)
OPTIMISES(Algorithm,Objective)
REQUIRES(Algorithm,Precondition)
MAINTAINS(Algorithm,Invariant)
PRODUCES(Algorithm,Result)
CERTIFIES(Certificate,Result)
HAS_TIME_COMPLEXITY(Algorithm,Bound)
HAS_SPACE_COMPLEXITY(Algorithm,Bound)

5. ALGORITHM CONTRACT
Algorithm A := (input_type, precondition, transition, invariant, termination_measure, postcondition, complexity).
EXECUTE(A,x) is defined only when x satisfies A.precondition.
CORRECT(A,x) iff A terminates and its output satisfies A.postcondition.
A certificate is independently checkable evidence of the stated postcondition.

6. BREADTH-FIRST SEARCH (BFS)
Input: finite graph G and start vertex s in V.
State: FIFO queue Q, discovered set D, distances d, predecessors p.
Initial: Q=[s]; D={s}; d[s]=0; p[s]=null.
Transition: dequeue u; for each undiscovered neighbour v, set d[v]=d[u]+1, p[v]=u, add v to D and Q.
Invariant: discovered vertices have a valid predecessor path from s; vertices are dequeued in nondecreasing distance.
Postcondition: d[v] equals minimum number of edges from s to v for every reachable v; unreachable vertices have distance infinity.
Time: O(|V|+|E|) using adjacency lists; space O(|V|).

7. DEPTH-FIRST SEARCH (DFS)
Input: finite graph G and starting vertex or all vertices.
State: stack or recursive call stack, visited set, discovery/finish times.
Transition: explore an unvisited neighbour until no unexplored neighbours remain, then backtrack.
Invariant: each vertex is first discovered once; active recursion stack corresponds to a DFS path.
Postcondition: reachable vertices are visited; a full DFS forest covers all vertices.
Time: O(|V|+|E|); space O(|V|) plus adjacency storage.
Uses: cycle detection, topological sorting, SCC algorithms, articulation points and bridges (with appropriate extensions).

8. SHORTEST PATHS
Relax(u,v): if d[u]+w(u,v)<d[v], update d[v] and p[v].
Dijkstra: requires nonnegative edge weights; extracts smallest tentative distance and relaxes outgoing edges.
Dijkstra postcondition: settled distances are optimal; binary heap complexity O((|V|+|E|) log |V|).
Bellman-Ford: permits negative weights; performs |V|-1 relaxation passes and detects reachable negative cycles on an additional pass.
Bellman-Ford time O(|V||E|); if a reachable negative cycle exists, finite shortest distances may be undefined for affected vertices.
DAG shortest paths: topologically order vertices and relax edges once; O(|V|+|E|).
Floyd-Warshall: all-pairs shortest paths by dynamic programming; O(|V|^3) time and O(|V|^2) space; negative cycles require separate handling.

9. MINIMUM SPANNING FOREST
Input: finite undirected weighted graph.
Kruskal: sort edges by weight, add an edge iff it connects distinct disjoint-set components.
Invariant: chosen edges form a forest extendable to a minimum spanning forest.
Time: O(|E| log |E|) including sorting; disjoint-set operations nearly constant amortised.
Prim: grow a tree by minimum-weight crossing edge; run per component for disconnected graphs.
Correctness principle: cut property, with ties allowed.
Postcondition: minimum total weight spanning forest; for connected graph, a minimum spanning tree.

10. DIRECTED GRAPH ALGORITHMS
TopologicalSort(G): requires DAG(G); output order places u before v for every edge u->v.
Kahn: repeatedly remove zero-indegree vertices; failure to process all vertices certifies a directed cycle.
Time: O(|V|+|E|).
SCC: Tarjan or Kosaraju partitions a directed graph into maximal strongly connected components in O(|V|+|E|).
Condensation graph: contract SCCs into supervertices; result is a DAG.

11. MAXIMUM FLOW
Input: directed network (V,E,c,s,t) with c(e)>=0, s!=t.
Feasible flow f satisfies 0<=f(e)<=c(e) and flow conservation at all vertices except s,t.
Residual capacity determines augmenting paths.
Ford-Fulkerson framework: augment along residual s-t paths; termination is not guaranteed for arbitrary irrational capacities under arbitrary path choices.
Edmonds-Karp: choose BFS shortest augmenting path; O(|V||E|^2) time.
Max-flow/min-cut theorem: maximum feasible s-t flow value equals minimum s-t cut capacity.

12. INFERENCE RULES
R1: BFS_REACHED(s,v) -> REACHABLE_FROM(v,s) [direction convention: v reachable from s].
R2: BFS_DISTANCE(s,v,k) and UNWEIGHTED(G) -> SHORTEST_EDGE_COUNT(s,v)=k.
R3: DAG(G) -> EXISTS(TopologicalOrder(G)).
R4: EXISTS(TopologicalOrder(G)) -> DAG(G) for a finite directed graph with all edges respected.
R5: MST_EDGE_BY_CUT_PROPERTY(e) -> SAFE_FOR_SOME_MST(e), subject to the cut and light-edge premises.
R6: NEGATIVE_WEIGHT_EDGE(G) -> NOT_GUARANTEED_CORRECT(Dijkstra,G).
R7: REACHABLE_NEGATIVE_CYCLE(G,s) -> UNDEFINED_FINITE_SHORTEST_PATHS_FOR_AFFECTED_VERTICES.
R8: NO_RESIDUAL_ST_PATH(f) and FEASIBLE(f) -> MAXIMUM_FLOW(f).

13. WORKED EXAMPLES
Example A: V={A,B,C,D}, E={(A,B),(A,C),(B,D),(C,D)} undirected, unweighted.
BFS from A: d(A)=0, d(B)=1, d(C)=1, d(D)=2.
A shortest path to D is A-B-D; A-C-D is equally short.
Example B: directed edges A->B, A->C, B->D, C->D.
Valid topological orders include A,B,C,D and A,C,B,D.
Example C: undirected weighted triangle AB=2, BC=3, AC=7.
Minimum spanning tree edges AB and BC; total weight 5.

14. COMPLEXITY MODEL
n:=|V|; m:=|E|.
Time complexity counts primitive operations as a function of n,m and data-structure assumptions.
Space complexity states whether input graph storage is included or only auxiliary memory.
Traversal with adjacency lists: O(n+m) time.
Adjacency matrix scanning may require O(n^2) time for a full traversal.
Priority-queue choice changes shortest-path and MST implementation bounds.

15. SEMANTIC EQUIVALENCE
'graph traversal' ~ systematic exploration of vertices/edges (not identical to shortest-path optimisation).
'BFS' ~ breadth-first search.
'DFS' ~ depth-first search.
'MST' ~ minimum spanning tree (only when connected; otherwise minimum spanning forest).
'SCC' ~ strongly connected component.
'edge relaxation' ~ candidate shortest-distance improvement.
Distinguish path vs walk; reachability vs adjacency; shortest path vs minimum spanning tree.

16. VALIDATION
V1: Reject graph inputs containing endpoints absent from V.
V2: Reject Dijkstra's optimality claim when negative edges are allowed without further justification.
V3: Check BFS predecessor chains terminate at source and match reported distances.
V4: Check topological order respects every directed edge.
V5: Check spanning forest acyclicity and component coverage.
V6: Check feasible flows satisfy capacities and conservation.
V7: Check claimed complexity against representation and queue/heap assumptions.
V8: Treat disconnected, empty, self-loop and parallel-edge cases explicitly.

17. CONFIDENCE
Formal theorems: HIGH when stated preconditions are satisfied.
Worked-example calculations: HIGH when verified against listed edges and weights.
Implementation-dependent performance: CONDITIONAL on data structures and input representation.
Claims about the source webpage: UNVERIFIED.

18. FLOW_HASH
Canonicalise ontology content as UTF-8, normalise line endings to LF, and hash with SHA-256.
FLOW_HASH := SHA256(canonical_content_excluding_flow_hash_field).
Hash value is computed on publication; no fabricated digest is supplied.

19. UPDATE_MODEL
version: 1.0
change_policy: semantic versioning; record modified rules, proofs, algorithm contracts and assumptions.
update_trigger: corrected complexity, new algorithms, refined definitions, verified source-page changes.
provenance: record source URL, access date, reviewer and change summary when available.

20. AI_CONSUMPTION
representation: typed text-based Flow Algebra
parse_mode: sections + typed relations + rule premises/conclusions
reasoning_mode: precondition-aware symbolic inference
validation_mode: check invariants, postconditions and certificates
safety: do not infer optimality without required assumptions
interoperability: knowledge graphs, algorithm selection, formal verification, educational retrieval
output: algorithm contract, result, complexity, evidence and confidence

END FLOW ALGEBRA