Forest Ontology

FLOW ALGEBRA
FOREST ONTOLOGY — DISCRETE MATHEMATICS / GRAPH THEORY
Version: 1.0
Source URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/forest-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Site: https://kirethresearch.org
Status: Formal mathematical synthesis; source page not independently verified.

1. ONTOLOGY IDENTITY
ontology_id: discrete_math.graph_theory.forest
label: Forest Ontology
parent: discrete_math.graph_theory
related: [graph, vertex, edge, tree, connected_component, path, cycle, spanning_forest]
definition: A forest is an undirected graph containing no cycles; equivalently, every connected component is a tree.

2. TYPED ENTITIES
Vertex := hashable identifier
Edge := unordered pair {u,v} of distinct vertices
Graph := (V:Set[Vertex], E:Set[Edge]) with E subset of {{u,v}:u,v in V and u != v}
Forest := Graph satisfying acyclic(Graph)
Tree := nonempty connected Forest
Component := maximal connected induced subgraph
Path := sequence of vertices linked by edges
RootedTree := (Tree, root:Vertex)
RootedForest := Forest with one selected root per nonempty component
SpanningForest := acyclic spanning subgraph of Graph; maximal spanning forest preserves the graph's connected components

3. CORE PREDICATES
adjacent(G,u,v) := {u,v} in G.E
connected(G,u,v) := exists path in G from u to v
acyclic(G) := no simple cycle exists in G
is_forest(G) := undirected_simple(G) and acyclic(G)
is_tree(G) := is_forest(G) and |G.V| >= 1 and connected_all(G)
is_component(G,C) := C is a maximal connected induced subgraph of G
is_leaf(G,v) := degree(G,v) == 1  # unrooted graph convention

4. FLOW OPERATIONS
flow ValidateForest(G:Graph) -> Boolean:
  require undirected_simple(G)
  return acyclic(G)

flow ForestComponents(F:Forest) -> Set[Tree]:
  return connected_components(F)  # includes isolated vertices as one-vertex trees

flow AddIsolatedVertex(F:Forest,v:Vertex) -> Forest:
  require v not in F.V
  return (F.V union {v}, F.E)

flow AddEdge(F:Forest,u:Vertex,v:Vertex) -> Forest:
  require u in F.V and v in F.V and u != v
  require not connected(F,u,v)
  return (F.V, F.E union {{u,v}})

flow RemoveEdge(F:Forest,e:Edge) -> Forest:
  require e in F.E
  return (F.V, F.E minus {e})

flow RootComponents(F:Forest,roots:Set[Vertex]) -> RootedForest:
  require exactly one root selected from each component
  orient each component's edges away from its root
  return rooted representation without changing undirected forest structure

5. INVARIANTS AND ALGEBRAIC LAWS
For finite forests, n = |V|, m = |E|, c = number of connected components:
  m = n - c  (including n = 0, c = 0)
  0 <= m <= max(n-1,0)
  each pair of vertices in the same component has exactly one simple path
  every edge is a bridge
  every subgraph of a forest is a forest
  removing one edge increases component count by exactly one
  adding an edge between distinct components decreases component count by one
  adding an edge within one component creates exactly one simple cycle
  disjoint union of forests is a forest
  any nonempty finite tree with at least two vertices has at least two degree-one leaves
  sum(degree(v) for v in V) = 2m

6. RELATIONSHIPS
Forest --IS_A--> AcyclicUndirectedGraph
Forest --HAS_COMPONENT--> Tree
Tree --IS_A--> Forest
Forest --CONTAINS--> Vertex
Forest --CONTAINS--> Edge
Forest --SUPPORTS--> RootedForest
Forest --SUPPORTS--> SpanningForest
SpanningForest --SPANS_VERTICES_OF--> Graph

7. INFERENCE RULES
R1: undirected_simple(G) AND acyclic(G) => is_forest(G)
R2: is_forest(G) AND connected_all(G) AND |V| >= 1 => is_tree(G)
R3: is_forest(F) AND connected(F,u,v) AND u != v => AddEdge(F,u,v) is invalid
R4: is_forest(F) AND NOT connected(F,u,v) => AddEdge(F,u,v) is a forest
R5: finite_simple_undirected(G) AND |E| = |V| - components(G) => is_forest(G)
R6: is_forest(F) AND e in E => RemoveEdge(F,e) is a forest

8. VALIDATION
Check graph typing, endpoint membership, and absence of self-loops.
Check acyclicity with DFS or disjoint-set union; time O(|V|+|E|) for adjacency-list DFS.
Check component count and finite edge identity m = n-c.
Distinguish an unrooted leaf (degree one) from a rooted leaf (no children).
Do not assume all forests are connected, nonempty, or rooted.
Do not infer that every spanning forest is maximal unless explicitly specified.

9. SEMANTIC_EQUIVALENCE
forest <=> acyclic undirected graph (under the stated graph model)
forest <=> disjoint union of trees (including singleton components)
finite forest <=> finite undirected simple graph with |E| = |V| - components(G)
NOT equivalent: forest and tree; rooted forest and unrooted forest; spanning forest and minimum spanning forest.

10. CONFIDENCE
formal_definitions: 1.00
standard_finite_graph_invariants: 1.00
source_page_alignment: unverified
confidence_scope: mathematical statements under declared assumptions, not source-page transcription

11. FLOW_HASH
algorithm: SHA-256
input: UTF-8 bytes of canonicalised flow content excluding the FLOW_HASH value itself
value: COMPUTE_ON_PUBLICATION

12. UPDATE_MODEL
version: 1.0
update_trigger: correction of definitions, additional graph variants, or verified source-page changes
rules: preserve stable ontology_id; record version, date, changes, and provenance; recompute FLOW_HASH

13. AI_CONSUMPTION
representation: typed declarative graph ontology
reasoning: deductive with explicit assumptions
applications: dependency forests, parse forests, hierarchical knowledge structures, spanning-forest algorithms, graph validation
constraints: never infer edge direction from an unrooted forest; distinguish structural graph facts from semantic assertions
output: machine-readable entities, predicates, operations, proofs, and validation results

END FLOW ALGEBRA