Deterministische Irrfahrten auf Graphen

Inhaltsverzeichnis

1 Einleitung

2 Einordnung in die Literatur

3 Graphentheoretische Grundlagen

4 Die deterministische Irrfahrt[Abbildung in dieser Leseprobe nicht enthalten]in der Eckenversion
4.1 Die deterministische Irrfahrt [Abbildung in dieser Leseprobe nicht enthalten] auf Bäumen
4.2 Die deterministische Irrfahrt [Abbildung in dieser Leseprobe nicht enthalten] auf vollständig bipartiten Graphen Ka,b

5 Die deterministische Irrfahrt[Abbildung in dieser Leseprobe nicht enthalten]in der Kantenversion
5.1 Die deterministische Irrfahrt[Abbildung in dieser Leseprobe nicht enthalten]auf Bäumen
5.2 Die deterministische Irrfahrt[Abbildung in dieser Leseprobe nicht enthalten]auf vollständigen Graphen Kn

6 Zusammenfassung

Literatur

Abbildungsverzeichnis

Mein besonderer Dank gilt meinem Betreuer Dr. Jens Schreyer, Christopher Löbens und Geraldine Utech für die verdienstvolle Aufgabe mich zu motiv_ieren, Ellen Buch- berger für die Hinweise zur Textgestaltung, meiner Familie, die mich bis zum heutigen Tag unterstützt hat, und Gott, der es überhaupt erst so weit hat kommen lassen.

1 Einleitung

Die Idee für diese Arbeit stammt von Prof. Armin Mikler 2007, der nach einem (möglichst deterministischen) Algorithmus suchte, der jede Ecke eines unbekannten Graphen mindestens einmal besucht und danach zur Ausgangsecke zurückkehrt. Insbesondere steht für diesen Algorithmus kein beliebig großer Speicher zur Verfügung, der durch die Irrfahrt mitgeführt wird, um den gesamten Graphen zu speichern. Die Fragestellung wäre dann triv_ial: Es wäre keine Markierung des Graphen notwendig, sondern der Graph würde als Ganzes gespeichert.

Aus dieser Grundidee entstanden die beiden deterministischen Irrfahrten:[Abbildung in dieser Leseprobe nicht enthalten]in der Eckenversion und[Abbildung in dieser Leseprobe nicht enthalten] in der Kantenversion. Die deterministische Irrfahrt[Abbildung in dieser Leseprobe nicht enthalten]wählt von der Startecke aus eine benachbarte Ecke und im Anschluss immer die Ecke, die am seltensten besucht wurde, außer alle Ecken wurden gleich oft besucht, dann wird die nächste Ecke ausgewählt entsprechend einer zuvor festgesetzten Reihenfolge unter den Ecken. Die Irrfahrt endet, wenn die Startecke zum zweiten Mal erreicht wird.

Die deterministische Irrfahrt[Abbildung in dieser Leseprobe nicht enthalten] wählt von der Startecke aus eine benachbarte Kante und im Anschluss immer die Kante, die am seltensten besucht wurde, außer alle Kanten wurden gleich oft besucht, dann wird die nächste Kante ausgewählt entsprechend einer zuvor festgesetzten Reihenfolge unter den Kanten. Die Irrfahrt endet, wenn die Startecke zum zweiten Mal erreicht wird.

Die beiden Irrfahrten sind - wie Abschnitt 4 bzw. 5 näher erläutern - im Allgemeinen nicht erfolgreich in ihrer Zielsetzung alle Ecken des Graphen zu erreichen, außer auf Bäumen mit dem Grad der Startecke[Abbildung in dieser Leseprobe nicht enthalten]. Es ergeben sich neue Fragestellungen: Wird die Startecke zum zweiten Mal erreicht und ist die Irrfahrt somit endlich? Welchen Weg legt die Irrfahrt maximal zurück? Außerdem ergibt sich die Frage, ob es überhaupt einen Algorithmus geben kann, der durch reines Zählen der Besuche der Ecken bzw. Kanten das Netzwerk vollständig absuchen und danach zur Startecke zurückkehren kann.

