While this submission is a draft, it cannot be used by other submissions.

Optimality under uniform traversal times

Lax330177.UniformCosts · concepts/Lax330177/UniformCosts.lean · lax-330177

definition

Loading review…

Sign in with ORCID

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

    Definition

    With constant traversal time c, elapsed time equals total internal waiting plus c times the number of hops. At c = 0, fastest and minimum-waiting paths coincide. At c = 1 a hop contributes one unit even if the path never waits.

    • Elapsed time splits into travel and waiting. If every available traversal takes c time units, every feasible path has elapsed time equal to its total internal waiting time plus c times its number of hops.
    • Zero traversal time. With uniform traversal time zero, a feasible path is fastest exactly when it minimizes total internal waiting time.
    • Unit traversal time. With uniform traversal time one, a feasible path is fastest exactly when it minimizes the sum of its hop count and its total internal waiting time.
    Concept map
    6 concepts; 7 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax330177.OptimalPaths
    2
    3/-!
    4---
    5title: Optimality under uniform traversal times
    6type: definition
    7---
    8With constant traversal time c, elapsed time equals total internal waiting plus
    9c times the number of hops. At c = 0, fastest and minimum-waiting paths coincide.
    10At c = 1 a hop contributes one unit even if the path never waits.
    11
    12- [Elapsed time splits into travel and waiting.](Lax330177Proofs.UniformCosts.elapsed_eq.html) If every available traversal takes c time units, every feasible path has elapsed time equal to its total internal waiting time plus c times its number of hops.
    13- [Zero traversal time.](Lax330177Proofs.UniformCosts.zero_optima.html) With uniform traversal time zero, a feasible path is fastest exactly when it minimizes total internal waiting time.
    14- [Unit traversal time.](Lax330177Proofs.UniformCosts.unit_optima.html) With uniform traversal time one, a feasible path is fastest exactly when it minimizes the sum of its hop count and its total internal waiting time.
    15-/
    16namespace Lax330177.UniformCosts
    17open Lax330177.Representations Lax330177.OptimalPaths
    18variable {n : ℕ} {G : Graph n} {q : Query G}
    19def Uniform (q : Query G) (c : ℕ) := ∀ t u v, G.edge t u v → q.transit t u v = c
    20
    21end Lax330177.UniformCosts
    22

    Discussion

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

    Loading discussion…