Baumbestand

Die Arborizität eines ungerichteten Graphen ist die minimale Anzahl von Wäldern , in die seine Kanten partitioniert werden können . Äquivalent dazu ist sie die minimale Anzahl von Spannwäldern, die benötigt werden, um alle Kanten des Graphen abzudecken. Der Satz von Nash-Williams liefert notwendige und hinreichende Bedingungen dafür, wann ein Graph k -arborisch ist.

Die Abbildung zeigt den vollständigen bipartiten Graphen K_{_4,4} , wobei die Farben eine Partitionierung seiner Kanten in drei Wälder darstellen. K _{_4,4} kann nicht in weniger Wälder partitioniert werden, da jeder Wald mit seinen acht Knoten höchstens sieben Kanten besitzt, während der gesamte Graph sechzehn Kanten aufweist – mehr als doppelt so viele wie ein einzelner Wald. Daher beträgt die Arborizität von K_{_4,4} drei.

Die Arborizität eines Graphen ist ein Maß dafür, wie dicht der Graph ist: Graphen mit vielen Kanten haben eine hohe Arborizität, und Graphen mit hoher Arborizität müssen einen dichten Teilgraphen haben.

Genauer gesagt: Da jeder Wald mit n Knoten höchstens n − 1 Kanten besitzt, ist die Arborizität eines Graphen mit n Knoten und m Kanten mindestens n − 1. Außerdem kann die Arborizität der Teilgraphen eines Graphen nicht größer sein als die des Graphen selbst; äquivalent dazu muss die Arborizität eines Graphen mindestens der maximalen Arborizität eines seiner Teilgraphen entsprechen. Nash-Williams bewies, dass sich diese beiden Tatsachen kombinieren lassen, um die Arborizität zu charakterisieren: Bezeichnen wir die Anzahl der Knoten bzw. Kanten eines beliebigen Teilgraphen S des gegebenen Graphen mit n_{_S} und m _{_S}, so ist die Arborizität des Graphen gleich n_S = n_S + m_S + ...${\displaystyle \lceil m/(n-1)\rceil }$${\displaystyle \max _{S}\{\lceil m_{S}/(n_{S}-1)\rceil \}.}$

Jeder planare Graph mit Knoten hat höchstens Kanten, woraus sich nach der Nash-Williams-Formel ergibt, dass planare Graphen höchstens drei Arborizität besitzen. Schnyder verwendete eine spezielle Zerlegung eines planaren Graphen in drei Wälder, den sogenannten Schnyder-Wald , um eine geradlinige Einbettung jedes planaren Graphen in ein Gitter kleiner Fläche zu finden .${\displaystyle n}$${\displaystyle 3n-6}$

Die Arborizität eines Graphen lässt sich als Spezialfall eines allgemeineren Matroid-Partitionierungsproblems [1] darstellen, ^{bei dem die} Elemente eines Matroids als Vereinigung einer kleinen Anzahl unabhängiger Mengen ausgedrückt werden sollen. Folglich kann die Arborizität mit einem Polynomialzeitalgorithmus berechnet werden ( Gabow & Westermann 1992 ). Der derzeit beste exakte Algorithmus berechnet die Arborizität in einer Zeit von O(n^n), wobei n die Anzahl der Kanten im Graphen ist. ${\displaystyle O(m{\sqrt {m}})}$${\displaystyle m}$

Näherungen für die Arborizität eines Graphen lassen sich schneller berechnen. Es existieren lineare 2-Approximationsalgorithmen. ^{[ 2 ] [ 3 ]}

Die Anarborizität eines Graphen ist die maximale Anzahl von kantendisjunkten, nichtazyklischen Teilgraphen, in die die Kanten des Graphen partitioniert werden können.

Die Stern-Arborizität eines Graphen ist die Größe des minimalen Waldes, in den sich die Kanten des Graphen zerlegen lassen, wobei jeder Baum ein Stern ist (ein Baum mit höchstens einem Nicht-Blattknoten). Ist ein Baum selbst kein Stern, beträgt seine Stern-Arborizität zwei, wie man durch die Zerlegung der Kanten in zwei Teilmengen mit geraden bzw. ungeraden Abständen von der Wurzel erkennen kann. Daher ist die Stern-Arborizität eines jeden Graphen mindestens gleich der Arborizität und höchstens doppelt so groß.

Die lineare Arborizität eines Graphen ist die minimale Anzahl linearer Wälder (einer Menge von Pfaden), in die die Kanten des Graphen unterteilt werden können. Die lineare Arborizität eines Graphen steht in engem Zusammenhang mit seinem maximalen Grad und seiner Steigungszahl .

Die Pseudoarborizität eines Graphen ist die minimale Anzahl an Pseudowäldern , in die seine Kanten partitioniert werden können. Äquivalent dazu ist sie das maximale Verhältnis von Kanten zu Knoten in einem beliebigen Teilgraphen des Graphen, aufgerundet auf eine ganze Zahl. Wie die Arborizität besitzt auch die Pseudoarborizität eine Matroidstruktur, die eine effiziente Berechnung ermöglicht ( Gabow & Westermann 1992 ).

Die Subgraphendichte eines Graphen ist die Dichte seines dichtesten Subgraphen.

Die Dicke eines Graphen ist die minimale Anzahl planarer Teilgraphen, in die seine Kanten zerlegt werden können. Da jeder planare Graph die Arborizität drei besitzt, ist die Dicke eines jeden Graphen mindestens gleich einem Drittel und höchstens gleich der Arborizität.

Die Entartung eines Graphen ist das Maximum des minimalen Grades eines Knotens in allen induzierten Teilgraphen des Graphen. Die Entartung eines Graphen mit Arborizität ist mindestens gleich 1 und höchstens gleich 2. Die Färbungszahl eines Graphen, auch bekannt als seine Szekeres-Wilf-Zahl ( Szekeres & Wilf 1968 ), ist stets gleich seiner Entartung plus 1 ( Jensen & Toft 1995 , S. 77f.). ${\displaystyle a}$${\displaystyle a}$${\displaystyle 2a-1}$

Die Stärke eines Graphen ist ein Bruchteil, dessen ganzzahliger Anteil die maximale Anzahl disjunkter Spannbäume angibt, die in diesem Graphen gezeichnet werden können. Sie ist das duale Packungsproblem zum Überdeckungsproblem, das durch die Baumstruktur aufgeworfen wird. Die beiden Parameter wurden von Tutte und Nash-Williams gemeinsam untersucht.

Die fraktionale Arborizität ist eine Verfeinerung der Arborizität, da sie für einen Graphen wie folgt definiert ist : Mit anderen Worten, die Arborizität eines Graphen ist die Aufrundung der fraktionalen Arborizität. ${\displaystyle G}$${\displaystyle \max\{m_{S}/(n_{S}-1)\mid S\subseteq G\}.}$

Die (a,b)-Zerlegbarkeit ist eine Verallgemeinerung der Arborizität. Ein Graph ist (a,b) -zerlegbar, wenn seine Kanten in Mengen partitioniert werden können , von denen jede einen Wald induziert, außer einer, die einen Graphen mit maximalem Grad induziert . Ein Graph mit Arborizität ist (a,b )-zerlegbar. ${\displaystyle (a,b)}$${\displaystyle a+1}$${\displaystyle b}$${\displaystyle a}$${\displaystyle (a,0)}$

Die Baumzahl ist die minimale Anzahl von Bäumen, die die Kanten eines Graphen abdecken.

Die Arborizität taucht in der Goldberg-Seymour-Vermutung auf .