Die dargestellten deterministischen Irrfahrten haben am Rande mit den aus der Literatur bekannten Irrfahrten zu tun, weisen allerdings gegenüber den in Abschnitt 2 genannten Irrfahrten die Besonderheit auf, dass jeder ihrer Schritte eindeutig festgelegt ist und es sich somit nicht um randomisierte Algorithmen handelt.

2 Einordnung in die Literatur

Den Begriff ”RandomWalk“(deutsch:Irrfahrt)führteKarlPearson¹⁹⁰⁵ erstmalig ein, indem er nach einer Lösung für folgendes Problem fragte:

“A man starts from a point O and walks l yards in a straight line; he then turns through any angle whatever and walks another l yards in a second straight line. He repeats this process n times. I require the probability that after these n stretches he is at a distance between r and r + dr from his starting point, O.” ([PEA05])

Pearson erhielt kurz darauf von Lord Rayleigh eine Antwort, die das Problem für große n zurückführt auf eine Überlagerung von n Schwingungen gleicher Frequenz und gleicher Amplitude, deren Phase zufällig verteilt ist (vgl. [PEA05]). Er folgert daraus:

“The lesson of Lord Rayleigh’s solution is that in open country the most probable place to find a drunken man who is at all capable of keeping on his feet is somewhere near his starting point!” ([PEA05])

