Weighted Graph Ontology

FLOW ALGEBRA
TITLE: Weighted Graph Ontology
DOMAIN: Discrete Mathematics / Graph Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/weighted-graph-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
STATUS: Mathematical reference model; source page not independently verified

1. PURPOSE
Represent weighted graphs as typed mathematical structures, supporting explicit weight semantics, graph traversal, optimisation, provenance, validation and AI reasoning.

2. TYPED ENTITIES
Graph := (V, E, directed: Boolean, multigraph: Boolean)
Vertex := uniquely identified node v in V
Edge := (edge_id, source: Vertex, target: Vertex)
WeightDomain := numeric domain D (e.g. non-negative real numbers)
WeightFunction := w: E -> D
WeightedGraph := (V, E, w, directed, weight_semantics)
Walk := finite alternating sequence of vertices and incident edges
Path := walk with no repeated vertices (unless stated otherwise)
Cycle := closed path with at least one edge, using the applicable graph convention
WeightSemantics := cost | distance | duration | capacity | strength | probability | custom
AlgorithmResult := (value, witness, assumptions, provenance)

3. RELATIONSHIPS
HAS_VERTEX(Graph, Vertex)
HAS_EDGE(Graph, Edge)
CONNECTS(Edge, Vertex, Vertex)
HAS_WEIGHT(Edge, Weight)
HAS_WEIGHT_SEMANTICS(WeightedGraph, WeightSemantics)
IS_PATH_IN(Path, WeightedGraph)
OPTIMISES(AlgorithmResult, Objective)
DERIVED_FROM(AlgorithmResult, InputGraph)

4. CONSTRUCTION
flow BUILD_WEIGHTED_GRAPH(V, E, w, directed, semantics):
  require all edge endpoints belong to V
  require w is defined for every edge in E
  require each w(e) belongs to declared WeightDomain
  return WeightedGraph(V, E, w, directed, semantics)

5. WEIGHTED OPERATIONS
flow PATH_WEIGHT(P, w):
  require P is a valid finite walk in the graph
  require weights are additive for the declared objective
  return SUM(w(e) for every edge occurrence e traversed by P)

flow SHORTEST_PATH(G, s, t):
  require s,t in V and additive edge-cost semantics
  if all edge weights are non-negative: use Dijkstra or equivalent
  else: use Bellman-Ford or equivalent for finite graphs
  if a reachable negative-weight cycle can reach t: return UNBOUNDED_BELOW
  if t is unreachable: return UNREACHABLE
  return minimum-cost walk and its cost

flow MINIMUM_SPANNING_TREE(G):
  require G is finite, undirected, connected, and edge-weighted
  return a spanning tree T minimising SUM(w(e) for e in T)

flow MINIMUM_SPANNING_FOREST(G):
  require G is finite and undirected
  return a minimum spanning tree for each connected component

flow MAXIMUM_FLOW(G, s, t):
  require G is a finite directed flow network
  require non-negative capacities on edges
  require s != t
  return feasible maximum s-t flow and its value

6. ALGEBRAIC AND STRUCTURAL LAWS
PATH_CONCATENATION: weight(P ++ Q) = weight(P) + weight(Q) when endpoints match and weights are additive.
NON_NEGATIVE_PATH: if all traversed edge weights >= 0, then path weight >= 0.
MST_EDGE_COUNT: a spanning tree of a finite connected graph with |V| >= 1 has |V|-1 edges.
UNDIRECTED_SYMMETRY: for a single undirected edge {u,v}, its weight does not depend on endpoint order.
SHORTEST_PATH_OPTIMALITY: every subpath of a shortest path is shortest between its endpoints, provided a finite optimum exists and additive costs are used.
RELABELLING_INVARIANCE: graph isomorphisms preserving weights preserve weighted path costs and optimisation values.

7. SEMANTIC DISTINCTIONS
WEIGHT is not inherently COST: large weights may mean stronger affinity, higher capacity, or greater probability.
MINIMUM_SPANNING_TREE is not SHORTEST_PATH_TREE in general.
DIRECTED_WEIGHTED_GRAPH is not equivalent to UNDIRECTED_WEIGHTED_GRAPH.
NEGATIVE_WEIGHT is permitted in shortest-path models, but not in standard non-negative capacity models.
ZERO_WEIGHT does not mean ABSENT_EDGE.

8. INFERENCE RULES
IF edge e in E AND w(e) = k THEN HAS_WEIGHT(e,k).
IF walk P contains edges e1,...,en AND weights are additive THEN PATH_WEIGHT(P) = SUM_i w(ei).
IF graph is finite, undirected and connected THEN a minimum spanning tree exists for real-valued edge weights.
IF graph has non-negative additive edge costs THEN Dijkstra's algorithm is applicable.
IF a negative-weight cycle is reachable from s and can reach t THEN no finite minimum s-t walk cost exists.

9. VALIDATION
CHECK unique vertex and edge identifiers.
CHECK every edge endpoint is in V.
CHECK weight function totality on E and domain membership.
CHECK directedness and parallel-edge conventions.
CHECK units and semantics (e.g. kilometres vs minutes).
CHECK shortest-path algorithm preconditions, unreachable targets and negative cycles.
CHECK spanning-tree connectedness and undirectedness.
CHECK capacity non-negativity for flow problems.
CHECK that claimed optimal solutions include verifiable witnesses where practical.

10. SEMANTIC_EQUIVALENCE
weighted_network ~ weighted_graph WHEN nodes, edges, direction and weights have matching interpretations.
edge_cost ~ edge_weight ONLY WHEN cost semantics are explicitly declared.
weighted_adjacency_matrix ~ weighted_graph representation ONLY WITH a documented absent-edge sentinel, loop and multiedge policy.

11. CONFIDENCE
mathematical_definitions: 1.00 (under stated conventions)
algorithmic_conclusions: 1.00 WHEN preconditions and verification hold
source_page_alignment: UNVERIFIED
empirical_edge_weights: SOURCE_DEPENDENT

12. FLOW_HASH
HASH_INPUT := canonicalise(V, E, directed, edge_ids, w, units, semantics, version)
FLOW_HASH := SHA256(UTF8(HASH_INPUT))
NOTE: Compute on actual canonical data; no fabricated digest is supplied.

13. UPDATE_MODEL
ON vertex_added_or_removed: validate endpoints, rebuild affected graph structures and invalidate dependent results.
ON edge_added_or_removed: recompute impacted paths, trees and flows.
ON weight_changed: check units, semantics and algorithm assumptions; invalidate affected optimisation results.
ON semantics_changed: require revalidation of all dependent conclusions.
PRESERVE provenance, version history and calculation assumptions.

14. AI_CONSUMPTION
INPUT: typed weighted graph, query, weight semantics, constraints and provenance.
PROCESS: validate -> select compatible algorithm -> calculate -> verify witness -> explain assumptions.
OUTPUT: result, graph version, algorithm, feasibility status, confidence and traceable reasoning.
FAIL_CLOSED: reject unsupported units, invalid endpoints, missing weights or incompatible optimisation semantics.

15. EXAMPLE
V = {A,B,C}
E = {(A,B),(B,C),(A,C)}
w(A,B)=2; w(B,C)=3; w(A,C)=8
semantics = additive non-negative travel cost
PATH_WEIGHT(A->B->C)=5
SHORTEST_PATH(A,C) = (A->B->C, cost=5)

END FLOW ALGEBRA