Lax Lean Archive

Uniqueness and diagonal entries of shortest-path distances

Lax489179.DistanceProperties · concepts/Lax489179/DistanceProperties.lean · lax-489179

proven

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Lemma

    The distance specification has at most one answer for each ordered pair. In a graph with no negative cycle every diagonal answer is zero. An encoded nn by nn distance matrix contains exactly n2n^2 words.

    Concept map
    7 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 3 statements. Each proof establishes one of them relative to its assumptions.

    1 diagonal_zero proven

    2 distance_unique proven

    3 matrix_length proven

    Lean source view on GitHub

    1import Lax489179.WeightedAPSP
    2
    3/-!
    4---
    5title: Uniqueness and diagonal entries of shortest-path distances
    6type: lemma
    7---
    8The distance specification has at most one answer for each ordered
    9pair. In a graph with no negative cycle every diagonal answer is zero.
    10An encoded nn by nn distance matrix contains exactly n2n^2 words.
    11-/
    12
    13namespace Lax489179.DistanceProperties
    14
    15open WeightedAPSP
    16
    17axiom distance_unique (G : Graph) (u v : Fin G.vertices) (a b : Option ℤ)
    18 (ha : Distance G u v a) (hb : Distance G u v b) : a = b
    19
    20axiom diagonal_zero (G : Graph) (h : NoNegativeCycle G) (v : Fin G.vertices) :
    21 Distance G v v (some 0)
    22
    23axiom matrix_length (n : ℕ) (matrix : Fin n → Fin n → Option ℤ) :
    24 (encodeMatrix n matrix).length = n * n
    25
    26end Lax489179.DistanceProperties
    27
    Show ProofShow ProofShow Proof
    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…