Thomas Kahle
Wie versprochen geht es noch weiter mit der Graphentheorie, und zwar mit dem Problem auf einem Graphen eine möglichst große Teilmenge der Ecken zu finden, sodass der induzierte Teilgraph nur ungerade Grade hat. Das kann man sich auch so vorstellen, dass auf einer Party die Leute sich die Hände schütteln und man sucht am Ende eine möglichst große Gruppe von Leuten, in der sich untereinander nur ungerade oft die Hand geschüttelt wurde. Wer das Händeschütteln nicht mag, kann übrigens auch einfach Unterhaltungen nehmen, denn Graphentheorie abstrahiert alle Beziehungen, die zwischen zwei Ecken möglich sind. Ach ja, manchmal sage ich in der Folge auch „Vertizes“ zu den Ecken.
- Quanta-Artikel zu odd subgraphs
- Yair Caros Paper
- Lineare Schranke von 2020
- Paper von Scott: No 1., No. 2
Feedback gerne auf Mastodon @Eigenraum@podcasts.social, an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite.
Verwandte Folge:
Automatisch generiertes Transkript (nicht geprüft)
So, hallo zusammen, ich begrüße euch hier zu einem neuen Eigenraum, schön, dass ihr eingeschaltet habt wieder und an dieser Stelle gleich vorneweg mal danke für das nette Feedback zur letzten Folge, also die Grafentheorie hat anscheinend einigen da draußen gefallen und ich kann gleich sagen, dass es heute nochmal um Grafentheorie gehen wird.
Vorausschicken will ich mal, dass ich eigentlich nie ein Thema komplett abhandeln kann, schon gar nicht so ein Thema wie Grafentheorie, das ist einfach viel zu groß, ich picke mir eigentlich immer so einen Aspekt heraus, der mir irgendwie gefällt oder an dem man irgendwas schönes sehen kann über Mathematik und arbeite mich dann an dem ab.
Aber die Leute, die mir Empfehlungen geschickt haben oder Tipps, ich nehme das alles gerne an, ich schreibe mir das alles auf und irgendwie wird sich das immer verarbeiten lassen dann in einer späteren Folge, also danke für das viele Feedback und alle Hinweise und Ideen.
So, Grafentheorie, in der letzten Folge, also Eigenraum 11, haben wir schon mal ein bisschen was über Grafen besprochen, das könnt ihr euch also anhören, so ihr es denn noch nicht getan habt und zur Erinnerung, ein Graf, das ist so eine mathematische Struktur, die ganz einfach ist und ganz abstrakt, die besteht einfach nur aus einer Menge von sogenannten Ecken, das sind irgendwelche Dinge, die Paarbeziehungen eingehen können.
Und diese Paarbeziehungen, die speichern wir in den Kanten des Grafen und eine Kante ist einfach nur zwei Ecken und wenn wir jetzt also unsere Ecken haben und ein paar Kanten, dann speichern wir einfach nur, welche von den Ecken stehen in einer Beziehung.
Und so einen Grafen könnte man zum Beispiel malen, indem man für jede Ecke einen Punkt malt und für jede Kante einen Strich zwischen den zwei Punkten und da kriegt man ein schönes Bild von dem Grafen und der Begriff, der kommt vielleicht aus der Theorie der Polygone oder Polyeder, wo die wirklichen Ecken so eines Polyeders durch die Kanten verbunden sind und dann auch so ein Graf des Polyeders ersteht, aber das Konzept ist total vielfältig.
Da kann man alles mögliche mit abbilden, das ist eine Datenstruktur, die in der Informatik auch eine ganz wichtige Rolle spielt und in vielen praktischen Problemen auftaucht.
Zum Beispiel kann man denken an das Internet als Grafen, da ist eine Ecke ein Computer und eine Kante eine Netzwerkverbindung zwischen zwei Computern und zusammen bilden dann alle Computer der Welt einen großen Grafen und über den möchte man vielleicht irgendwas mal wissen.
So, jetzt gibt es irgendwie lauter Beispiele von Grafen, zum Beispiel der Graf, der alle Kanten hat, den nennt man den vollständigen Grafen.
Also man nimmt sich irgendeine Menge von Ecken und malt einfach alle Kanten hin.
Wie viele gibt es da eigentlich?
Das ist so ein Binomialkoeffizient.
Man fragt sich, wie viele Paare gibt es von Ecken.
Aus meinen sagen wir n Ecken und das ist der Binomialkoeffizient n über 2.
Kann man auch explizit ausrechnen, das ist n mal n minus 1 halbe.
Auf der anderen Seite des Spektrums steht der leere Graf.
Der leere Graf, der hat so seine Ecken und dann einfach gar keine Kanten.
Das gibt es auch und alles andere bewegt sich irgendwie dazwischen.
Da gibt es dann vielleicht noch bipartite Grafen, das sind Grafen, da kann man die Ecken in zwei Gruppen einteilen und alle Kanten, die es überhaupt gibt, gehen immer nur von der einen Gruppe zu der anderen Gruppe, aber nie innerhalb der Gruppe.
Das sind die sogenannten bipartiten Grafen.
Kreise hatten wir letztes Mal schon besprochen.
Das sind Grafen, wo die Kanten so einen Kreis bilden, also immer nacheinander kommen.
Das Ende von einer Kante ist der Anfang von der nächsten Kante und so wird ein Pfad beschrieben, der dann sich wieder schließt und ein Kreis ist.
Ein Graf ohne jegliche Kreise, in dem man niemals im Kreis laufen kann, den nennt man einen Baum.
Wenn man den hinmalt, sieht der auch so ein bisschen aus wie so ein Baum.
Das verzweigt sich nämlich immer nur und kommt niemals wieder kreisförmig zurück.
Und es gibt noch mehr so Naturterminologie in der Grafentheorie.
Zum Beispiel nennt man einen Wald, wenn man so mehrere Bäume nebeneinander tut, dann ist es ja auch wieder ein Graf, der eben aus diesen mehreren Bäumen besteht, die alle einzeln jetzt zu diesem ganzen Grafen zusammengefasst werden.
Das nennt man dann einen Wald.
So, aber jetzt will ich mal zu unserem heutigen Thema der ungeraden Grafentheorie kommen.
Und das habe ich gefunden in einem Artikel im Quanta Magazine, das ja immer ganz gut ist für eine mathematische Idee.
Und da wurde folgendes Partyspiel beschrieben.
Wieder mal ein mathematisches Partyspiel.
Es gibt also eine Party und wir werden gleich einen Grafen beschreiben und die Ecken von diesem Grafen sind die Leute, die auf der Party sind.
Also wir haben unsere Party, auf der sind Leute und es war jetzt für irgendwie vor Covid und die Leute schütteln sich die Hände.
Okay, die kommen auf die Party und schütteln ein paar Leute die Hände.
Und jetzt ist das Spiel auf der Party.
Jede Person soll versuchen, genau einer ungeraden Anzahl von Leuten die Hände zu schütteln.
Die ganze Gruppe gewinnt das Spiel, wenn es gelingt.
Wenn nach dem ganzen Händeschütteln jeder einer ungeraden Anzahl von Leuten die Hand geschüttelt hat.
Das kann man sich jetzt erstmal irgendwie überlegen, was man da für Strategien entwickeln könnte.
Also wenn keiner jemals irgendwie Hände schüttelt, weil gerade Pandemie ist oder so, dann verliert man.
Weil Null eben eine gerade Zahl ist und haben alle Null.
Also sollten die Leute schon mal irgendwie, um da zu gewinnen, anfangen Hände zu schütteln.
Zum Beispiel, wenn zwei Leute auf der Party sind, ist die Lösung ganz einfach.
Die beiden Leute schütteln die Hände, dann hat jeder einer anderen Person, nämlich der anderen Person, die Hand geschüttelt und das Spiel ist gewonnen.
Dann können wir nochmal auf drei Leute schauen.
Also bei drei Leuten nehmen wir mal eine erste Person.
Und die erste Person, die hat da Null. Das heißt, die schüttelt erstmal einer anderen Person die Hand.
Dann ist es schon gut.
Die andere Person ist jetzt auch versorgt. Die hat jetzt auch eine ungerade Anzahl.
Jetzt gibt es aber noch diese dritte Person.
Und schon haben wir verloren und können nicht mehr gewinnen.
Denn wenn die dritte Person jetzt einer von den beiden die Hand schüttelt,
dann hat sie zwar selbst eine ungerade Anzahl, nämlich 1.
Aber die Person, mit der sie die Hand geschüttelt haben, hat dann die 2.
Und das ist wieder eine gerade Zahl.
Und diese Person, die die 2 hat, hat dann schon allen anderen die Hand geschüttelt und kann keiner weiteren Person die Hand schütteln,
sodass die auf jeden Fall verliert und nicht mehr weiterkommt.
Bei vier Leuten funktioniert es wieder.
Da gibt es eine ganz einfache Idee.
Die vier Leute können sich nämlich einfach in Paare einteilen und das Problem so lösen.
Die teilen sich einfach in Paare ein.
Jedes Paar schüttelt sich die Hand und für alle ist gesorgt.
Und das sieht man sofort, dass es für jede gerade Anzahl geht.
Also das Partyspiel lässt sich für jede gerade Anzahl von Leuten mit einer sehr kleinen Anzahl von Händeschütteln lösen,
indem einfach man eine Person findet, die noch keine Hand geschüttelt hat und der die Hand schüttelt.
Ein Siebter bringt aber wieder ein Problem.
Ein Fünfter bringt auch ein Problem.
Das kann man jetzt mal so ein bisschen rumspielen.
Aber ich will vielleicht mal ein bisschen analytischer vorgehen,
um zu sehen, dass es bei einer ungeraden Anzahl von Leuten da ein Problem gibt.
Wenn wir jetzt zurücktreten und das Problem analysieren wollen,
dann sehen wir erstmal, dass es sich hier um ein Grafentheorie-Problem handelt.
Man kann die Party als Graf darstellen,
in dem die Personen die Ecken sind und die geschüttelten Hände die Kanten.
Weil das ja eben genau so eine Paarbeziehung ist,
wo zwei von den Personen miteinander in diese Paarrelation treten,
indem sie sich gegenseitig die Hand schütteln.
So, und jetzt kommt wieder der Grad ins Spiel,
den ich letztes Mal schon definiert habe in Eigenraum 11.
Der ist ja genau die Größe, die wir jetzt betrachten wollen in diesem Grafen.
Also wir suchen jetzt für unsere Party einen Grafen,
einen Händeschüttelgrafen nenne ich es mal,
in dem jeder Grad ungerade ist.
Der Grad einer Ecke in dem Grafen ist die Anzahl anderer Ecken,
mit der diese Ecke verbunden ist.
Jede Ecke hat einen Grad.
Ich zähle einfach, wie viele Kanten gehen aus der Ecke raus,
mit wie vielen anderen Ecken ist sie verbunden.
Und wir sollen jetzt einen Grafen konstruieren auf den Leuten unserer Party,
so dass jede Ecke ungeraden Grad hat.
Und unsere Vermutung ist,
wenn die Anzahl der Leute ungerade ist, geht das nicht.
Und wir wissen schon, wenn die Anzahl der Leute gerade ist, dann geht es.
Denn die können sich einfach in Paare einteilen,
so wie wir es eben schon gesehen haben.
So, und die Lösung ist jetzt ganz einfach.
Wenn man weiß, wie es geht,
man bildet mal die Summe über alle Gerade.
Sagen wir also mal, wir betrachten das Problem für sieben Personen
und irgendwie schütteln die jetzt die Hände.
Wir wissen noch nicht wie, aber wir nehmen mal an,
die haben jetzt irgendwie die Hände geschüttelt.
Und wir wollen zeigen, dass diese ungerade Bedingung nicht erfüllt sein kann.
Wenn wir das zeigen können, dann ist es nicht möglich
für diese Party mit sieben Leuten das Spiel zu gewinnen.
Und dazu betrachten wir die Gradsumme.
Also wir addieren die sieben Zahlen, die gerade sind.
Und die Behauptung, die ich jetzt mache,
ist, dass diese Gradsumme immer eine gerade Zahl ist.
Denn die Gradsumme ist auch gleich zweimal die Anzahl der Kanten,
die es überhaupt in dem Graphen gibt.
Und das ist ganz logisch, weil jede Kante zwischen zwei Ecken verläuft.
Das heißt, jede Kante wird genau zweimal gezählt.
Einmal bei der ersten Ecke, an die sie andockt,
und einmal bei der zweiten Ecke, an die sie andockt.
Das heißt, wenn ich alle Gerade über alle Ecken aufsummiere,
erhalte ich immer eine gerade Zahl.
Und die gerade Zahl ist zweimal die Anzahl der Kanten,
die ich in meinem Graphen habe.
Wenn ich jetzt das Spiel aber gewinnen würde,
wenn die Party von sieben Leuten das Spiel gewinnen würde,
dann würden die Gerade sieben ungerade Gerade sein.
Das sind zu viele Gerade.
Also sieben ungerade Zahlen werden addiert
und ergeben auch die Gradsumme.
Sieben ungerade Zahlen addiert,
ergeben aber wieder eine ungerade Zahl
nach den Rechenregeln für gerade und ungerade Zahlen.
Das heißt, das kann keine Gradsumme sein.
Die Gradsumme ist immer gerade.
Deswegen heißt sie ja Gradsumme.
So, Schluss mit diesem Wortspielen.
Also, ich hoffe, ihr konntet mitrechnen.
Sieben ungerade Zahlen, sieben ungerade Gerade,
ergeben immer eine ungerade Zahl,
aber die Gradsumme ist immer eine gerade Zahl.
Also ist das Problem genau für
eine gerade Anzahl von Leuten auf der Party lösbar
und für eine ungerade Anzahl nicht lösbar.
Und jetzt wollen wir mal ein bisschen
zur mathematischen Graphentheorie kommen
nach dieser Fingerübung.
In der Graphentheorie betrachtet man
üblicherweise große Graphen oder alle Graphen.
Also wir wollen ja in der Mathematik
ein universelles Gesetz finden.
Also wir wollen verstehen, wie die Graphen ticken.
Und deswegen müssen wir eine Aussage machen,
die für alle Graphen gilt.
Zum Beispiel den Graphen des Internets,
also einen riesigen Graphen.
Und wir wollen wissen, was dieser Graph
für Eigenschaften hat.
Wie funktioniert der Graph?
Wie findet man Wege in diesem Graphen?
Wo sollen neue Kanten hin,
damit irgendwas besser funktioniert?
Wo sind Schwachstellen?
Und so weiter und so fort.
Und Mathematik beantwortet meistens
nicht direkt diese Fragen,
sondern entwickelt eine Theorie
und diese Theorie gilt, will ich euch heute mal vorstellen.
Also, jetzt stellen wir uns vor,
wir haben einen großen Graphen,
der ist jetzt fest.
Den betrachten wir jetzt.
Einen beliebigen großen Graphen.
Zum Beispiel der Graph des Internets.
Und dann schauen wir uns
die Teilgraphen von dem an.
Wir schauen uns an, wie sehen Teile
von diesem Graphen aus.
Und da benutzt man den Begriff
des induzierten Teilgraphs.
Der geht so.
Anzahl von Ecken
aus meinem ursprünglichen großen Graphen
und dazu
alle Kanten, die zwischen meinen ausgewählten
Ecken verlaufen.
Zum Beispiel könnte ich so eine Kante
herausnehmen, indem ich einfach zwei Ecken
nehme, die verbunden sind.
Und wenn ich irgendeine Teilmenge
von Ecken nehme und genau alle
Kanten, die zwischen diesen Ecken verlaufen,
dann erhalte ich auch einen Graphen
und das nennt man den induzierten Teilgraph.
Und jetzt könnte ich
mein Spiel mit den ungeraden Graphen
von der Party für Teilgraphen
spielen. Mein großer Graph,
mit dem ich gestartet bin, ist
mit großer Wahrscheinlichkeit
wahrscheinlich kein solch ungerader
Graph. Das heißt, nicht alle
Ecken haben
ungeraden Grad. Ich könnte mich aber
fragen, finde ich vielleicht so einen
induzierten Teilgraphen, der ungerade
ist? Das könnte man
sich doch mal fragen. Findet man in jedem
Graphen einen induzierten Teilgraphen,
der ungerade ist? Das heißt, so dass
jede Ecke ungeraden Grad hat,
aber eben in diesem Teilgraphen.
Und eine kurze
Nachdenkenpause
bringt die Antwort hervor.
Ja, das ist ganz einfach.
Man muss einfach nur eine Kante nehmen,
indem ich zwei
Ecken nehme, die verbunden sind
durch eine Kante. Wenn ich sowas finde, also wenn
mein Graph irgendwie zumindest eine Kante hat,
dann kann ich das lösen. Es ist also
sehr leicht, so einen ziemlich
einfachen und langweiligen
ungeraden Teilgrafen zu finden.
Also fragt man sich vielleicht,
ob man auch große ungerade
Teilgrafen finden kann, also welche mit
möglichst vielen Vertizes.
Und es stellt sich heraus, dass
das ein schwieriges Problem
der Graphentheorie ist,
bzw. war.
Und wie es in der Mathematik immer so ist,
man kam da nicht voran
und hat erst mal verwandte Probleme betrachtet.
Also zum Beispiel könnte man sich auch mal fragen,
ob man gerade Teilgrafen finden kann.
Wobei ein gerader Teilgraf jetzt
einer ist, wo jeder Grad
gerade ist. Und das ist
relativ einfach zu lösen.
Ich will jetzt den Beweis nicht vorstellen,
aber er passt auf eine Seite.
Es gibt einen Beweis, der auf eine Seite passt
und den man auch verstehen kann.
Und das wurde in den 1960ern bewiesen,
zuerst von Tibor Galay,
dass man die Ecken jedes Graphen
in zwei Gruppen einteilen kann,
sodass, wenn ich diese beiden induzierten
Teilgrafen nehme,
die auf meinen zwei Gruppen entstehen,
dass ich dann jeweils
einen geraden Graphen habe.
Das ist möglich und ist
schon seit 1960 bekannt.
Das kann man auch mal ausprobieren.
Das ist wie ein neues Brettspiel vor mir.
Also man kann den Graphen
des Internets nehmen
und dann die Menge
der Computer in zwei Gruppen
einteilen, sodass
in jeder Gruppe,
wenn ich nur die Kanten betrachte,
die Netzwerkverbindungen, die
innerhalb der Gruppe sind und alle anderen
ignoriere, dass dann
jeder eine gerade Anzahl
an Nachbarn hat.
Ganz wichtig
dabei ist, dass null
eine gerade Anzahl ist.
Wenn ich zum Beispiel an meinen einen Computer denke,
der hier gerade vor mir steht,
der ist nur mit einem anderen Computer
verbunden, nämlich
meinem Router.
Dass er mit einem
anderen Computer verbunden ist.
Das heißt, damit
der in einem induzierten
Teilgrafen eine gerade Anzahl
Verbindungen hat, muss diese Kante weg.
Null ist die einzige Möglichkeit
für meinen Computer
eine gerade Anzahl Verbindungen zu haben,
weil die Anzahl Kanten, die übrig
bleibt, die von ihm ausgehen,
eine Teilmenge der Kanten ist,
die er jetzt schon in dem großen Graphen
des Internets hat.
Ich kann daraus folgern, wenn ich
meinen Graphen immer in diese zwei Gruppen
einteilen kann, sodass die beide
gerade Graphen induzieren,
dass dann einer von den beiden mindestens
die Hälfte der Ecken hat.
Also gibt es immer
einen geraden
Teilgrafen, der
die Hälfte der Ecken hat.
Also auch im Internet kann ich mindestens
die Hälfte, wahrscheinlich mehr Computer
auswählen, sodass
diese Gruppe, wenn man alle Kanten
hat, jeder eine gerade Anzahl von Kanten
hat. Wenn ich jetzt mal
praktisch darüber nachdenke, ist das wahrscheinlich
gar nicht so überraschend, denn es stehen
ja überall auf der Welt irgendwie so Endgeräte
rum und die heißen Endgeräte,
weil sie am Ende vom Internet sind und nur mit
ihrem Internetrouter
verbunden sind. Und wenn man die
Gruppe von diesen Endgeräten nimmt,
dann sind die alle nicht miteinander
verbunden. Also wenn ich diese Gruppe nehme
und ich frage mich jetzt, wie viele
von allen Computern im Internet das sind,
aber wahrscheinlich würde ich sagen, mehr
als die Hälfte sind
Endgeräte. Und wenn die Endgeräte
immer nur mit einem Router verbunden sind
und nicht untereinander, dann kann ich einfach diese Gruppe
der Endgeräte nehmen. Darauf wird der leere
Graph induziert
und dann habe ich so eine
gerade Gruppe. Man kann auch
abstrakt zeigen, dass es nicht
besser geht. Also man
kann zum Beispiel einen Graphen nehmen,
der nur so eine Schlange ist, ein Pfad.
Also eine Kante, an deren Ende noch eine
Kante, an deren Ende noch eine Kante, an deren Ende noch eine Kante
und so weiter.
Und da ist die
Einteilung, die einzige Einteilung
in zwei
gerade Teilgrafen
ist, alle Kanten zu unterbinden.
Indem man
als eine Gruppe nimmt, jeden
zweiten, jede zweite Ecke auf dem
Pfad und als andere Gruppe jede
andere zweite Ecke auf dem Pfad.
Denn wenn ich irgendwo eine Kante
nehmen würde, da das ein
Pfad ist, habe ich den Anfang
des Pfades drin und der hat eben
genau eine Verbindung
und das ist ungerade.
Eins ist ungerade.
Ein gerader Teilgraf ist auch
interessant, denn wenn er nicht verbunden ist, erlaubt er
einen Eulerkreis. Also kann man
damit zum Beispiel Eulerkreise finden
und hat dieses Problem mit den geraden
Grafen schon schön gelöst.
Aber was ist jetzt mit ungeraden Teilgrafen
und warum ist ungerade so viel schwieriger
als gerade? Und ungerade
ist viel schwieriger als gerade.
Das ist eben verrückt.
So 30 Jahre nach den 60ern, also
ungefähr in den 90ern, hat
J. R. Caro gezeigt, dass ein Graf mit
N-Ecken einen ungeraden
Teilgrafen der Größe Wurzel
N hat. Also
man kann Wurzel N
von den Ecken auswählen,
sodass dort ein ungerader
Teilgraf induziert wird.
Das ist schon ganz gut,
aber das fällt eben ab mit der Größe
und das ist schade. Also für die geraden
Teilgrafen hätte man ja eine
Konstante mal die Anzahl der Ecken.
In diesem Fall die Hälfte der Ecken.
Und hier, aber Wurzel aus der
Anzahl der Ecken, das fällt eben ab mit der Größe.
Also wenn ich eine Million Ecken habe, dann habe ich
eben nur noch einen ungeraden Teilgraf
der Größe 1000
oder um genauer zu sein, gibt es da auch
noch Konstanten in seiner Arbeit. Also eigentlich
409 habe ich da nochmal
ausgerechnet. Also wenn man
einen Grafen mit einer Million Ecken
hat, egal wie der gemalt ist,
findet man
einen ungeraden Teilgrafen
der Größe 409.
Zu beachten ist hierbei aber, dass wir
einen Grafen nehmen
müssen, in der jede
Ecke mindestens einen Nachbarn
hat. Wenn man den leeren
Grafen nimmt, dann kann man
keinen solchen induzierten Teilgrafen auswählen.
So ungefähr zehn Jahre
später gibt es dann
einige Veröffentlichungen von Scott,
die zeigen, dass man
die Vertizes eines Grafen nicht nur
in zwei Gruppen unterteilt,
sondern in mehr Gruppen.
Also er ändert
das Problem, statt
die Ecken des Grafen in zwei Gruppen
zu unterteilen, die
jeweils einen
ungeraden Teilgraf induzieren,
nimmt er jetzt mehrere Gruppen.
Er lässt jetzt eine beliebige Anzahl von Gruppen
zu. Also da würde zum Beispiel auch
diese Lösung, dass man
die Partygäste
in Paare einteilt
und jedes Paar stellt sich einmal
die Hand, wieder vorkommen.
Wenn man so eine Partition
hat, so eine Einteilung der
Ecken in diese Gruppen,
dann hat jede Zusammenhangskomponente,
also jedes zusammenhängende Stück,
eine gerade Anzahl an
Ecken. Denn das haben wir ja oben schon bei der
Party gesehen. Also notwendig,
damit das funktionieren kann bei einem
zusammenhängenden Stück, ist, dass man
eine gerade Anzahl an
Ecken hat.
Und die
Überraschung ist jetzt, dass diese Bedingung
auch hinreichend ist. Also unter
anderem, der Satz ist noch ein bisschen stärker,
wann immer man einen zusammenhängenden Grafen
hat, also einer, der nicht aus
mehreren Teilen besteht, die eigentlich nebeneinander gelegt wurden,
und der hat eine gerade
Anzahl an Ecken,
dann kann man die Ecken so in Gruppen
einteilen, dass jede Gruppe
ein ungerader Graf ist.
Dabei sind aber alle Gruppen
möglicherweise klein. Das ist jetzt der Preis,
den man dann dafür bezahlt.
Und schließlich
entwickelte sich die Sache weiter und
2020 gab es
dann einen Durchbruch.
Ferber und Krivelewig haben gezeigt,
dass eine lineare
Schranke möglich ist. Und das bedeutet,
eine Schranke von der Form, man kann
in jedem Grafen
eine konstante
mal Anzahl Ecken des ursprünglichen
Grafen große Gruppe
von Ecken finden, sodass der induzierte
Teilgraf
dann ungerade ist.
Und ihre Konstante ist 1 durch 10.000.
1 durch 10.000 ist nicht
unbedingt optimiert, die Arbeit ist auch
nur 8 Seiten lang, und
sie schreiben auch, dass man da
vielleicht noch ein bisschen optimieren kann, aber der
Durchbruch ist wirklich, dass
man eine Konstante hat, und die
nicht mehr von N abhängt. Also man nennt das
eine lineare Schranke.
Und ich verlinke euch das Paper natürlich,
und dann könnt ihr euch die 8 Seiten
selbst anschauen.
So, und damit ist dieses
Problem zumindest
einigermaßen zufriedenstellend gelöst.
Also diese lineare
Schranke, das war das, was man
haben wollte, und
ist jetzt damit glücklich.
Aber so ganz würde ich damit noch nicht aufhören,
denn in Wirklichkeit,
wenn man jetzt aber experimentell
daran geht und Experimente macht
und wirkliche Graphen anguckt,
dann findet man oft viel bessere
ungerade Teilgraphen.
Zum Beispiel mein Beispiel
aus dem Internet, wenn man
ausnutzt, was die konkreten Graphen
für eine Struktur haben, kann man
oft bessere Lösungen finden.
Und in der Mathematik muss man dann
weggehen von
der Lösung
für alle Graphen. Weggehen davon,
alle Graphen zu betrachten
und zulassen,
dass es vielleicht
einige konstruierte Beispiele gibt,
in denen mein Problem eine schwierige
Lösung oder keine gute Lösung hat,
und Aussagen
formulieren, die sagen, dass
es eine spezielle
Konfiguration benötigt, um
mein Spiel schlecht zu machen,
um meine Methode schlecht zu machen.
Und üblicherweise
führt das eben auf die Betrachtung
von Zufallsgraphen
oder Betrachtung von fast
allen Graphen. Und einen zufälligen
Graphen zu erzeugen, ist gar nicht so schwer.
Man nimmt einfach seine Ecken,
die man haben will, also
die entsprechende Anzahl, und dann würfelt
man einfach für jedes Paar von Ecken,
ob da eine Kante sein soll.
Zum Beispiel könnte man mit so einem
normalen Sechser würfeln, und immer wenn da eine
gerade Zahl kommt, dann macht man eine Kante.
Wenn da eine ungerade Zahl kommt, macht man keine Kante.
Das bedeutet also, dass jede Kante,
jede mögliche Kante, mit der Wahrscheinlichkeit
einhalb da ist. Das nimmt man
in Erdo-Schreni-Graphen für die Wahrscheinlichkeit
einhalb, und das ist eigentlich
ein allererstes, sehr einfaches
Modell für einen zufälligen Graphen.
Und so könnte man sich ja mal
diese Zufallsgraphen anschauen. Wie sieht denn das Problem
dafür aus? Und schon 2001
hat es Scott gezeigt,
dass für fast alle Graphen,
die so ausgewürfelt wurden,
also fast alle Graphen mit so
ungefähr der Hälfte der Kanten,
in seiner Arbeit drei Gruppen ausreichen.
Also er hatte ja
gezeigt, dass man
den Graphen in
Gruppen einteilen
kann. Wenn jede Zusammenhangskomponente
eine gerade Anzahl Vertizes hat, also
die notwendige Bedingung erfüllt ist,
dann kann man den Graphen in
Gruppen einteilen, sodass auf jeder Gruppe
ein ungerader
Teilgraph entsteht. Und
jetzt zeigt er, dass für diese
Zufallsgraphen drei Gruppen
reichen. Und jetzt gehen wir
rückwärts in der Zeit. Schon
1992, also davor,
hat er gezeigt, dass fast jeder
Graph mit der Hälfte aller Kanten,
also wieder so ein Zufallsgraph,
den ungeraden induzierten
Teilgraphen mit 77
Prozent der Ecken hat.
Also die Dauerkonstante ist
0,7729
mal Anzahl der Ecken
des Graphen. Also
ich ziehe einen Graphen mit meiner
Methode. Ich nehme eine große Anzahl
Ecken und für
diese mögliche Kante würfel ich
und mit Wahrscheinlichkeit ein Halb
mache ich eine Kante hin oder eben nicht.
Und das Ergebnis davon ist
ein Graph und
fast jeder Graph
hat einen ungeraden induzierten Teil
Graphen mit 0,7729
mal Anzahl
der Ecken, mit der ich gestartet bin.
Und das ist mal wieder ein schönes
Beispiel, wie sich mathematische Schwierigkeiten
erleichtern können, wenn man mal 5
gerade sein lässt. Also die
Schwierigkeiten mit dem ursprünglichen Problem,
die kommen daher,
dass es einzelne,
konstruierte, strukturierte
Beispiele gibt, die die
allgemeine Methode versauen.
Und wenn man diese Beispiele rauslässt,
indem man so mit einem zufälligen
Prozess Graphen erzeugt,
dann bekommt man viel bessere Ergebnisse.
Jetzt kann man natürlich noch fragen,
was hier fast jeder Graph
bedeuten soll und das ist eine Aussage, die
mit Wahrscheinlichkeiten und Grenzwerten zu tun hat
und ich fasse das jetzt mal ein bisschen salopp
so zusammen, dass wenn ihr jetzt
einen Graphen von der Größe des
Internets mit dieser
Methode erzeugt, dass
dann eine Teilmenge von 77%
der Computer einen ungeraden
induzierten Teil Graphen bilden.
Also es ist eine Aussage,
die gilt mit
immer höher werdender Wahrscheinlichkeit,
je größer
die Anzahl der Ecken ist, die ihr betrachtet.
Und damit will ich es euch jetzt mal
gut sein lassen. Ich hoffe,
ihr konntet ein bisschen mitknobeln
und damit wünsche ich euch
einen schönen Tag, einen schönen Abend,
einen guten Morgen, eine gute Nacht
und bis bald!