Merken

Spielperfekte Graphen

Zitierlink des Filmsegments

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
Magnifizenz ist jede Geste liebe Kolleginnen und Kollegen haben wird meine sehr geehrten Damen und Herren einmal möchte ich mich für die netten einleitenden Worte von Herrn erscheinen Hochstapler und vorher bedanken an das ist mir eine Ehre in diesem Fakultät Kolloquium vortragen zu dürfen ja mein Vertrag geht
Beispiel perfekte Grafen also zunächst einmal über Grafen hier auf der Titelfolie sehen Sie einige trafen nämlich alle trafen mit bis zu 5 Knoten und noch einige weitere den Grafen Inselsee in der Graphentheorie sind Strukturen die aus einer endlichen Menge aus Knoten besteht bestehen manche dieser Knoten sind durch kannten verbunden andere eben nicht also haben Sie einige Beispiele haben wir ja in gewisser Weise gibt es dieses Bild schon einer 1. 1 eine 1. Idee wie die Klassifikation Spiel perfekter Grafen sein könnten im Grunde schon die Lösung was damit genau gemeint ist und was später sagte Grafen überhaupt sind zufällig ich in den Vortrag hoffentlich erläutern können in neuen Vortrag
werd ich zunächst einmal auf das klassische Problem der der der Färbung von Grafen eingehen aber dieses Problem führt in natürlicher Weise zu der zu dem Begriff von perfekten trafen in gleicher Weise für den Mac Verbrecher Grafen Färbung spielen zu dem Begriff der Spiel perfekten kaufen und im 3. und 4. Teil meines Vortrags möchte ich dann auf die Klassifikation Spiel perfekter Grafen eingehen also dem Inhalt meiner Arbeit und dazu werde ich zunächst einmal die perfekte Grafen Klassifizierung haben was einen Basis-Schritte ist und dann noch auf eine andere SIM-Karte meiner Arbeit eingehen die daraus dann vom
betrachten Sie folgendes Stundenplan Probleme also Sie haben eine Schule und so oder so ein Stundenplan erstellt werden und sie haben gewisse Bedarf haben zum Beispiel Lehrer aber Klasse 1 unterrichten Lehrer aber soll aber auch Klasse 2 unterrichten Lehrer B Klasse 1 unterrichten und so weiter haben sie eine gewisse Menge an einen das haben ja und wie kann man dieses Problem modellieren also anhalten wird wird zunächst mal Lehrer Konflikte also Lehrer A kann nicht gleichzeitig Klasse 1 Klasse 2 Klasse 3 unterrichten und für die anderen Lehrer gilt das dasselbe deswegen machen wird ist zwischen diesen Bedarf fragen wo Konflikte bestehen eben kannten dann gibt es auch noch Klassenkonflikte dass die roten Kanten Klasse 1 soll nicht gleichzeitig von der war A B und C unterrichtet werden sondern eben in jeweils getrennten stimmen dann machen wir es auch wieder Kanten zwischen ja und was wir suchen ist eine konfliktfreie Stunden zuordnen aber das kann man so Modellierung ich verarbeitet die Bedarf es habe so das benachbarte benachbarte aber in unterschiedlichen Farben sind also die Farben entsprechend praktisch den Stunden und will aber gleichzeitig auch noch optimieren nämlich die Anzahl benötigter Stunden minimiert also hier könnte man so eine Lösung versehen also wenn man meinetwegen diese rote Stunde sich anguckt dass ist Lehrer ihren Klassen 4 gleichzeitig für Lehrer und ist ein Jahr und aus dieser Lösung kann man dann eben einen Lehrplan und entlassen Plan ablesen haben Sie für Ihr Leben ist der 1. Stunde als Lehrer aber Klasse 1 und Lehrer wie die Klasse 4 was im hervorgehoben hat und so weiter dann ist es noch ein anderes Problem aber die Stunden aber richtig zu kommunizieren so dass möglichst wenig Freistunden entstehen das ist aber jetzt nicht der Inhalt dieses Vertrages sondern einiges einfallen um das Währungsproblem wenn man das abstrakt modelliert ist es
einfach so haben gegeben einfach einen Grafen also ein Netzwerk in der Informatik spricht man oft von Netzwerken was das ist aber viel Kraft meint also wäre oder beziehungsweise und berichtet das Netzwerk ja und wir wollen in die Knoten so haben das benachbarte Knoten unterschiedliche Farben haben und dabei die Anzahl der verwendeten Farben minimieren das ist genau unser Problem in abstrakter Form ja wo tauchen solche Grafen Zahlungsprobleme auf eigentlich
immer in Situationen wo wir aber am Ressourcenkonflikte haben also waren verschiedenartige Ressourcen das können Arbeitskräfte sein also zusätzlich im engeren Sinne kein auch irgendwelche Personen Arbeiter Fahrer Schüler Lehrer seine Maschinen das können Fließband einhalten Erntemaschinen LKW oder auch Rheuma Produktionsorte Lagerkapazitäten Klassenräume sein und diese stehen miteinander in Konflikt und was versuchen ist eine konfliktfreie Färbung und mit wir wollen die Anzahl der Farben minimieren und die Farben des stehen immer für eine bestimmte Zielgröße meistens bei also bei den meisten Problemen sind welche Zeitfenster kann aber auch Lagerräume zum Beispiel sein oder sie wird im nächsten Beispiel sehen es können auch Funkfrequenzen sein möchte
ich hier ein Beispiel vorstellen die Funkfrequenzen Zuweisung stellen Sie sich vor Sie haben aber irgendwie eine Insel und da haben die gewisse Funkfrequenzen 15 drauf und den sollen Funkfrequenzen zugewiesen werden aber benachbarte Sender sollen sich nicht stören das heißt also wenn die nach einem Mann darstellen sollen die verschiedene Frequenzen ja und dadurch hat man hier auch wieder gewisse Konflikte die auftreten können und in einen Konflikt Grafen Jahr und dann möchte ich danke dann möchte ich eben diese diese Knoten dieses Konflikts Grafen Sofa-Abende dass möglichst wenig Farben verwendet werden also das heißt möglichst wenig Funkfrequenzen durchführen die von Frequenzen sind ja sehr wertvoll die in die DDR und da gibt es ja nicht so viele Stunden wach und ja und dann werden
eben das und habe es Probleme gibt und dass wir eine Lösung haben wenn wir jetzt diese Lösung betrachten dann stellen wir fest ok es gibt eine Lösung mit 4 Farben und geht es jetzt besser es geht in diesem Beispiel nicht besser denn wenn wir den oberen Teil des Grafen mal betrachten dann ist das ein vollständiger Graph mit 4 Knoten das ist unvorstellbar dass ein Graph in den jetzt verknoten benachbart sind und so ein Graph muss natürlich genau mit der Anzahl der Toten in vielen Farben gefärbt werden das heißt also weniger als 4 Farben ist hier nicht möglich und das kann man allgemein sagen also allgemeiner können wir sagen haben beim Fahren eines Grafen
benötigen wir mindestens so viele Fragen wie die Größe des größten vollständigen trafen den die Auftritt beträgt und diese Größen den wir in die schicken Zahlen von von dem Grafen und dann aber noch eine andere Definition nämlich die Mindestanzahl von Vorhaben die wir tatsächlich benötigen das ist die chromatische 2 jetzt aber einen zum Beispiel die lieblichen zahlen die ,komma zwar identisch aber allgemein in der Regel ist
es tatsächlich so dass es sich um chromatische zwar nicht größer ist als die klicken Zahl und das einfachste Beispiel ist der Kreis mit 5 Toten der offensichtlich klicken Teil 2 hat aber nicht mit 2 Farben gefärbt werden kann in verlangen und ungerade Anzahl von Knoten besitzt ja und das wir betrachten sind praktisch als Markgrafen aber wie in unserem Beispiel wo die Flecken vergleicht der chromatischen zahlbar und in unserem Beispiel galt noch eine Eigenschaft der darüber hinaus nämlich nicht nur für den Grafen selber galt dieser Eigenschaft sondern für jede für jeden in der 4. Teil Grafen haben war die Gegend zwar der chromatischen 2 also in der 4.
Teil davon sind trafen sich durch Löschen von Knoten das Orginal Grafen bekommen und solche Grafen in denen das Leben für jeden Interessierten Paragraphenwelt dienen und perfekt ja da möchte ich jetzt etwas zur Geschichte der perfekten Grafen sagen es gibt einen Satz in der Graphentheorie der praktisch die
gesamte Graphentheorie aber sehr stark entwickelt hat beziehungsweise die Suche nach den Beweis an dass nämlich die 4 Farben Vermutung jetzt 4 Farben-Satz die Vermutung wurde er erstmals in den fünfziger Jahren des 18. und und 19. Jahrhunderts gestellt und ein 1. Beweis versuchen macht da erkennen 1879 beweist wurde dann lange Zeit also 11 Jahre lang als er akzeptiert von der Fachwelt ist 1890 Archivo zeigte dass der beweisen grundlegende Fehler hat dass man mit dieser Ansatz eigentlich nur zeigen kann dass sich jeder Plan aber Graph mit 5 Farben färben kann also kleiner Markgraf heißt ein Graph der der sich in die Ebene zeichnen lässt ohne dass der bekannten Überkreuzungen entstehen und solche Grafen kann man den mit 5 Farben Farben und die Suche danach ob ich mit vierfachem vermisst das hat dann die Graphentheorie sehr befruchtet und haben ja schließlich haben Apple abgehackten kochen 1977 den vierfachen Satz bewiesen haben mit enormer Computerhilfe unter Beweis ist sehr undurchsichtig weil eben diese Computerhilfe natürlich nicht nicht gut ja akzeptierbar ist Robertson sein dass jemand Thomas andere 1997 einen etwas durchsichtige und beweist aber der immer noch am Computer eine Überprüfung benötigt angegeben und ja spätestens seit dem sollte man dann den vierfachen Satz auch akzeptieren so gingen in gleicher Weise wieder 4 Farben-Satz die gesamte Graphentheorie befruchtet hat
hat er an 2 Vermutungen von der die Theorie der perfekten Grafendorf befruchtet also das eines der 1. die perfekte Grafen Vermutung dass ein Graph genau dann perfekt das wäre noch ein Kompliment perfekt ist und das 2. ist der starke Mann sagte die starke befragte Grafen Vermutungen zu der ich gleich auch noch was sagen wir also zunächst einmal das Jahr 1.
führte die perfekten Grafen in den sechziger Jahren einen unvermutete eben schon diese beiden Sätze und dieser 1. der perfekte Grafen Satz wurde von Lubbers 172 gezeigt also wir haben wir einen eintraf und sein Kompliment das sind eben einfach der Graph auf der seinen Quotenbringer wo die Kanten und die nicht kannten vertauscht sind was für uns sehr interessanter ist dass der starke perfekte Grafen Satz
der erst viel später bewiesen wurde nämlich der 2006 von Schweden aus 4 Robertson und Thomas der Satz besagt dass ein Graph genau dann perfekt ist wenn er keine indizierten Teil Grafen aber von folgenden Typen besitzt einmal dafür keine Umfragen Kreise der Länge größer gleich 5 besitzen das ist der Titel 1 und dann Komplimente von solchen Strukturen sind eben diese sogenannten an und so ja der Beweis ist sehr kompliziert ist es aber eine einfache Idee dazu sind ähnlich dem zugrunde also zunächst mal ist es so wenn ein Graph perfekt ist dann kann man sehr einfach sehen dass das er in diese beiden Typen von induzierten Tage laufen nicht enthalten darf aber die Umkehrung es eben das schwierige Jahr und dann nimmt man eben so Grafen die eben diese beiden Strukturen nicht enthalten sogenannte Strafen und schön dass wir haben dann eben gezeigt haben dass die entweder von einem Typen sind die man schon als perfekt erkennt oder dass diese sogar Strafen dann eine ganze Reihe von Eigenschaften haben und ja diese Eigenschaften sind so gestrickt dass ein minimales Gegenbeispiele weil diese Eigenschaften nicht enthalten nicht haben kann und damit ist einer der Satz bewiesen haben ja also das Wetter davon ist 179 Seiten lang und unter den Benutzern noch einige Vorgänger Resultat ja aber im Grunde möchte ich für die SPÖ perfekten Grafen eine ähnliche Charakterisierung finden also auch eine Charakterisierung durch verbotene induzierte Deichgrafen gleichwertig Ihnen sagen dass ich das Spiel perfekt den Grafen verstehe bloß meine Charakterisierung also es ist nicht so beweist aufwendig weil die Klasse der Spiel perfekt die Waffen eine sehr kleine Klasse ist und uns dadurch wird werden die Preise dann doch wesentlich einfacher so
warum sind perfekte Grafen interessant also trafen haben es ist ein schwieriges Problem also schon mit 3 Farben 1 zu haben ist ein ein NP-vollständige Probleme die Karte 1972 als 1 1 der initialen Probleme für Vollständigkeit gezeigt hat dagegen gilt praktisch das für haben von versagten Grafen ist effizient möglich haben ergibt sich allgemein dass Frank Rückert Schönhubers Treiber war ja und nicht nicht nur das haben auch auch andere NP-vollständige Probleme lassen sich eben auf perfekten Grafen von denen wir wissen also zum Beispiel das Max klickt Probleme haben es könnte man sich fragen zwischen 2 1972 und 1988 ist da nichts passiert da ist sehr viel passiert insbesondere was wichtig ist dass sehr viele Klassen von trafen die man als perfekt erkannt hat dass für diese Klassen gezeigt würde dass es effiziente Algorithmen gibt und das ist eigentlich das ist der Grund weswegen er dann eben auch die perfekten trafen in der Informatik so wichtig sind die später perfekten Grafen haben in dem sich vor vorschieben haben ich noch nicht so konkrete Anwendungen aber vielleicht findet man dann auch welche so also das zwar zum Färben von Grafen
und jetzt kommt Teil 1 hinsichtlich stellen sich wieder an das Problem mit den 5
vor und nun werden nicht alle Frequenzen zentral vergeben sondern einige Teilnehmer erlegen eigenmächtig für sich Frequenzen fest ja man sollte jetzt nicht unbedingt einen Piratensender denken das kann man natürlich denken aber ich meine was es gibt auch ganz praktische Gründe zum Beispiel das könnte sein dass es einige alte Sender den ergibt gibt die da schon stehen und die in bestimmten Frequenzen senden und die für die sollen einfach nicht umgestellt werden oder es gibt es der Sender die zu einem anderen Land gehören dass der Vergabe Behörden nicht unterstellt und die liegen auch für sich in die Frequenzen fest und so also keinesfalls sein dass das man das man jetzt aber einerseits diese diese regelkonforme Festsetzung hat und an einer selbst dieser Teil 1 so das ist natürlich alles nur moderat schwer fassbar aber wenn man nicht als wahrscheinlich dass theoretisches Modell erfasst es gibt dabei aber einen Modelle was was vielleicht ein bisschen in diese Richtung geht und dass nämlich genau die eintrafen Fragen stellen die uns interessieren diese worden waren
191 von Rothländer Länder eingeführt und zwar nicht der Lernmotivation irgendein konkretes Problem zu lösen sondern eigentlich aus Komplexitätstheorie Tischen Untersuchungen motiviert also was ist jetzt so ein paar Fragen spielen wir haben einen ungestörten trafen und eine Fahrt Menge vorgegeben und 2 Spieler erlässt der Mekka und bot der 3 und die ziehen dann abwechselnd und Anzug besteht immer darin aber ein ungefärbten Knoten in einer Farbe aus der Fahrt zu haben so das benachbarte wurden verschiedene Farben an und irgendwann ist das nicht mehr möglich entweder weil alle Knoten gefärbt sind und in dem Fall sagen wir alles gewinnt oder es kann sein dass ein wurden von allen Farben und gegen umgeben ist und dann kann er natürlich nicht mehr gefragt werden und in dem Fall sagen wir das Opfer sind dass es diese so genannte Mekka breiter gewinnen also ehrlich ist Neckar Weise versucht eine eine vollständige Färbung zu erstellen und baut dabei kann versucht werden dies zu verhindern also ob könnte man eben dann mit diesen anarchistischen Elementen gleich ja machen wir mal ein Beispiel haben unseren Konflikt
Grafen von der Funkfrequenzen Beispiele und geben 4 Farben vorgegeben und der zwar ohne dass man die Spieler Ausgangsstellung erlässt ist darunter Spieler und dort der blau Spieler eines fängt man an Kraft Knoten wird überlegt ob wir diesen Knoten gehört verlässt hat den gegenüberliegenden Knoten gelb und jetzt ab ob in Spitzen wurden mit blauen in dieser Situation kann man jetzt schon sehen dass er jetzt gewinnen wird das Spiel kann man natürlich erstmal Weiterführung eines für diesen Staat könnten Violet ob diesen Knoten schwarz und er deshalb diesen Worten aber der letzte Knoten kann nicht mehr gefärbt werden denn er ist von einem violetten Knoten einen schwarzen Knoten einen blauen Knoten und Knoten geben das 1. Spiel wird nicht auf und ob gewinnt ja das kann man sich fragen sagt dass es nur da dran dass alles schlecht gespielt hat oder hat auch wirklich einen Gewinn Strategie und dazu betrachten war in den oberen Teil des Grafen ich möchte Sie darauf aufmerksam machen diese beiden Knoten sind mit gelb gefärbt und dieser ist mit blau gefärbt aber tatsächlich wenn er es irgendwie gewinnen wollte müsste dieses erreichen dass alle 3 Knoten in gelb gefärbten oder beziehungsweise in einer gleichen Farben gefärbt sind denn wir haben hier einen sogenannten Dreiecks Standardstruktur in der Mitte ist ein ein Dreieck das mussten da muss nicht wird natürlich in verschiedenen Farben und zu zu jedem dieser Knoten ist sind eben dann diese 3 Spitzen an der Hand und die müssen natürlich dann in der 4. Farbe gefärbt ja nur da alles umworben abwechselnd zu dran sind kann er überhaupt spätestens in seinem 2. Zug erreichen dass diese das 2 von diesen Knoten in verschiedenen Farben gefärbt und damit hat er einen Gewinn Strategie mit 4 Farben so also alles
verliert bei 4 Farben obwohl es es ja 4 Farben mit 4 Farben gibt und bei 5 haben würde alles gewinnen das motiviert dann eben die folgende Definition also die Spiele ,komma zwar ist die kleinste Anzahl von Farben für die Erde eine Gewinn Strategie auf einen auf dem vorgegebenen Grafen hat wir hier so und natürlich ist die wildromantische war mindestens so
groß wie die chromatische zahlen und damit natürlich wie wir eben schon gesehen haben das Recht zu groß für die klicken Zahl und den Ländern einen Grafen Spiel perfekt denn bei Ihnen und bei jedem induzierten Tage nach von ihm die Spiele ,komma Chats vergleicht der Krieg alles also das ist jetzt analog zu der perfekt hat nur eben das was das Leben die spätromantische zahlte die chromatische Zahlen der Definition ersetzt aus der Definition sieht man natürlich direkt auch das sich später sagten Grafen eine Unterklasse der am Samstag den Grafen zu einem sehr kleinen Unterklasse so auf ein kleines Detail bei dieser Definition hab ich noch nicht hingewiesen es macht
nämlich einen großen Unterschied ob er lässt das Spiel anfängt oder das Spiel anfängt das sind völlig verschiedene Spiele es gibt Grafen wo wovor eben jener anfangs Spieler haben die Spiele ,komma Stückzahl unterschiedlich ist und man kann auch noch andere Sonderregeln sich überlegen und dadurch entstehen verschiedene Spielvarianten also eigentlich hauptsächlich interessanteste Spielvariante haben und gehen wo wir für die Spiele perfekt hat dann eben perfekt hat heißt das das Spiel wo er anfangen darf und keinen aussetzen erlaubt ist und dies zu diskutieren hat sie aber wie wir in diesen Tagen einen ein leichteres Spiel erstmal zu betrachten nämlich das Spiel weg was sie der perfekte definiert und bei diesem Spiel das ob aussetzen und Anfang also Bob darf insbesondere auch in seinem 1. Zug aussetzen so dass sehr praktisch in diesem Spiel alle Vorteile für sich hat dann kann man analog dazu definieren in die der hat wo alles aussitzen und anfangen darf und und dann noch so ein paar andere Spieler wo die Regeln irgendwie gemischt sind beziehungsweise gewesen das duale zu dem Spiel so das heißt ja wir konzentrieren uns erst mal auf die B perfekt hat also ob das aussetzen und
Anfang so und jetzt sehen wir hier
dieses Bild und das ist und hier habe ich sogar unter Licht aller B perfekten trafen bis zur 2. zwar 5 und dann noch so ein paar von den Zahlen 6 und so und Hocker unterlegt oder ob wirklich und ehrlich sind die sind die nicht die perfekten Grafen und dabei fällt auf jeder dieser nicht den perfekten trafen enthält eine von diesen 4 besonders hervorgehobenen Konfigurationen also einen Vater Länge 4 einen Kreis der Länge 4 oder eben noch diesen beiden anderen wie man hier sieht also etwa dieses hat einen Kreis der Länge 4 1 als in den 4. Teil Graph ja und das ist eigentlich auch schon die Lösung des Problems ist nur noch beweisen also die Frage
ist was in die wir perfekten Grafen charakterisieren sie mittels verbotener endet der Datei greifen würde vermuten dass
eben genau diese 4 verboten sind wollen wir jetzt mal erst mal als einfache Übungen zeigen dass eben diese 4 Grafen nicht wir perfekt sind dann haben wir schon mal die leichtere Richtungen in der Fragestellung beantwortet also betrachten etwa den C 4 und die Flecken davon von den C 4 ist in 2 haben das heißt wir müssen das Spiel mit 2 Farben betrachten ja ob selbst in seinen 1. Zug aus das heißt alles muss irgendeine wurden in der 1. Phase fragen dann keinen überhaupt den gegenüberliegenden Knoten mit der 2. Farbe haben und er gewinnt weil eben die letzten beiden wird nicht mehr gefördert werden können ganz analoge dass bei den 4 der 4 ob selbst in seinen 1. Zug aus und egal was er macht er kann nach 2. Zug immer so eine Situation herstellen oder eine symmetrische dazu so dass ein Klub nicht gefärbt werden kann dann betrachten wir den gespaltenen 3 Sterne hier spielt in seinem 1. Zug so erlässt steht jetzt vor dem Dilemma wenn Sie jetzt sagen einen der Linken bei den Knoten Verrat am unteren Ende natürlich in der 2. Farbe dann würde ob diesen Knoten in der 3. Farbe färben und hätte dann geworden weil dieser andere wurden dann nicht mehr gefragt werden können also musste zwangsläufig einen dieser Knoten verfärben und zwar in derselben Farbe denn sonst hat sie auch verloren aber das noch ein 3. gibt an Bord der in der 2. Phase haben und ja es ist nur noch eine Frage übrig für für diese beiden Knoten unter bräuchten aber es war auch das wir gewinnen ob mit 3 fahren also ist 3 des nur mit 3 Farbenspiel so bei dem Doppel fern ist auch die klicken 2 3 und wir geben jetzt wieder einen Gewinn Strategie verborgen mit 3 Farben an Bord hatte seinen 1. sucht die linke obere Ecke und damit alles nicht direkt verliert muss sie dafür Sorge tragen dass die rechte obere Ecke in der gleichen Farbe gefärbt ist wie die linke obere Ecke das kann sie nicht erreichen indem sie einen anderen Knoten Fahrt sondern die einzige Möglichkeit dafür ist dass sie den direkt in derselben Farbe hat dann kein Wort aber den linken unteren Knoten in der 2. Phase Farben aus denselben Grund muss alles für den rechten unteren in der 2. Phase schlagen mehr und jetzt fragt ob irgendein und den oberen oder unteren und mittleren Knoten in der 3. Farbe und der Zentrag werden kann nicht mehr gefragt werden was das Wort gewinnt auch so ja
dann wollen wir mal diesen Satz beweisen also der Satz lautet für einen Grafen sind äquivalent ist perfekt dass das was wir untersuchen wollen die an die die Charakterisierung die wir haben wollen ist das Geld 1 keinem dieser 4 verbotenen Konfigurationen als induzierten Teil Grafen enthält und dann haben wir noch eine 3. Charakterisierung nämlich ein explizit als in dass jede Komponente von 1 und hier ist was ein und jetzt will ich gleich noch erklären aber das ist sozusagen der Weg in den Beweis dass man eben diese 3. Eigenschaft noch mit benutzt und dann kann man einen Ring Schluss machen das ist sozusagen die die 2. Eigenschaft ist eine indirekte Charakterisierung durch verbotene Konfigurationen und die 3. Eigenschaft ist praktisch eine Charakterisierung der explizit wie wie der Graph tatsächlich aussieht und ein
und hier sind ebenso war also ihre Komponenten des Grafen sieht es so aus dass ich ein zentraler Knoten habe in der Mitte dann hab ich irgendwelche Lieder die sind sehr vollständige Grafen und dann hab ich noch hier ein Kopf mit 2 Ohren und jeweils die Ohren und der Kopf sind auch vollständige Grafen und und der Kopf ist mit beiden Ohren verbunden aber die Ohren untereinander sind nicht verbunden so das muss nicht sein dass der Kopf von existieren oder dass die wieder existieren das kann auch nur Teile davon existieren aber auf jeden Fall ist die Struktur in in dieser in dieser Frauen also wichtig ist dass es eben nur eine solche Strukturen und mit Kopf und Ohren gibt und die die übrigen Glieder des das können beliebig viele so also wir haben
jetzt gerade schon gezeigt werden eine Grafen Spiel perfekt ist oder wäre perfekt ist dann enthält der nicht haben diese 4 verboten Konfigurationen und jetzt wollen wir die anderen zeigen zunächst
einmal von 3 nach 1 wenn machen also den Schluss also wenn ihre Komponenten und ist dann wollen wir zeigen dass der Graph der perfektes ist und dazu müssen wir eigentlich nur einen Gewinn Strategie für erlässt auf so orientieren angeben ja und also ist welches in den Details Ausführung aber die Strategie ist sehr einfach haben den alles hat eigentlich 2 Ziele Sinnesart einerseits an sehen dass rechtzeitig der Central Knoten gefärbtes bevor viele andere Knoten gefärbt sind und andererseits muss sie dann dafür Sorge tragen dass wenn in einem Oberarm eine Fahrbahn vorkommt nach ihrem Zug dann in dem anderen Ohr genau die gleiche Farbe auch wieder vorkommen Jahr und genau und das ist da kann man dann eine einfache Strategie angeben und ja jeder interessierte Teil davon und hier ist wieder ein und hier oder beziehungsweise auch vom Grafen deren Komponenten aus und geschehen ist es in Kraft das Komponenten aus und steht und deswegen reicht das Leben zu zeigen so die etwas schwierige
Richtung ist die von 2 nach 3 also wenn wir haben keine dieser verbotenen Fehlkonfigurationen enthält wollen wir zeigen dass die Struktur eben genauso ist dass jede Komponente ein und ist ist also wieder in den Mund zu einem Grafen der der eben keiner dieser 4 wurden Konfigurationen teilt und
nehmen davon eine Komponente und dann hilft uns aber in entscheidender Weise einen Hauch von Wolke
von 1965 ein zusammenhängender Graph ohne induzierten C 4 und C 4 solche Grafen in Montreal perfekte Grafen an die besitzen einen Antrag lohnt also ein zentraler Knoten ist immer ein Knoten der zu allen anderen Knoten benachbart ist und damit hat diese Komponente eines eintragen und so und jetzt kommen ein paar technische Beweise dann müssen
wir nämlich noch zeigen also wenn das was am Central hängt nicht wie bei uns hier aussieht das dann eben eine dieser verbotenen Konfigurationen enthalten ist also Nummer 3 das Sagen haben und dann noch ein bisschen und auch Fallunterscheidungen auch zu machen sind die möchte ich jetzt wir jetzt nicht alles Mathematiker hier sind auch mal weglassen und wenn man das dann hat aber gezeigt haben dass diese Äquivalenz im Einsatz wird damit dass die Charakterisierung der Wirtschaft auf den bewiesen haben
uns noch mal das Bild an also wir haben schon festgestellt war ich nicht mehr perfekten enthalten in diese 4 Konfigurationen irgendwo drin und wenn wir jetzt uns mal diesen Abend der perfekten trafen am gucken dann aber ist der eine und hier in folgender Weise der 2. Knoten von rechts ist der Zentrag Knoten dann haben wir hier ein die etwas aus einem Knoten besteht und hier haben wir ein die etwas aus 3 Noten besteht dieses Dreieck und das ist also ein und hier was ohne Kopf verlogen ist hier haben wir aber das ist der 3. Graph von von links in der unteren Reihe da haben wir einen und hier was was nur als Kopf oben besteht und dem Zentrag wie etwa unten der Central Knoten und die der Ober Knoten ist der Kopf des Linke ist das linke Ohr und diese beiden rechten Sinn das rechte Ohr also die von ist nicht gleich groß sein hier uns nur so kann man das bei den anderen Grafen eben auch sehen so das hat einmal gesagt die wir perfekten Grafen haben diskutiert und eigentlich haben die Betten in die geht perfekten Grafen diskutieren zu können das heißt wir
betrachten erst noch ein paar andere spiele ich mich zunächst mal dass
wir gehen so alles anfangen muss und niemand aussetzen darf bei der Diskussion dieses
Spiels stelle ich fest dass die G perfekten trafen genau dieselbe Klasse von Grafen beschreibt wie die aber perfekten Grafen obwohl die Spiele ,komma Action Zahlen zu diesen beiden Spielen für bestimmte den Grafen verschieden sein können das heißt um und in das das ist es auch hilfreich um das überhaupt Resultat eines verpasst und Formulierungen untersuchen wir nicht nur das Spiel geht sondern auch in das Spiel aber wo wo alles anfangen muss und ob aus setzen darf dass das hier ist ist es so dass das Aussetzen von Bord für die Spiele perfekter mindestens aber keine Auswirkungen hat und dann werden
wir bei Hauptresultate meines Körpers angelangt Graph ist hier perfekt beziehungsweise aber perfekt genau dann wenn er keinen der obigen 7 Grafen als 4. Teil Grafen enthält da haben wir wieder den C 4 und den 4 und aus dem gespaltenen 3 Sterne sein Dreiecks extern geworden und aus dem Jahr in der Prophet ist eigentlich die Kraft geworden und zwar entstehen sie einfach aus den anderen Konfigurationen dadurch dass ein zusätzlicher der zentral Knoten noch eingefügt wurden und außerdem haben wir noch 3 weitere Konfiguration die verboten sind nämlich das mehrfach Auftreten von dort entfernt beziehungsweise gespaltenen 3 Sterne das ist auch verboten Jahr und wir benutzen wir eine in der Einrichtung des Beweises die Klassifikation der perfekter Grafen und andererseits zeigen wir eigentlich noch mehr nämlich dass die perfekte Grafen beziehungsweise AB perfekte Grafen von
Struktur haben jede Komponente ist entweder wir perfekt also ein und wir haben oder oder ist es gibt es noch eine besondere Komponenten die sich um die aus einem zentral flutende besteht an denen wiederum und hier ein und aus dieser Struktur kann man sehr einfach sehen was was alles für eine Strategie hat wenn Sie jetzt den 1. Zug hat und voraussetzen darf dann als er nur diesen einen Vorteil und dem Fernsehen dazu nutzen diesen Vertrag Noten zu haben und dann ist sie 1. das Spiel reduzierte genauso wie bei dem Spiel WWE wieder über dem Spiel gehen wo wo ich halt nur noch um Tiere vorliegen haben also die Details des des Beweises also das war jetzt nur noch ein Teil des Rings Schluss ist richtig auslassen und stattdessen noch einmal auf die anderen Spieler eingehen mir noch 3 andere
vor aber muss ich sagen aber hier sind ist die Klassifikation noch nicht gelungen betrachten wir zunächst mal das einfach so von diesen Spielen nämlich das Spiel was praktisch Gewalt im Spiel geht es vor allem aber ob anfangen muss und niemand aus 10. und hier
habe ich folgende verboten Konfigurationen gefunden habe der C 5 der G 5 der Stuhl gespalten 3 Stellen und dann noch 4 aus dem C 4 und 4 und einen zusätzlichen Quoten gebildet Konfiguration was macht das jetzt schwieriger als das vorherige entscheidend war vorher das eben der P 4 und der Zephir verboten sind das ist also trivial perfekte Grafen vorliegen hatten ohne die ohne diese Konfiguration also wenn diese Konfiguration erlaubt sind die Struktur der Grafen viel komplizierter und daher ist es eben noch offen ob dies alle verbotenen Konfiguration für GB perfekt hat sind was man sagen kann aufgrund dieser Konfiguration hier unten entweder der Graph besteht aus mehreren Komponenten dann ist jede Komponente B perfekt aber wenn der Graph zusammenhängend ist also nur aus einer Komponente besteht ja dann kann die Struktur dieser Komponente noch komplizierter sein und diese zusammenhängenden perfekt gelaufen sind eben noch nicht klassifiziert ,komma zu nicht
schwierigen spielt der in der Variante B A also ob muss anfangen aber er lässt auf aussetzen dass er die wildromantische Zahl wiederum etwas kleiner und das heißt andererseits die Klasse der Spiel perfekten Grafen ist größer und demgemäß auch schwieriger zu klassifizieren und hier habe ich
folgende wurden Konfiguration bis jetzt gefunden der C 5 P 5. Stuhl wie schon vorher gespaltener 3 Standorte für und ungerade an die Löcher also die Konfiguration vom Typ 2 aus dem starken perfekten Grafen Satz und schließlich die
Spielvariante die am reichsten ist dass die Art vergleicht wo
alles alle Vorteile hat er lässt das Aussetzen und anfangen
da hab ich folgende Konfiguration gefunden auch wieder diese 1. 3 die wir schon kennen C 5. 5 und Stuhl an den 3 Sternen die Graph einer ungeraden Anzahl Löcher und dem auch die 2. 1 2 gespaltene 3 Sterne und den gemischten traf ja Jahr was ich hier noch dazu sagen möchte ist die Ungarn an die Löcher sind hier in diesem Fall tatsächlich eine minimale verboten Konfiguration das heißt ich kann ich nicht durch irgendwelche anderen Konfiguration der rausschmeißen haben denn ich habe in früheren Partner schon gezeigt haben dass er Komplimente von Deportierten Grafen war perfekt sind und wenn ich als in ungeraden eigentlich noch irgendeine Glocken rausschmeißen dann ist der ist das Komplement davon einfach 1 Jahr an Graph der nur aus Faden besteht also insbesondere deportiert und damit müssen diese ran Leiche in der Minimalkonfiguration zu haben ja die offene Frage stellt sich Jagd sind dies alle verbotenen Konfiguration wenn nein welche weiteren gibt es ein Jahr man beweisen dass mit dieser offene Frage möchte ich mich für Ihre Aufmerksamkeit bedanken
Endliche Menge
Diskrete Mathematik
Graphentheorie
Optimierung
Struktur <Mathematik>
Graphfärbung
Menge
Klasse <Mathematik>
Graphfärbung
Verträglichkeit <Mathematik>
Kante
Computeranimation
Graph
Graphfärbung
Netzwerk <Graphentheorie>
Kraft
Graphfärbung
Computeranimation
Total <Mathematik>
Graph
Vollständiger Graph
Frequenz
Computeranimation
Mathematische Größe
Kreis
Zahl
Total <Mathematik>
Zahl
Computeranimation
Ebene
Graph
Graph
Graphentheorie
Computeranimation
Graph
Graph
Länge
Kante
Komplementarität
Computeranimation
Gegenbeispiel
Graph
Vollständigkeit
Länge
Graph
Klasse <Mathematik>
Länge
Reihe
Mathematik
Umkehrung <Mathematik>
Struktur <Mathematik>
Frequenz
Computeranimation
Richtung
Sierpinski-Dichtung
Graph
Spitze <Mathematik>
Menge
Kraft
Graphfärbung
Element <Mathematik>
Dreieck
Computeranimation
Komplexitätstheorie
Graph
Graphfärbung
Zahl
Teilgraph
Zahl
Computeranimation
Computeranimation
Kreis
Länge
Graph
Zahl
Computeranimation
Einfach zusammenhängender Raum
Graph
Verschlingung
Graph
Teilgraph
Einfach zusammenhängender Raum
Ecke
Computeranimation
Richtung
Einfach zusammenhängender Raum
Struktur <Mathematik>
Computeranimation
Einfach zusammenhängender Raum
Graph
Graph
Kraft
Teilgraph
Einfach zusammenhängender Raum
Computeranimation
Richtung
Einfach zusammenhängender Raum
Graph
Zusammenhängender Graph
Äquivalenz
Einfach zusammenhängender Raum
Mathematiker
Zusammenhängender Graph
Ausgleichsrechnung
Computeranimation
Verschlingung
Graph
Reihe
Dreieck
Computeranimation
Klasse <Mathematik>
Zahl
Computeranimation
Einfach zusammenhängender Raum
Sierpinski-Dichtung
Graph
Unterring
Graph
Kraft
Technische Zeichnung
Konfigurationsraum
Gemischter Graph
Körpertheorie
Einfach zusammenhängender Raum
Quote
Graph
Konfigurationsraum
Computeranimation
Klasse <Mathematik>
Konfigurationsraum
Zahl
Computeranimation
Graph
Komplementarität
Graph
Konfigurationsraum
Gemischter Graph
Computeranimation

Metadaten

Formale Metadaten

Titel Spielperfekte Graphen
Serientitel Kolloquium der Fakultät für Mathematik und Informatik der FernUniversität in Hagen
Autor Andrese, Stephan Dominique
Lizenz Keine Open-Access-Lizenz:
Es gilt deutsches Urheberrecht. Der Film darf zum eigenen Gebrauch kostenfrei genutzt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden.
DOI 10.5446/18573
Herausgeber FernUniversität in Hagen
Erscheinungsjahr 2012
Sprache Deutsch
Produzent FernUniversität in Hagen

Inhaltliche Metadaten

Fachgebiet Mathematik
Abstract Graphenfärbungsprobleme treten in vielen Anwendungen auf, wie zum Beispiel bei der Funkfrequenzzuweisung oder Stundenplanproblemen oder, allgemeiner, bei Problemen, bei denen verschiedene Ressourcen miteinander in Konflikt stehen. Meist sind aber keine effizienten Lösungsverfahren bekannt. Eine Klasse von Graphen, bei denen das Färben gutartig ist, sind die sogenannten perfekten Graphen. Diese wurden 2006 von Chudnovsky, Robertson, Seymour und Thomas durch einen Beweis einer jahrzehntelang offenen Vermutung von Berge mittels verbotener induzierter Teilgraphen klassifiziert. Im Gegensatz zu diesen Problemen, deren Lösung eine zentrale Instanz vornehmen kann, stehen Probleme, in denen anarchistische Elemente, die eigene Interessen verfolgen, die Lösungsfindung stören dürfen. Letztere stellen nichtkooperative Spiele dar. In einem mathematisch sehr vereinfachten Modell färben zwei Spieler abwechselnd bislang ungefärbte Knoten eines gegebenen Graphen mit Farben einer vorgegebenen Farbmenge, so dass benachbarte Knoten verschiedenfarbig gefärbt sind. Wenn das Spiel

Ähnliche Filme

Loading...