Seit diesen Anfängen hat sich das Gebiet der Irrfahrten rasant entwickelt, sodass allein in den Jahren 2007 bis 2015 das TIB-Portal (https://www.tib.eu/ - Einsichtnahme: 08.03.2016) im Fachbereich Mathematik an die 8000 Arbeiten zum Schlagwort ”Ran- dom Walk“ liefert. Heute werden Irrfahrten nicht nur in der Biologie oder Physik als Lösungskonzepte erfolgreich angewendet:

Online-Händler wollen ihren Kunden in der nicht zu überschauenden Menge an Produkten eine kleine Auswahl an Produkten empfehlen, die am wahrscheinlichsten zu den Vorlieben des Kunden passen. Die entsprechenden Empfehlungsdienste ( ”Recom- mender Systems“) nutzen dann Irrfahrten, um im bipartiten Graphen aus Nutzern und Produkten neue Produkte vorzuschlagen. (vgl. [COO[14]) So z.B. der Online-Händler ”Amazon“:

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.1: Empfehlungsdienst des Online-Händlers

Irrfahrten können genutzt werden, um den Algorithmus ”Amazon“ ”PageRank“der ”Google Search“ für die Ecken eines Netzwerks auszurechnen (vgl. [ATI[13]) und damit Sucher- gebnisse der Suchmaschine ”Google“inihrerReihenfolgeundRelevanzzuordnen:

Abbildung in dieser Leseprobe nicht enthalten

Abb.2.2: Suchergebnisliste der Suchmaschine

Irrfahrten können genutzt werden, um Verbindungen in sozialen Netzwerken vorher- zusagen und vorzuschlagen (vgl. [BAC11]), z.B. für ein Konto des sozialen Netzwerks ”Facebook“.

Im Gegensatz zu den im Folgenden dargestellten deterministischen Irrfahrten be- trachtet László Lovász in seiner Zusammenfassung ”Randomwalksongraphs:A survey.“([LOV[93]) ausschließlich Irrfahrten, die dadurch entstehen, dass von einer Ecke aus alle benachbarten Ecken mit gleicher Wahrscheinlichkeit gewählt werden. Dabei ist ein Startpunkt gegeben; von dort wird ein zufälliger Nachbar ausgewählt, zu dem sich die Irrfahrt weiterbewegt. Danach wird wiederum ein zufälliger Nachbar aus- gewählt, zu dem sich die Irrfahrt weiterbewegt usw. Die Irrfahrt sei definiert wie folgt: Die Irrfahrt starte an einer Ecke v 0. Wenn der t -te Schritt die Ecke vt erreicht, bewegt sich die Irrfahrt mit der Wahrscheinlichkeit [Abbildung in dieser Leseprobe nicht enthalten] z u einem Nachbarn von vt. Diese Folge zufälliger Ecken charakterisiert Lovász demzufolge als endliche, zeit-reversible Markow-Kette. (vgl. [LOV93])

Die klassische Theorie der Irrfahrten beschäftigt sich mit Irrfahrten auf einfachen, aber unendlichen Graphen, wie Gittern. Es ergeben sich Fragen wie: Kehrt die Irrfahrt mit Wahrscheinlichkeit 1 zum Startpunkt zurück? Kehrt die Irrfahrt unendlich oft dorthin zurück? (vgl. [LOV93]) So zeigt ein - für weitere Forschung bahnbrechender - Satz von Pólya 1921: Eine Irrfahrt auf einem d-dimensionalen Gitter kehrt (mit Wahrscheinlichkeit 1) unendlich oft zum Startpunkt zurück, wenn d = 1 oder d = 2, aber nur endlich oft, wenn d ≥ 3. (vgl. [POL21], 150)

Weitere und aktuellere Ergebnisse finden sich u.a. in der 2006 überarbeiteten Version des Buches ”Randomwalksandelectricnetworks“([DOY[06])vonPeterDoyleundLau- rie Snell. Die Autoren zeigen den Zusammenhang zwischen Irrfahrten und der Theorie elektrischer Netzwerke und argumentieren wesentlich mit Rayleighs Monotoniegesetz (”Rayleigh’sMonotonicityLaw“)ausderTheorieelektrischerNetzwerke:Werdendie Widerstände eines Stromkreises erhöht, kann der effektive Widerstand R eff zwischen zwei beliebigen Punkten nur steigen. Werden die Widerstände gesenkt, kann der effektive Widerstand nur sinken. (vgl. [DOY06], 54)

Eine aktuelle Publikation in dieser Richtung bildet Wolfgang Woess’ ”RandomWalks on Infinite Graphs and Groups“ aus dem Jahr 2000, worin er als Zustandsraum der Markow-Kette diskrete aber unendliche Graphen und Gruppen (durch ihren Cayleygra- phen) zugrunde legt. Woess behandelt Transienz/Rekurrenz, Abklingen und asympto- tisches Verhalten von Übergangswahrscheinlichkeiten, Fluchtrate, Konvergenz im Un- endlichen zu einer Schranke und harmonische Funktionen. (vgl. [WOE[00], v_iii) Als ein wesentliches Werkzeug in der Betrachtung von Markow-Ketten nutzt Woess den Spektralradius. (vgl. [WOE00], 81f.) Als Verallgemeinerung des obigen Satzes von Pólya zeigt er einen lokalen zentralen Grenzwertsatz für Gitter. (vgl. [WOE00], 139f.) Die Ergebnisse über unendliche Graphen werden noch erweitert durch das Konzept transfiniter Graphen, bei denen zwei Kanten durch einen unendlich langen Weg verbunden sein können. (vgl. [ZEM96], 12f.)

Nach den Anfängen der klassischen Theorie der Irrfahrten kamen neue Betrachtungen hinzu über allgemeinere, aber endliche Graphen. Die in diesem Zusammenhang un- tersuchten Aspekte waren gegenüber den unendlichen Graphen quantitativer: Welchen Weg legt die Irrfahrt zurück, bevor sie zur Startecke zurückkehrt? Wie lang ist die Irr- fahrt, bis alle Ecken erreicht wurden? Wie lang ist sie, bis eine bestimmte Ecke erreicht wurde? Wie schnell konvergiert die Verteilung der Irrfahrt zu ihrer Grenzverteilung? (vgl. [LOV93]) Eine Zusammenfassung dieser Ergebnisse bis 1993 findet sich bei Lovász in [LOV93]:

Er gibt Ergebnisse an für die ”accesstime“bzw. ”hittingtime“[Abbildung in dieser Leseprobe nicht enthalten], die die erwartete Zahl an Schritten darstellt, bevor die Ecke j besucht wird, wenn man von der Ecke i startet. Die ”commutetime“bezeichnetdenErwartungswertfürdenWegvonEcke i zu Ecke j und wieder zurück:[Abbildung in dieser Leseprobe nicht enthalten]. Die erwartete Anzahl an Schritten, um jede Ecke zu erreichen, berechnet er in der ”covertime“.Die ”mixingrate“hingegenbildet ein Maß, wie schnell die Irrfahrt konvergiert zu ihrer Grenzverteilung.

Eine wichtige Motivation für diese Theorien über endliche Graphen bildet die Nutzung von Irrfahrten als Algorithmus. Denn Irrfahrten können genutzt werden, um ”verbor- gene“ Bereiche großer Mengen zu erreichen, und um zufällige Elemente großer und komplizierter Mengen zu erzeugen, z.B. perfekte Matchings in einem Graphen. (vgl. [LOV 93] Weitere Ergebnisse zu diesen Aspekten finden sich in der 2014 überarbeiteten, aber unfertigen Monografie ”ReversibleMarkovChainsandRandomWalksonGra- phs“([ALD 14]) von Dav_id Aldous und James A. Fill, die insbesondere auch auf die algorithmischen Anwendungen eingeht, sowie in [DOY 06].

Eine gewisse, wenn auch kleine Ähnlichkeit zu den hier dargestellten deterministischen Irrfahrten bildet der ”self-avoidingwalk“aus[LOV 93],denndiebeschriebenendeter- ministischen Irrfahrten vermeiden - wie der ”self-avoidingwalk“-dieWiederholung einer Ecke bzw. Kante, solange noch ungenutzte Nachbarn vorhanden sind. Weitere Ergebnisse zum ”self-avoidingwalk“findensichinNealMadras,GordonSlade: ”The Self-Avoiding Walk“([MAD 93]) von 1993. Signifikantere Ähnlichkeiten zu den hier dargestellten deterministischen Irrfahrten kommen in der Literatur nicht vor.

3 Graphentheoretische Grundlagen

Definition 1. Ein Graph ist ein Paar G = (V, E) disjunkter Mengen mit E ⊆ [ V ]² ; die Elemente von E sind also 2-elementige Teilmengen von V . Die n Elemente [Abbildung in dieser Leseprobe nicht enthalten] von V seien die Ecken des Graphen G, die m Elemente [Abbildung in dieser Leseprobe nicht enthalten]von E seine Kanten.

Eine Ecke v_i und eine Kante e inzidieren miteinander und hei ß en inzident, wenn v_i ∈ e gilt. Die beiden Ecken einer Kante sind ihre Endecken, und die Kante verbindet diese Ecken. Eine Kante {v_i, v_j } sei kurz bezeichnet mit v_iv_j (oder v_j v_i). Die Menge [Abbildung in dieser Leseprobe nicht enthalten] aller mit v inzidenten Kanten sei bezeichnet mit [Abbildung in dieser Leseprobe nicht enthalten]. (vgl. [Graphentheorie], 2)

Zwei Ecken v_i, v_j von G sind adjazent oder benachbart in G und hei ß en Nachbarn von- einander, wenn v_iv_j ∈ E (G) ist. Zwei Kanten e = f sind benachbart, falls sie eine ge- meinsame Endecke haben. Sind je zwei Ecken von G benachbart, so hei ß t G vollständig . Der vollständige Graph auf n Ecken sei bezeichnet mit Kn. (vgl. [Graphentheorie], 3)

Definition 2. Die Menge der Nachbarn einer Ecke v sei bezeichnet mit N (v) . Der Grad dG (v) = d (v) einer Ecke v gibt die Anzahl |E (v) | der mit v inzidenten Kanten an. Die Zahl Δ(G) := max {d (v) |v ∈ V } hei ß t Maximalgrad. (vgl. [Graphentheorie], 5)

Definition 3. Der Abstand zweier Eckenmengen X, Y in G ist die geringste Länge eines X − Y -Weges in G; existiert kein solcher Weg, so sei ihr Abstand unendlich. Den Abstand zweier einzelner Ecken x und y bezeichnen wir mit dG (x, y) . Der gr öß te Abstand zweier Ecken in G ist der Durchmesser diam(G) von G. ([Graphentheorie], 9)

Definition 4. Ein Kantenzug K der Länge l = k in einem Graphen G ist ei- ne nicht leere Folge[Abbildung in dieser Leseprobe nicht enthalten]von abwechselnd Ecken und Kanten aus G mit[Abbildung in dieser Leseprobe nicht enthalten]für alle i < k. (vgl. [Graphentheorie], 11) Da alle hier betrachteten Graphen schlicht sind, schreiben wir auch [Abbildung in dieser Leseprobe nicht enthalten]. Ein Kantenzug hei ß e geschlossen, wenn er in der Startecke endet. Der Grad im Kantenzug dK (v_i) gebe an, wiev_iele ein- gehende und ausgehende Kanten die Ecke v_i innerhalb des Kantenzugs K besitzt. Der Grad einer Kante im Kantenzug dK (ei) gebe an, wie oft die Kante ei im Kantenzug K auftritt.

Definition 5. Ein zusammenhängender Graph, der keinen Kreis enthält, ist ein Baum . Ein Wurzelbaum enthält eine ausgezeichnete Ecke, die Wurzel. Alle anderen Ecken vom Grad 1 au ß er der Wurzel sind seine Blätter . (vgl. [Graphentheorie], 14)

Definition 6. Ein Graph G = (V, E) hei ß t bipartit, wenn eine Partition von V in zwei Teile existiert, so dass die Endecken einer jeden Kante von G in verschiedenen Partitionsklassen liegen: Ecken aus der gleichen Klasse dürfen nicht benachbart sein. Ist G ein bipartiter Graph, in dem je zwei Ecken aus den beiden verschiedenen Klas sen benachbart sind, so hei ß t G vollständig bipartit . Sind a und b die Mächtigkeiten seiner zwei Partitionsklassen, so sei dieser (bis auf Isomorphie eindeutig bestimmte) Graph mit Ka,b bezeichnet. (vgl. [Graphentheorie], 18) Die Partitionsklasse der Mächtigkeit a sei mit A bezeichnet, die der Mächtigkeit b mit B. Die Elemente aus A seien[Abbildung in dieser Leseprobe nicht enthalten], die Elemente aus B hingegen [Abbildung in dieser Leseprobe nicht enthalten]

Definition 7. Ein offener Eulerzug ist ein Kantenzug, der alle Kanten des Graphen genau einmal enthält und nicht geschlossen ist. Ein geschlossener Eulerzug enthält alle Kanten des Graphen genau einmal und endet in der Startecke.

4 Die deterministische Irrfahrt - in der Eckenversion

Definition 8. Eine deterministische Irrfahrt[Abbildung in dieser Leseprobe nicht enthalten]auf dem Gra phen G mit der Startecke [Abbildung in dieser Leseprobe nicht enthalten]und einer Familie von Abbildungen[Abbildung in dieser Leseprobe nicht enthalten]

Abbildung in dieser Leseprobe nicht enthalten

sei eine Folge von Kantenzügen[Abbildung in dieser Leseprobe nicht enthalten] die schrittweise entstehe:

Abbildung in dieser Leseprobe nicht enthalten

[...]