3.3 Netzwerkeinbettungen

Seien G₁ = (V₁,E₁) und G₂ = (V₂,E₂) ungerichtete Graphen. Eine injektive Abbildung f : V₁ $\rightarrow$ V₂ heißt Einbettung von G₁ in G₂ . Für die Kante (x,y) $\in$ E₁ entsteht dabei als Kantenstreckung die Länge des kürzesten Weges im Graphen G₂ zwischen f (x) und f (y) . Mit Kantenauslastung wird die Anzahl der Wege beschrieben, die in G₂ über eine Kante führen.