O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

8.2 A Class of Tree-Like Graphs and Some of Its Derivatives

8.2.1 Preliminary Notions

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, LV, LE, μ) be a connected weighted undirected graph whose vertices are uniquely labeled by the function LV : VLV for the set of vertex labels LV and whose edges are uniquely labeled by LE : ELE for the set of edge labels LE. Throughout this chapter we assume that LVimages0 and LEimages0, that is, vertices and edges are labeled by ordinal numbers. Further, we assume that this numbering is consecutive. Next, let D = (V, A, LV, LE, ν) be an orientation of G, that is, a connected weighted digraph such that ∀aA : ν(a) = μ(e) ⇔ e = {in(a), out(a)} ∈ E. By ≤VL2v (≤EL2E) we denote the natural order of LVimages0 (LEimages0) such that for all a, bLV (a, bLE): a <V b (a <E b) iff aV b (aE b) and ab. This allows ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required