3 Die metrischen Parameter in Graphen
Definition
- Der Abstand zweier Knotenmengen in \(X, Y \in G\), geschrieben \(d_G(X, Y)\), ist die geringste Länge eines \(X-Y\) Weges in \(G\).
- Wenn es keinen Weg zwischen Knoten \(x, y \in E\) gibt, dann \(d_G(x, y) := \infty\).
Definition
- Diameter is the (shortest) distance between the farthest two vertices: \[\text{diam}(G) := \max_{x, y \in V} d_G(x, y)\]
- Ein Knoten ist zentral in \(G\), wenn sein größter Abstand zu den anderen Knoten möglichst klein ist: \[x\text{ ist zentral in }G \quad\Longleftrightarrow\quad x \in \argmin_{z\in V}\;\bigl(\max_{y\in V}d_G(z,y)\bigr)\]
- Dieser Abstand heißt Radius von \(G\): \[rad(G) := \min_{x \in V}\max_{y \in V} d_{G}(x, y)\]
Bemerkung
The diameter of the (abstract) graph is an upper bound on the diameter of the embedded graph, considered as a subset of \(\R^n\) for any n with edges of constant length. As if we could take two vertices of graph and „stretch“ the graph in this two directions. Its length would be bounded by the diameter. > Diameter and radius are not related to minimum, average or maximum degree if we say nothing about the order of the graph. However, graphs of large diameter and minimum degree must be large (larger than forced by each of the two parameters alone), and graphs of small diameter and maximum degree must be small.
Lemma 3.4
\[rad(G)\leq \text{diam}(G) \leq 2 \text{rad}(G).\]
Satz 3.5
Sei \(G\) ein Graph mit \(\text{diam}(G)\geq 4\) dann \(\text{diam}(\bar{G}) \leq 2\).
Korollar 3.6
Der Durchmesser eines nicht-triviales, selbskomplementäres Graphen \(G \cong \bar{G}\) ist \(2\) oder \(3.\)
Definition 3.7
Die Taillenweite (girth) \(g(G)\) von \(G\) ist die Länge eines kürzesten Kreises in \(G\). Der Umfang (circumference) \(u(G)\) von \(G\) ist die Länge eines längsten Kreises in \(G\). Enthält \(G\) keinen Kreis, so ist \(g(G) := \infty\) und \(u(G) := 0\).
Bemerkung
- Falls \(G\) mindestens einen Kreis enthält, gilt offensichtlich \(g(G) \leq u(G)\).
- Taillenweite (girth) g(G) ist die Länge eines kürzersten Kreises, der automatisch ein Untegraph ist.
- Umfang (Circumference) u(G) ist die Länge eines längsten Kreises, der dagegen ein Teilgraph, aber nicht notwendigerweise ein Untergraph ist.
Bemerkung
Die Taillenweite ist eine lokale Eigenschaft, der Umfang ist eine globale Eigenschaft:
- Graphen mit großer Taillenweite sehen lokal wie Bäume aus, also sie zumindest lokal keine kurzen Kreise haben. Ein echter Baum ist sozusagen das absolute Ideal dieses Konzepts, denn er hat überhaupt keine Kreise und deswegen hat man \(g(G) := \infty\) für Bäume.
- Die Bedingung \(u(G)=0\) schließt die Existenz von Kreisen beliebiger Länge im gesamten Graphen aus. Ein solcher Graph besitzt global keinerlei zyklische Teilstrukturen und ist folglich stets ein Wald.
Beispiel
- Peterson Graph hat \(g(G) = 5, u(G) = 6\),
- \(g(C_k) = u(C_k) = k\).
Satz 3.8
- Jeder Graph G enthalt einen Weg der Länge \(\delta(G)\).
- Wenn \(\delta(G) \geq 2\), enthält G einen Kreis der Lange mindestens \(\delta(G) +1\).
- Insbesondere: \(\delta(G) \geq 2 \Rightarrow u(G) \geq \delta(G) +1\).
(otherwise the path can be expended with an unvisited neighbor of \(x_k\))
Bemerkung
- Therefore, if a graph acyclic then there is at least one node \(v\) with \(d(v) \in \{0,1\}\).
- If a graph has large minimum degree, it contains long paths and cycles.
- Der kürzeste Kreis kann jedoch in Verhältnis zu \(\delta(G)\) beliebig lang sein.
Satz 3.9
Für jeden Graph, der einen Kreis enthält, gilt: \[g(G) \leq 2\ \text{diam}(G)+1\]
Beispiel
\[g(C_{2k+1}) = 2k + 1 = 2\ \text{diam}(C_{2k+1}) + 1\]
Definition 3.10
- Eine Kante in G, die zwei Knoten eines Kreises in G verbindet, aber nicht selbst die Kante des Kreises ist, ist eine Sehne.
- Ein Kreis ist sehnlos (chordless), wenn der keine Sehne besitzt.
Bemerkung
- Ein Kreis ist genau dann sehnlos, wenn er ein induzierter Teilgraph von G ist.
- Ein kürzester Kreis kann keine Sehne haben.