In this section we briefly define two well-known notions that will be used throughout the chapter to introduce our graph model. This relates to paths in undirected and directed graphs as well as to the notion of geodesic distance in weighted graphs.

**Definition 8.1 (Preliminaries)** Let *G* = (*V*, *E*, *L*_{V}, *L*_{E}, *μ*) be a connected weighted undirected graph whose vertices are uniquely labeled by the function *L*_{V} : *V* → *L*_{V} for the set of vertex labels *L*_{V} and whose edges are uniquely labeled by *L*_{E} : *E* → *L*_{E} for the set of edge labels *L*_{E}. Throughout this chapter we assume that *L*_{V} ⊂ _{0} and *L*_{E}⊂ _{0}, that is, vertices and edges are labeled by ordinal numbers. Further, we assume that this numbering is consecutive. Next, let *D* = (*V*, *A*, *L*_{V}, *L*_{E}, ν) be an orientation of *G*, that is, a connected weighted digraph such that ∀*a* ∈ *A* : ν(*a*) = *μ*(*e*) ⇔ *e* = {in(*a*), out(*a*)} ∈ *E*. By ≤_{V}⊂*L*^{2}_{v} (≤_{E}⊂*L*^{2}_{E}) we denote the natural order of *L*_{V} ⊂ _{0} (*L*_{E} ⊂ _{0}) such that for all *a*, *b* ∈ *L*_{V} (*a*, *b* ∈ *L*_{E}): *a* <_{V} *b* (*a* <_{E} *b*) iff *a* ≤_{V} *b* (*a* ≤_{E} *b*) and *a* ≠ *b*. This allows ...

Start Free Trial

No credit card required