Kerne und Grundyfunktionen auf Bäumen

Michael Drmota Technische Universität Wien

Sei G = (E(G), V (G)) ein einfacher gerichteter Graph mit Knotenmenge E(G) und Kantenmenge V (G). Zu einer nichtleeren Teilmenge M ⊆ V (G) der Knoten bezeichne Γ^{+}(M) die Menge der Nachfolgerknoten, Γ^{−}(M) die Menge der Vorgängerknoten und Γ(M) = Γ^{+}(M) ∪ Γ^{−}(M). Eine Teilmenge I ⊆ V (G) der Knotenmenge heißt unabhängig (oder innenstabil), falls Γ(M) ∩ M = ∅ gilt, d.h. zwei Knoten aus I sind nicht adjazent. Eine Teilmenge D ⊆ V (G) der Knotenmenge heißt von außen stabil, fall Γ^{−}(M) ∪ D = V (G) erfüllt ist, mit anderen Worten, jeder Knoten, der nicht in D liegt, ist Vorgänger eines Knoten aus D. Ein Kern K ⊆ V (G) eines Graphen ist dann eine unabhängige und von außen stabile Teilmenge der Knotenmenge. Graphen, die einer Kern besitzen, können mit Hilfe einer Grundyfunktion (vgl. [Be]) noch feiner untersucht werden. Eine Grundyfunktion g : V (G) → N = {0, 1, 2, …} ist auf der Knotenmenge definiert und erfüllt für alle Knoten v ∈ V (G)

g(v) = min(N \ g(Γ^{+}({v}))).  (1)

Kerne sind dann genau die Urbilder g^{−1}({0}).

Nun müssen Kerne und Grundyfunktionen nicht immer existieren bzw. nicht eindeutig sein. Man kann allerdings zeigen ([To]), daß fast alle gerichtete Graphen einen Kern und damit eine Grundyfunktione besitzen. Besonders einfach ist die Situation jedoch in zyklenfreien Graphen, wo eine eindeutig bestimmte Grundyfunktion existiert.

In dieser Note soll das Verteilungsverhalten von Kernen und Grundyfunktionen in ebenen Wurzelbäumen beschrieben werden, wo alle Kanten von der Wurzel weg gerichtet sind. Und zwar sollen einfach erzeugte Baumfamilien F betrachtet werden. Sei φ(t) = 1 + φ_{1}t + φ_{2}t^{2} + ⋯ eine formale Potenzreihe mit nichtnegativen Koeffizienten φ_{i}. Einem ebenen Wurzelbaum T wird dann ein Gewicht (φ_{0} = 1)

ω(T) = ∏_{i≥0} φ_{i}^{D_{i}(T)},  (2)

wobei D_{i}(T) die Anzahl der Knoten von T mit Weggrad i bezeichnet, zugeordnet. Die erzeugende Funktion Y (x) = ∑_{n≥1} y_{n}x^{n} der Zahlen y_{n} = ∑_{|V (T)|=n} ω(T) erfüllt dann die Funktionalgleichung Y = xφ(Y). In F werden nun jene ebenen Wurzelbäume T mit ω(T) > 0 aufgenommen. Ist φ_{i} ∈ {0, 1}, so ist auch ω(T) ∈ {0, 1} und y_{n} ist die Anzahl der Bäume aus F der Größe n. Beispielsweise werden durch φ(t) = 1 + t^{2} die Menge der ebenen Binärbäume und durch φ(t) = 1 + t + t^{2} + ⋯ = 1/(1 − t) alle ebenen Wurzelbäume beschrieben.

Jeder ebene Wurzelbaum T, bei dem alle Kanten von der Wurzel w weg gerichtet sind, besitzt eine eindeutig bestimmte Grundyfunktion g. Sei d_{m,i}(T) = 1 (m = (m_{0}, m_{1}, …), i ≥ 0), falls g(w) = i gilt und für alle j ≥ 0 die Anzahl der Knoten v ∈ V (T) mit g(v) = j gleich m_{j} ist. Andernfalls sei d_{m,i}(T) = 0. Die erzeugenden Funktionen D_{i}(x, y) = ∑_{m,n} d_{mn,i}y^{m}z^{n} (y = (y_{0}, y_{1}, …), y^{m} = y_{0}^{m_{0}}y_{1}^{m_{1}} ⋯) der Größen d_{mn,i} = ∑_{|V (T)|=n} ω(T)d_{m,i}(T) und D(x, y) = ∑_{i≥0} D_{i}(x, y) erfüllen dann die formalen Funktionalgleichugen

Lemma 1.

∑_{i≥0} \frac{1}{y_{i}} D_{i}(x, y) = xφ(D(x, y))  (3)

D_{i}(x, y) = xy_{i} ∑_{J⊆{0,...,i−1}}(−1)^{|J|}φ(D(x, y) − D_{i}(x, y) − ∑_{j∈J} D_{j}(x, y)), i ≥ 0.  (4)

Es erscheint unmöglich, aus diesem i.a. unendlichen Funktionalgleichungssystem explizite Resultate zu erhalten. Es gelingt jedoch, mit analytischen Methoden asymptotische Aussagen über das Verteilungsverhalten der Werte der Grundyfunktionen zu gewinnen. Die Größen d_{mn} = ∑_{i≥0} d_{mn,i} erfüllen einen zentralen Grenzwertsatz mit relativ einfach zu bestimmenden Mittelwerten

δ_{n}^{(i)} = \frac{1}{y_{n}} ∑_{m} m_{i}d_{mn}.  (5)

