Forest Ontology

FLOW ALGEBRA
FOREST ONTOLOGY
Kireth Semantic Library | Mathematical Entities | Graph and Network Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/graph-and-network-entities/forest-ontology-2.html
Version: 1.0 | 2026-10-14 | Locale: en-GB
Authors: Mark Higgins — Sky (Recursive AI)
Status: Proposed mathematical formalisation; source-page wording not independently verified.

flow "ForestOntology" v1.0 {
  DOMAIN: GraphTheory
  ENTITY: Forest
  DEFINITION: An undirected graph containing no cycles; equivalently, a disjoint union of trees (including isolated vertices).

  TYPES {
    Vertex: identifiable entity
    Edge: unordered pair of distinct vertices
    Graph: (V:Set<Vertex>, E:Set<Edge>)
    Forest: Graph where acyclic(Graph)
    Tree: connected(Forest)
    Component: maximal connected subgraph
    RootedForest: Forest with one designated root per nonempty component
    SpanningForest: acyclic spanning subgraph of a graph, commonly maximal within each component
  }

  AXIOMS {
    A1: V is finite for finite-forest counting rules; E subset of {{u,v}:u,v in V and u != v}.
    A2: FOREST(G) iff UNDIRECTED(G) and NOT EXISTS simple_cycle(G).
    A3: Every connected component of a forest is a tree.
    A4: Between any two vertices in the same forest component there is exactly one simple path.
    A5: For finite forest G with n vertices and c connected components, |E| = n - c (including n=0,c=0).
    A6: Every subgraph of a forest is acyclic.
    A7: Adding an edge between vertices in different components preserves acyclicity and reduces component count by one.
    A8: Adding an edge between distinct vertices already connected in a forest creates exactly one cycle.
  }

  RELATIONSHIPS {
    Forest IS_A AcyclicUndirectedGraph
    Forest HAS_COMPONENT Tree
    Tree IS_A Forest
    Forest HAS_VERTEX Vertex
    Forest HAS_EDGE Edge
    Edge CONNECTS Vertex
    RootedForest ASSIGNS_ROOT_TO Component
    SpanningForest SPANS_VERTICES_OF Graph
    Forest SEMANTICALLY_DISTINCT_FROM Tree: forest need not be connected
    Forest SEMANTICALLY_DISTINCT_FROM DirectedAcyclicGraph: edge orientation differs
  }

  MATHEMATICAL_RULES {
    COMPONENT_COUNT: c(G) = |V| - |E| for finite forests.
    CYCLE_RANK: mu(G) = |E| - |V| + c(G) = 0 for finite forests.
    DEGREE_SUM: sum(deg(v) for v in V) = 2|E|.
    UNIQUE_PATH: connected(u,v) implies exactly one simple u-v path.
    ISOLATED_VERTEX: degree(v)=0 implies {v} is a tree component.
    ROOTED_PARENT: each non-root vertex has exactly one parent within its rooted component.
  }

  INFERENCE {
    R1: IF undirected(G) AND acyclic(G) THEN classify(G,Forest).
    R2: IF classify(G,Forest) AND connected(G) AND |V|>0 THEN classify(G,Tree).
    R3: IF classify(G,Forest) AND finite(G) THEN assert(|E|=|V|-component_count(G)).
    R4: IF classify(G,Forest) AND vertices_in_different_components(u,v) THEN adding_edge(u,v) yields Forest.
    R5: IF classify(G,Forest) AND vertices_in_same_component(u,v) AND u!=v THEN adding_edge(u,v) yields CyclicGraph.
    R6: IF classify(G,Forest) AND remove_edge(e) THEN result is Forest with one additional component.
  }

  EXECUTION {
    INPUT: graph G with vertex set V and undirected edge set E
    PRECONDITIONS: valid vertex identifiers; endpoints in V; no self-loops; no duplicate edges under simple-graph convention
    STEP_1: initialise disjoint-set union for all vertices
    STEP_2: for each edge {u,v}, reject if find(u)=find(v), else union(u,v)
    STEP_3: if no rejection, classify as Forest
    STEP_4: count disjoint-set roots as components c
    STEP_5: validate |E|=|V|-c
    OUTPUT: {is_forest, component_count, component_vertex_sets, edge_count, validation_result}
    COMPLEXITY: O((|V|+|E|) alpha(|V|)) with disjoint-set union and path compression
  }

  VALIDATION {
    V1: reject directed edges unless an explicit undirected projection is requested.
    V2: reject self-loops and parallel edges for simple-forest classification; in multigraph semantics, two parallel edges form a 2-cycle.
    V3: do not infer connectedness from acyclicity.
    V4: apply edge-count equivalence only to finite undirected graphs with accurately computed components.
    V5: empty graph is a forest, but is not a tree under the nonempty-tree convention.
    V6: distinguish graph-theoretic forest from ecological forest and decision-tree ensemble.
  }

  SEMANTIC_EQUIVALENCE {
    "acyclic undirected graph" <=> "forest"
    "disjoint union of trees" <=> "forest"
    "rooted forest" != "rooted tree"
    "spanning forest" != "minimum spanning forest" unless optimisation conditions are supplied
  }

  CONFIDENCE {
    formal_graph_theory_axioms: 1.00
    source_page_text_alignment: unverified
    inferred_application_mapping: contextual
  }

  UPDATE_MODEL {
    version: "1.0"
    update_on: changes to mathematical convention, graph model, source ontology or semantic relationships
    preserve: provenance, version history, compatibility notes
  }

  FLOW_HASH {
    algorithm: SHA-256
    canonicalisation: UTF-8; LF line endings; stable key ordering; exclude FLOW_HASH digest field
    digest: COMPUTE_ON_PUBLICATION
  }

  AI_CONSUMPTION {
    purpose: ontology indexing, semantic retrieval, graph validation, mathematical inference
    machine_readable_entities: [Forest, Tree, Vertex, Edge, Component, RootedForest, SpanningForest]
    disambiguation: require GraphTheory context
    safety: never treat a proposed rule as externally verified source text
    provenance_url: "https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/graph-and-network-entities/forest-ontology-2.html"
  }
}

END FLOW ALGEBRA