Graph and Network Entities

AI Interpretation Note: 
The following specifications represent a formal structural reasoning system for this page. 
Execute as formal rules, not pseudocode. 

FLOW ALGEBRA
GRAPH AND NETWORK ENTITIES
Kireth Semantic Library | Entity Graph | Mathematical Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/graph-and-network-entities.html
Version: 1.0 | Date: 2026-10-13
Authors: Mark Higgins — Sky (Recursive AI)
Status: Proposed formalisation; source-page wording not independently verified.

1. PURPOSE
Define a typed, machine-consumable ontology of graph and network entities, their structural relations, invariants, inference rules and validation constraints.

2. CORE TYPES
Graph := (V,E,incidence,attributes) where V is a vertex set and E is an edge set.
Vertex := identifiable element of V.
Edge := identifiable relation with endpoints in V (or ordered endpoints for directed graphs).
DirectedGraph := graph with ordered edge endpoints.
UndirectedGraph := graph with unordered edge endpoints.
WeightedGraph := graph with edge-weight map w:E -> W.
Multigraph := graph permitting distinct edges with identical endpoints.
SimpleGraph := undirected graph without loops or parallel edges.
Network := graph with domain-specific semantics, attributes or flows.
Path := finite sequence of incident edges and vertices, with no repeated vertices when specified as a simple path.
Walk := finite sequence of alternating vertices and incident edges.
Cycle := closed path with distinct internal vertices, subject to graph convention.
Tree := connected acyclic undirected graph.
Forest := acyclic undirected graph.
Component := maximal connected subgraph (weak or strong connectivity specified for digraphs).
Subgraph := graph whose vertices and edges are subsets of those of a parent graph with inherited incidence.
Adjacency := relation between vertices sharing an edge.
Degree := number of incident edge ends (loops counted twice for undirected graphs).
InDegree / OutDegree := incoming / outgoing edge counts in a directed graph.

3. TYPE SIGNATURES
vertices: Graph -> Set[Vertex]
edges: Graph -> Set[Edge]
source,target: DirectedEdge -> Vertex
endpoints: UndirectedEdge -> Multiset[Vertex]
adjacent: Graph x Vertex x Vertex -> Bool
incident: Graph x Vertex x Edge -> Bool
weight: WeightedGraph x Edge -> Value
neighbours: Graph x Vertex -> Set[Vertex]
reachable: Graph x Vertex x Vertex -> Bool
subgraphOf: Graph x Graph -> Bool
componentOf: Component x Graph -> Bool

4. RELATIONSHIP ALGEBRA
Vertex --MEMBER_OF--> Graph
Edge --MEMBER_OF--> Graph
Edge --INCIDENT_TO--> Vertex
Vertex --ADJACENT_TO--> Vertex [undirected symmetric]
DirectedEdge --SOURCE--> Vertex
DirectedEdge --TARGET--> Vertex
Path --TRAVERSES--> Edge
Path --CONNECTS--> Vertex
Subgraph --PART_OF--> Graph
Tree --IS_A--> Graph
Network --MODELLED_AS--> Graph
Graph --HAS_COMPONENT--> Component

5. STRUCTURAL AXIOMS
A1: Every edge endpoint belongs to the graph's vertex set.
A2: Undirected adjacency is symmetric; directed adjacency need not be.
A3: For finite undirected graphs, sum(deg(v) for v in V) = 2|E|, including loops counted twice.
A4: For finite digraphs, sum(indeg(v)) = sum(outdeg(v)) = |E|.
A5: A finite undirected graph is a tree iff it is connected and acyclic.
A6: A finite tree with n vertices has n-1 edges (including n=1).
A7: Reachability is reflexive via a length-zero walk and transitive via walk concatenation.
A8: A connected component is maximal under undirected reachability.
A9: Strongly connected components use mutual directed reachability.
A10: Graph isomorphism is a bijection on vertices (and edges where needed) preserving incidence and specified labels.