Satz 1. Es sei der Konvergenzradius R der Potenzreihe φ(t) so groß, daß die Gleichung xφ′(x) = φ(x) eine Lösung 0 < τ < R besitzt. Damit besitzt auch das i.a. unendliche System

d_{i} = \frac{τ}{φ(τ)} ∑_{J⊆\{0,...,i−1\}}(−1)^{|J|}φ (τ − d_{i} − ∑_{j∈J} d_{j}) , i ≥ 0.  (6)

eindeutig bestimmte nichtnegative Lösungen d_{i} mit ∑_{i≥0} d_{i} = τ, und die Mittelwerte δ_{n}^{(i)} sind dann für jedes i ≥ 0 asymptotisch durch

δ_{n}^{(i)} = \frac{d_{i}}{τ} n + O(1)  (7)

gegeben.

Etwas einfacher wird die Situation, wenn es ein i_{0} gibt, sodaß für alle i ≥ i_{0} φ_{i} = 0 ist. Für jeden Baum T aus F ist dann die Grundyfunktion g strikt durch i_{0} beschränkt. Demnach ist d_{i} = 0 für i ≥ i_{0} und das i.a. unendliche System (6) reduziert sich auf ein endliches.

Betrachte man etwa die Familie der Binärbäume mit φ(t) = 1 + t^{2}, so bestimmt man ohne Schwieriegkeiten τ = 1, d_{0} = 2 − \sqrt{2} = 0.585 …, d_{1} = (2\sqrt{2} − 1)/7 = 0.261 … und d_{2} = (5\sqrt{2} − 6)/7 = 0.153 . . .. Daraus ermittelt man den mittleren Wert der Grundyfunktion zu 0d_{0} + 1d_{1} + 2d_{2} = (12\sqrt{2} − 13)/7 = 0.567 . . ..

Es fällt auf, daß in diesem Beispiel d_{0}/τ > 1/2 gilt, was übrigens ein Spezialfall der folgenden allgemeinen Eigenschaft ist.

Lemma 2. Für i ≥ 0 gilt

d_{i} > ∑_{j>i} d_{j}.  (8)

Da Kerne gerade jene Teilmengen der Knotenmengen sind, wo die Grundyfunktion den Wert 0 annimmt, ist (d_{0}/τ)n > n/2 etwa die mittlere Größe eines Kernes. Kerne besitzen aber sonst keine innere Struktur, da wegen der Unabhängigkeit der von einem Kern induzierte Teilgraph keine Kanten besitzt, also vollkommen unzusammenhängend ist. Um jedoch einem besseren Überblick bekommen zu können, empfiehlt es sich Komplemente von Kernen V (T) \ K zu betrachten. Die induzierten Teilgraphen der Komplemente besitzen die Struktur eines Waldes, wo die Komponenten nicht unbedingt nur aus einem Knoten bestehen müssen. Über diese Kompoenten läßt sich folgendes aussagen.

Satz 2. Sei F eine einfach erzeugte Familie von Bäumen, wo alle Kanten von der Wurzel weggerichtet sind. Weiters sei der Konvergenzradius R von φ(t) so groß, daß die Gleichungen xφ′(x) = φ(x) und x(φ′(d_{0} + x) − φ′(d_{0})) = φ(d_{0} + x) − φ(d_{0}) positive Lösungen 0 < τ, ϑ < R besitzen. (d_{0} sei wie oben definiert.) Dann ist die mittlere Anzahl g_{n}^{(j)} der Komponenten der Größe j (der Komplemente der Kerne) in Bäumen der Größe n asymptotisch durch

g_{n}^{(j)} = μ_{j}n + O(1)  (9)

gegeben, wobei

μ_{j} = \frac{φ′(τ − d_{0})}{φ(τ)} (\frac{τ}{φ(τ)})^{j} \frac{1}{j}[t^{j−1}](φ(d_{0} + t) − φ(t))^{j}  (10)

ist. Die mittlere Anzahl der Komponenten ist

\frac{τ − d_{0}}{φ(τ)} φ′(τ − d_{0}) + O(\frac{1}{n})  (11)

und die mittlere Größe einer Komponente

\frac{φ(τ)}{τφ′(τ − d_{0})} + O(\frac{1}{n}).  (12)

Hingegen ist die mittlere Größe der größten Komponente in Bäumen mit n Knoten

\frac{log n}{log \frac{φ′(τ)}{φ′(d_{0}+ϑ)−φ′(d_{0})}} + O(log log n).  (13)

Die für den Beweis notwendigen Methoden werden in [BD1] bereitgestellt, wo auch explizite Resultate gewonnen werden können. Verwandte Resultate findet man auch in [BD2]. Literatur

[Be] C. Berge, Graphes and Hypergraphes, Dunod, Paris, 1970.

[To] J. Tomescu, Almost all Digraphs Have a Kernel, Discr. Math. 84 (1990), 181–192.

[BD1] G. Baron and M. Drmota, Distribution Properties of Induced Subgraphs of Trees, Ars

Combinatoria, zur Publikation eingereicht.

[BD1] G. Baron und M. Drmota, Die Komponentenverteilung von gesättigten Teilgraphen in

Baumfamlien, Séminaire Lotharingien de Combinatoire, 25^{e} session, zur Publikation eingereicht.

Michael Drmota, Abteilung für Diskrete Mathematik, Technische Universität Wien, Wiedner Hauptstraße 8–10/118, A-1040 Wien, Österreich.