EIG012 Ungerade Grade

0:00 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.

0:18 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.

0:37 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.

1:22 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.

2:05 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.

2:31 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.

2:50 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.

3:13 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.

3:30 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.

3:50 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.

4:13 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.

4:29 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.

4:44 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.

5:09 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.

5:30 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.

5:50 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.

6:08 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.

6:25 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.

6:44 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.

7:02 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.

7:20 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.

7:45 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.

8:08 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.

8:31 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.

8:56 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.

9:12 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.

9:34 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.

9:52 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.

10:17 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.

10:39 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.

10:59 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.

11:17 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.

11:37 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.

12:01 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.

12:29 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.

13:05 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.

13:31 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.

13:53 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.

14:13 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.

14:35 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.

15:03 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.

15:31 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.

15:59 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,

16:43 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.

17:09 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.

17:35 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.

18:01 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.

18:31 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.

19:11 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.

19:39 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.

20:07 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.

20:31 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.

20:55 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.

21:31 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.

21:51 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.

22:25 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.

23:07 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.

23:29 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.

23:51 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

24:39 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.

25:13 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.

25:47 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.

26:19 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!