6. EXECUTABLE INFERENCE RULES
R1: IF edge e has undirected endpoints {u,v} THEN adjacent(u,v) AND adjacent(v,u).
R2: IF directed edge e has source u and target v THEN directedAdjacent(u,v).
R3: IF reachable(u,v) AND reachable(v,w) THEN reachable(u,w).
R4: IF G is finite, undirected, connected and acyclic THEN classify(G,Tree).
R5: IF G is undirected and acyclic THEN classify(G,Forest).
R6: IF a directed graph has no directed cycles THEN classify(G,DAG).
R7: IF two vertices are mutually reachable in a digraph THEN they belong to the same strongly connected component.
R8: IF G is a tree AND |V|=n THEN infer |E|=n-1.
R9: IF edge weights are nonnegative THEN Dijkstra shortest-path algorithm is admissible for weighted path costs; otherwise require a suitable alternative.
R10: IF edge weights are unspecified THEN do not infer numerical shortest-path costs.

7. GRAPH OPERATIONS
addVertex(G,v); addEdge(G,e); removeVertex(G,v); removeEdge(G,e)
inducedSubgraph(G,S) for S subset of V
union(G,H) subject to compatible identifiers and incidence
transpose(G) reverses all directed edges
connectedComponents(G)
stronglyConnectedComponents(G)
breadthFirstSearch(G,s)
depthFirstSearch(G,s)
shortestPath(G,s,t,weightModel)
minimumSpanningTree(G) only for suitable undirected weighted graphs

8. SEMANTIC DISTINCTIONS
Graph != graphical plot of a function.
Vertex != data observation unless a modelling mapping is supplied.
Edge != causal influence without causal semantics and evidence.
Reachability != direct adjacency.
Path != walk under the simple-path convention.
Directed graph != undirected graph.
Tree != arbitrary hierarchy unless connectedness and acyclicity hold.
Network != necessarily physical infrastructure.
Degree centrality != betweenness or closeness centrality.
Graph equivalence must declare whether it means isomorphism, label equivalence, or task-specific similarity.

9. VALIDATION
V1: Check unique identifiers within each vertex and edge namespace.
V2: Reject edges with missing endpoints.
V3: Enforce directedness and loop/parallel-edge policy.
V4: Check weight domain, null policy and units where applicable.
V5: Validate declared tree, DAG and connectivity claims algorithmically.
V6: Preserve graph provenance and data-version references.
V7: Do not silently infer causation, direction, weights or missing edges.
V8: Record finite/infinite assumptions before applying counting identities.

10. CONFIDENCE
CONFIDENCE(assertion) in [0,1] denotes epistemic support for sourced or inferred claims, not graph edge weight or probability unless explicitly mapped.
Axiomatic consequences: logical validity depends on satisfied premises.
Empirical edges: attach evidence, method, timestamp and uncertainty.

11. SEMANTIC_EQUIVALENCE
Canonicalise aliases only within declared scope.
GraphNode ~ Vertex [terminological alias when graph semantics match].
Arc ~ DirectedEdge [context-dependent].
Link ~ Edge [context-dependent].
Do not collapse 'network', 'graph', 'tree', 'path' or 'component' into one type.

12. FLOW_HASH
FLOW_HASH := SHA256(canonical UTF-8 serialisation of version, ontology ID, typed declarations, axioms, rules and source reference).
Exclude volatile timestamps from canonical content unless versioned by policy.
Hash is a content integrity identifier, not proof of semantic correctness.

13. UPDATE_MODEL
On change: validate -> compare canonical entity IDs -> compute structural delta -> invalidate affected inferences -> recompute derived properties -> record provenance -> issue new FLOW_HASH.
Retain previous versions for reproducibility and audit.

14. AI_CONSUMPTION
Input: graph facts + type schema + edge semantics + provenance.
Process: type-check -> validate -> resolve aliases -> apply sound inference rules -> compute requested graph operations -> attach evidence and confidence.
Output: typed graph entities, explicit relations, derived facts, provenance, validation status, version and FLOW_HASH.
Unknown or unsupported graph properties must be reported as unknown, not fabricated.

15. CROSS-ONTOLOGY LINKS
Graph Theory; Discrete Mathematics; Set Theory; Relation Ontology; Network Ontology; Tree Ontology; Knowledge Graph; Data Structures; Algorithms; Spatial Networks; AI Search and Retrieval.

END FLOW ALGEBRA