Direkt zum Inhalt

Lexikon der Mathematik: Bandweite

Bandbreite, Kenngröße eines Graphen.

Ist G numerierter Graph der Ordnung n, so nennt man

\begin{eqnarray}B(G)=\,\min \{{B}_{f}(G):f\,{\rm{Numerierung}}\,{\rm{von}}\,G\}\end{eqnarray} seine Bandweite. Dabei bedeutet f : ∈ (G) → {1, 2, …, n} eine bijektive Abbildung, also eine Numerierung von G und \begin{eqnarray}{B}_{f}(G)=\,{\rm{\max }}\{|f(u)-f\,(v)|:\,uv\in K(G)\}\end{eqnarray} die Bandweite oder Bandbreite von f.

Für einfache Graphen kann man die Bandweite mühelos bestimmen. Ist z. B. W ein Weg und C ein Kreis, so gilt B(W) = 1 und B(C) = 2. Natürlich gilt B(Kn) = n − 1 für den vollständigen Graphen Kn, und man berechnet \begin{eqnarray}B({K}_{p,q})=p+\lceil q/2\rceil -1\end{eqnarray}für den vollständigen bipartiten Graphen Kp,q, falls pq gilt. Das allgemeine Bandweitenproblem ist allerdings ein beweisbar schwieriges, ein NP-vollständiges Problem.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos