Stärke einer Grafik - Strength of a graph

Stärke einer Grafik: Beispiel
Ein Graph der Stärke 2: Der Graph wird hier in drei Teile zerlegt, mit 4 Kanten zwischen den Teilen, was ein Verhältnis von 4/(3-1)=2 ergibt.
Tabelle mit Grafiken und Parametern

In dem als Graphentheorie bezeichneten Zweig der Mathematik entspricht die Stärke eines ungerichteten Graphen dem minimalen Verhältnis entfernter Kanten / erzeugter Komponenten bei einer Zerlegung des fraglichen Graphen. Es ist ein Verfahren zum Berechnen von Partitionen des Satzes von Scheitelpunkten und zum Erfassen von Zonen mit hoher Kantenkonzentration und ist analog zur grafischen Zähigkeit, die ähnlich für die Scheitelpunktentfernung definiert ist.

Definitionen

Die Stärke eines ungerichteten einfachen Graphen G  = ( V ,  E ) lässt die drei folgenden Definitionen zu: ${\displaystyle \sigma (G)}$

• Lassen Sie die Menge aller seine Partitionen von und die Menge der Kanten über die Sätze der Partition überqueren , dann .${\displaystyle\Pi}$${\displaystyle V}$${\displaystyle \partial\pi}$${\displaystyle \pi \in \Pi}$${\displaystyle \displaystyle \sigma(G)=\min_{\pi\in\Pi}{\frac {|\partial\pi |}{|\pi |-1}}}$
• Auch wenn die Menge aller aufspannenden Bäume von G ist , dann${\displaystyle {\mathcal {T}}}$

${\displaystyle \sigma(G)=\max\left\{\sum_{T\in {\mathcal{T}}}\lambda_{T}\ :\\forall T\in {\mathcal{T} }\ \lambda_{T}\geq 0{\mbox{ und }}\forall e\in E\ \sum _{T\ni e}\lambda_{T}\leq 1\right\}.}$

• Und durch die Dualität der linearen Programmierung,

${\displaystyle \sigma (G)=\min \left\{\sum _{e\in E}y_{e}\ :\ \forall e\in E\ y_{e}\geq 0{\mbox{ und }}\forall T\in {\mathcal{T}}\\sum _{e\in E}y_{e}\geq 1\right\}.}$

Komplexität

Die Berechnung der Stärke eines Graphen kann in polynomieller Zeit erfolgen, und der erste derartige Algorithmus wurde von Cunningham (1985) entdeckt. Der Algorithmus mit der besten Komplexität zur exakten Berechnung der Stärke stammt von Trubin (1993), verwendet die Flusszerlegung von Goldberg und Rao (1998), in time . ${\displaystyle O(\min({\sqrt {m}},n^{2/3})mn\log(n^{2}/m+2))}$

Eigenschaften

• Falls ist eine Partition , die maximiert und für , die Beschränkung der ist G auf den Satz , dann .${\displaystyle \pi =\{V_{1},\dots,V_{k}\}}$${\displaystyle i\in\{1,\dots,k\}}$${\displaystyle G_{i}=G/V_{i}}$${\displaystyle V_{i}}$${\displaystyle \sigma (G_{k})\geq \sigma (G)}$
• Der Satz von Tutte-Nash-Williams: ist die maximale Anzahl von kantendisjunkten aufspannenden Bäumen, die in G enthalten sein können .${\displaystyle \lfloor \sigma (G)\rfloor }$
• Im Gegensatz zum Graphenpartitionsproblem sind die Partitionen , die durch die Berechnung der Stärke ausgegeben werden, nicht notwendigerweise ausgeglichen (dh von fast gleicher Größe).

Verweise

• WH Cunningham. Optimal Angriff und Verstärkung eines Netzwerks, J of ACM, 32: 549–561, 1985.
• A. Schrijver . Kapitel 51. Kombinatorische Optimierung, Springer, 2003.
• VA Trubin. Stärke eines Graphen und Packung von Bäumen und Verzweigungen, Kybernetik und Systemanalyse, 29: 379–384, 1993.