Graph Scanning and Connectivity II

Video thumbnail (Frame 0) Video thumbnail (Frame 6419) Video thumbnail (Frame 14119) Video thumbnail (Frame 28910) Video thumbnail (Frame 43701) Video thumbnail (Frame 48286) Video thumbnail (Frame 62077) Video thumbnail (Frame 74265) Video thumbnail (Frame 82733) Video thumbnail (Frame 91200) Video thumbnail (Frame 103526) Video thumbnail (Frame 115851) Video thumbnail (Frame 128176)
Video in TIB AV-Portal: Graph Scanning and Connectivity II

Formal Metadata

Title
Graph Scanning and Connectivity II
Title of Series
Part Number
3
Number of Parts
15
Author
License
CC Attribution - ShareAlike 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this license.
Identifiers
Publisher
Release Date
2012
Language
German

Content Metadata

Subject Area
Abstract
Auf Basis analytischer Sachverhalte entwickeln wir algorithmische Ideen für Verfahren auf Graphen. Daraus entstehen zunächst generische Verfahren, welche formal bezüglich ihrer Korrektheit und Laufzeit analysiert werden. Im Anschluss daran werden in jedem Kapitel Techniken zur Verbesserung und Beschleunigung vorgestellt. Abgerundet wird der Stoffplan durch zahlreiche Modellierungs- und Anwendungsbeispiele und der (optionalen) Implementierung eines Benchmarks verschiedener algorithmischer Varianten.
Loading...
Wavefront Graph (mathematics) Connectivity (graph theory) Ultraviolet photoelectron spectroscopy Connected space
Kante Stress (mechanics) Euclidean vector State of matter Graph (mathematics) Direction (geometry) Calculus Axiom Connected space Forest Inclusion map Connected space Mathematics Graph coloring Network topology Zusammenhang <Mathematik> Network topology Physical quantity Connectivity (graph theory) Theorem Vertex (graph theory) Linear map Directed graph
Link (knot theory) Euclidean vector State of matter Graph (mathematics) Lemma (mathematics) Ultraviolet photoelectron spectroscopy Connected space Physical quantity Inclusion map Forest Connected space Root Radical (chemistry) Network topology Zusammenhang <Mathematik> Logic Formaler Beweis Function (mathematics) Network topology Connectivity (graph theory) Vertex (graph theory) Loop (music) Directed graph Linear map
Kante Link (knot theory) State of matter Graph (mathematics) Lemma (mathematics) Ultraviolet photoelectron spectroscopy Hypothesis Connected space Forest Connected space Radical (chemistry) Network topology Zusammenhang <Mathematik> Network topology Many-sorted logic Connectivity (graph theory) Vertex (graph theory) Inductive reasoning Identical particles
Lineare Ordnung Kante Stress (mechanics) Series (mathematics) Link (knot theory) Process (computing) State of matter Graph (mathematics) Moment (mathematics) Wirkung <Physik> Ultraviolet photoelectron spectroscopy Connected space Position Plane (geometry) Causality Function (mathematics) Many-sorted logic Ecke Connectivity (graph theory) Vertex (graph theory) Quote
Kante Stress (mechanics) Link (knot theory) Graph (mathematics) Lemma (mathematics) Moment (mathematics) Ultraviolet photoelectron spectroscopy Number Function (mathematics) Network topology Many-sorted logic Connectivity (graph theory) Vertex (graph theory) Linear map
Kante Modal logic Stress (mechanics) Euclidean vector Graph (mathematics) Direction (geometry) Lemma (mathematics) Set (mathematics) Subset Connected space Physical quantity Partition (number theory) Plane (geometry) Subgraph Logic Bipartite graph Network topology Many-sorted logic Graph (mathematics) Connectivity (graph theory) Length Linie Partition (number theory)
Kante Modal logic Zahl Link (knot theory) Euclidean vector Graph (mathematics) Lemma (mathematics) Division (mathematics) Total S.A. Parameter (computer programming) Partition (number theory) Subgraph Bipartite graph Graph (mathematics) Connectivity (graph theory) Vertex (graph theory) Absolute value
Kante State of matter Graph (mathematics) Real number Nummerierung List of anatomical isthmi Mathematical induction Sequence Connected space Mathematics Coefficient of determination Graph (mathematics) Vertex (graph theory) Recursion Inductive reasoning Directed graph Social class Proof theory Modal logic Series (mathematics) Link (knot theory) Laufzeit Recursive language Liquid Index Function (mathematics) Connectivity (graph theory) Theorem Condition number Iteration
Link (knot theory) Graph (mathematics) Radius Strut Connectivity (graph theory) Vertex (graph theory) Gamma function Inductive reasoning Proof theory Traverse (surveying)
so genau sind die anderen immer so sein dass er verlängert werden an der TU Darmstadt so meine Damen und Herren nach
diese sie problematischen Angelegenheit von eben dieses ganz wird mal wieder aufzubauen kommen wir endlich mal wieder zur Sache organisatorisch vorne weg die Aufnahme ich denke dass ich die in dieser Woche der einstellen kann und die Bienen im Forum Bescheid eine weitere Rucksacktourist hatte schon im Forum gepostet leider funktioniert es doch nicht der sich in die KEF für diese Veranstaltung anzumelden es gibt die strikte Pollys sehe jeder Lehrveranstaltung ist nur einen Bereich zuzuordnen diese falsche und jetzt im Bereich Fock habe ich fragen wenn das betrifft ja tut mir leid ich seinen letzten Jahren anders aber irgendwie hat sich da etwas geändert müssen Sie vielleicht zum Studium nur geben wenn irgendwelche Anerkennungsfrage das dazu kann ich nichts sagen ich habe selber schwimmen kann bei immerhin daher dass die Dozenten solche Fragen nicht beantworten die in in den Hoheitsbereich des Prüfungsausschusses vor ein gut nach etwas Organisatorisches von Ihrer Seite aus wenn das nicht der Fall ist ich gucke noch mal ganz kurz ob das mit der Kamera alles so weit stimmt in weiß ich nicht ob das so stimmt na gut kann schauen wir mal ist ist die Karte wieder kein ordentliches Bild an was er eigentlich müsste ich okay man sitzt gut dann bin ich nur blind von der Nähe aus gut also comma dann sonst wenn unser deutsches mehr gibt zum inhaltlichen wir waren das letzte Mal stehen geblieben bei durchlaufen und kommen jetzt insbeson- zum Thema zusammen es Komponenten finden wir haben letztes Mal ein allgemeines generisches Schema zum Grafen durchlaufene sehen Sie sehen dass sie noch mal mit den roten blauen und grünen nein schön in keiner seine weiße Punkte zwischen Kunden und sie sehen hier die beiden Beispiele die wir gesehen haben breiten Suche BSF links die das ist die abstrakte Vorstellung die Sie damit nehmen sollten das ist immer so dass wie eine Wellenfront geht vom Staat Noten schwarz aus hinter der Wellen räumt alles war schon durchlaufen wurde ist drohte schon vollständig abgearbeitet blau sind die die in der aktuellen Datenstruktur sind bei der Breite Suche ist die Khieu und reißen die Knoten die noch gar nicht gesehen worden sind und diese Wellenfront um im Bild zu bleiben geht von links nach rechts so ungefähr durch den Grafen durch rechts sehen Sie ein Beispiel nach ein paar Schritten tiefen Suche so dass genau das Gegenteil dass man so weit so tief wie möglich kommt und es charakteristisch ist das eben um am Ende nicht so wie hier am Anfang bei breiten so sondern am Ende begonnen wird Knoten rot zu färben nämlich die wo es nicht mehr weitergeht die wären rot gefärbt und dann geht man zurück und es da auch nicht mehr weiter das rot gefärbt und so weiter und so fort bis man Schritt für Schritt den ganzen Grafen durchlaufen hat das wird natürlich etwas unübersichtlich wenn man versucht einen späteren Schnappschuss hier zu visualisieren das verbissene relativ früh ein Schnappschuss ihrer gewählt worden wo es erstmal mal ein Fahrt geht ja bei dieser Reise immer ein 2. und der 2. geht gleich wieder ein 2. und wenn so weitergeht gleich wieder ein 2. und sofort wie nach und nach irgendeinem Gusto und da es nicht mehr weitergeht da geht man zurück und da wo man zurückgegangen sondern Kundennummer zurückgegangen ist dieser Knoten wird rot gefärbt kommen hat König auch am Ende heraus dass sämtliche Knoten rot gefärbt sind sind ja reich Banknoten soll ich sagen
so war Zusammenhangs Komponenten ich möchte hier bei diesem Thema und auch bei manchen anderen Themen ein bisschen vom Skript abweichen versuchen anschaulicher Illustrativer zu werden als es im Skript ist insbesondere dann bei den beweisen da werde ich häufig eher an ihre Anschauung appellieren als das durchzuziehen was hier tatsächlich einen als Beweise auf den Folien stehen ich nehme an Sie werden nichts dagegen haben weil sie doch so was dagegen haben comma natürlich die Beweise Punkt für Punkt durchgehen aber ich habe gute Hoffnung dass man die Dinge nicht nur er period Färbung durchgehen kann sondern dass man sie auch illustrativ anschaulich verstehen kann dass darum will ich mich bemühen wenn jemand in der mündlichen Prüfung tatsächlich dann mit diesen hier ausgelassen Detail beweisen ankommt und das werden so reden dann dann erklären kann dann ist er schon denke ich ziemlich auf der Zielgeraden zu 1 0 aber es würde ich nicht als die Möglichkeit zum 1 0 zu kommen der verständlich sind Dinge die wir ausgelassen haben niemals Voraussetzung für irgendeine Not auch nicht wie die allerbeste so was zusammen es Kommunen betrachten wir zuerst mal den ungerichteten Fall in und da fängt es gleich an ich habe versäumt zu die Tafel zu putzen wir haben das immer so gesagt ja das ist ein Graf auch also müsse vorstelle Knoten kannten sowie immer sowie in drauf ist wir haben ungewichtete Grafen momentan gekommen dann zugerichteten und wenn es jetzt um Zusammenhangs Komponenten geht dann ist nicht das Graf sondern in Graf ist etwas das aus mir werden solchen Sachen bestellt ja die streckt separiert voneinander sind Knoten könnten wo man eben nicht von die ein Knoten der Einkommen der über einen Weg zu einem gesunderen Komponente kann und wie findet man diese Zusammenhangs Komponenten das ist im ungerichteten Grafen erst einmal ganz einfach wie starten irgendwo in einer dieser Zusammenhangs Komponenten mit unserer Grafen suche und egal was wir verwenden breiten Suche tiefen Suche oder sonst etwas wir wissen genau welche Knoten wie mit dieser breiten Suche am Ende auf von Weißen zu roten gemacht haben nämlich genau die offensichtlich die in dieser Zusammenhangs Komponente sind die haben wir alle erreicht die andern haben natürlich nicht erreicht so was heißt das dass es in dieser Situation in dieser ein Zusammenhangs Kommunen sind alle Knoten rot fertig prozessiert wenn die Suche fertig ist und den den anderen sündigen wurden alle noch Initial weiß also uns wieder um den weißen Knoten her und und wiederholen das ja es sind die beiden Bereiche rot alle Knoten halt noch immer wieder von irgendwo her und wieder und jedes Mal wenn meine Suche haben haben ich eine ganze zusammen das Komponente gewohnt und ich denke das ist einfach zu verstehen anschaulich zu verstehen brauchen uns jetzt keine abzubrechen und das irgendwie formal zu formulieren das ist das was hier auf Städte falls der Graf nicht zusammenhängend ist noch kein erklärt bleiben die Knoten in einem Komponenten war es und wenn wir das dann wiederholt machen dann haben wir am Ende alle Knoten wir sehen was wir haben ist nicht ein Baum sondern ein Baum pro Zusammenhangs Komponente das bedeutet einen Wald per Definition und jeder dieser Bäume ist also es gebündelte genau zielte gut dass es jetzt weniger wichtigen Zusammenhang Züge werden dabei auch natürlich entdeckt wichtig nur zum zum weiteren Reden über die Dinge wenn wir jetzt von jetzt an von DFS oder BFS sprechen dann meinen wir nicht nur eine Anwendung davon einmal durchlaufen sondern wie man dieses wiederholter also mit einem Noten alles erreichen was erreichbar ist dann mit dem nächsten starten alles erreichen was erreichbar ist und so weiter und so fort bis keine weißen Blumen mehr da sind so wir haben schon gesehen dass die Grafen sowie Zeit beansprucht egal wie wir sie implementieren ich arbeiten Suche oder tiefen Suche oder ähnliches das heißt also wir wissen damit dass wir und Gerichten Graf des Zusammenhangs Komponenten Zeit finden können jetzt kommt der gesamte und das ist auch der
Fall wo ich jetzt denke ich deutlich von den Beweisen für mathematischen Darstellung Abweichler auf die Wiese auf dem vorgegeben sind Versuche mehr an ihrer Anschauung zu appellieren immer im Bewusstsein das Bilder immer so bis tief sind darum macht man ja das ganze Brimborium Männer Mathematik mit Kalkülen aber und auf Axiomen Theoremen mehr zu beweisen und ähnliches weil eben wenn man versucht das informell zu machen das ist die Erfahrung die bittere Erfahrung durch die Jahrhunderte hindurch dass man sich da beliebig die beliebigen Blödsinn einbilden kann dem man dar gefunden haben will das heißt also diese mathematische Behandlung wie sie auf den Folien ist hat absolut ihre Berechtigung so starke Zusammenhangs Komponenten sie sehen jetzt hier noch mal ein Beispiel eines gerichteten Grafen was sind die starken Zusammenhangs Komponenten hier ja diese 3 roten sind stark zusammen was heißt das noch mal in einer starken Zusammenhangs Kommunen der kann jeder Knoten jeden anderen erreichen und wird auch dementsprechend dann eben einen Knoten innerhalb dieser Staaten Zusammenhangs komplett erreicht die beiden diese gelbe und diese roten sind nicht in einer gemeinsamen zu Staaten zusammen turbulente denn man kann zwar von jedem rund wurden zu Geld kommen aber man kann nicht von Gelb rückwärts die kann sie wieder zu Gerbereien man kann nicht davon gehört zu Roth kommen der aber genau aus diesem Grund ist Geld auch nicht Teil dieser Staaten Zusammenhangs kommen der dunkelblauen bei zwar vom Gärtner blau kommen kann aber nicht von blau nach gelb und hier die her diese hellblauen bilden ebenfalls sehr starke Zusammenhangs comma weil von jedem Knoten komme man zu jedem an so wir müssen uns im Klaren darüber sein das die Staaten Zusammenhangs Komponenten eine gewisse Struktur haben und zwar wir nehmen wieder die Staaten zusammen es Komponenten her und ich habe das schon beim letzten Mal so angefangen wir malen von rechts nach links so vielleicht so das reicht jetzt was nicht passieren kann ist beispielsweise dass es von dieser Staaten zusammen es kommen zu dieser eine Kante gibt irgendwo rein von irgendwo hier zu diesen von hier nach hier hier von irgend von hier nach hier von hier nach hier zum Beispiel und von hier von wurden hier rein das kann nicht sein denn das würde bedeuten das alle 4 zusammen eine starke Zusammenhangs Komponente ja von jedem Knoten hier komme zu jedem Knoten hier immer von hier zudem gehen früher war von hier zudem rüber von dir zum N Knoten und zurück ja wenn die kann wenn die Kanten die von einer starken zusammen kommt in so einem gehen wenn Dienstsiegel bilden das das kann nicht sein weil wir das ganze starke Zusammenhangs komme und deshalb habe ich auch recht damit dass sich das von links nach rechts Zeichen der ich brauche ich nur eine einzige könnte dafür stimmen diese rückwärts gehende ja denn sowas kann alles seien solange sich keine Züge schließt es kann natürlich auch halt hieß noch eine des Kennedy-Museum drehen so es kann natürlich mehr gekannt noch von einer Staaten zusammen es Kommunen sondern gehen solange sie alle dieselbe Richtung haben es das alles kein Thema war so der Gewinn noch Ja aber sie sehen schon wie diese Film war dann aus diese gesamt Knoten das ist das Bild was sie vor Augen haben sollten wenn sie bei über 1 Erregung eines gerichteten Jahren seine Staaten zusammen Komponenten nachdenken oder wenn sich hier in der Vorlesung davon berieseln lassen so und auf diesem Bild diese auf diese Vorstellung dass man alle Knoten dass man alle kannten die von einer starken Songs konnten den der andere gehen dass man die so von links nach rechts rechnen kann auf die oft darauf basiert der Algorithmus denn ich auch entsprechend bildhaft erst einmal versuchen wir zu erklären so wir fahren erst einmal wir nur sehr tief Sucher ja wichtig diesen wir haben erst einmal so wie eben gesehen haben irgendwo mit irgendeinem Knoten an wir wissen ja am Anfang gar nichts über die ganzen Knoten und über den der Struktur des Grafen ja also wir wissen nicht wo wir anfangen sollen wir fangen zum Beispiel an hier zufällig hier dann wissen wir bei der tiefen Suche oder überhaupt bei der Grafen suche was wir alles erreichen das wissen wir im voraus was wir von diesem Knoten aus erreichen werden wir wenn alle Knoten in dieser Staaten sollen uns geworden da reichen natürlich auch alle Knoten dieser Staaten zusammen das Komponente alle hier drin und alle hier drin so die haben wir alle erreicht die anderen noch nicht gesehen so jetzt wissen versuchen wir wieder mit irgend Knoten weiterzumachen vielleicht zufällig mit einem Knoten hier drin dann wissen wir wieder was alles erreichen alle Knoten hier drin und alle Knoten ihren als nächstes vielleicht erwischen wir hier so Ende das heißt wir reichen ansiedeln und eines hier drin und schlussendlich jetzt muss ich weiß nehmen neben den Knoten hier drinnen erwischen alles hier drin ja rot dann Geld dann grün dann weiß in dieser Reihenfolge so jetzt machen wir das das der 1. Schritt der zweite Schritt ist folgende ich versuche jetzt möglichst gut und dieses Bild noch mal zu zeichnen und das damit sie den möglichst parallel Eindruck bekommen so wir haben hier 2 Knoten 2 starke zusammen es kommen natürlich hier eine hier eine hier eine ja ja so das Stimme die beiden Bilder so weit über einen Deal zusammen zum 1 2 3 4 5 6 7 8 9 Jahre so jetzt machen wir Folgendes wir drehen sämtlicher kann den Gesamt Grafen um das heißt ich innerhalb der Staaten zusammen es Komponenten macht dass es keinen großen Unterschied war ja da das ist asymmetrisch jeder kann von jedem Knoten mit einem Weg erreicht werden aber es macht natürlich einen Unterschied zwischen den Staaten zusammen und Komponenten so war das heißt also wenn ich die kann man nehme die eben hier hatten dann haben wir plötzlich solche könnten ihren genau alles umgedreht Ruhe wo hier wie hier und da da ich sollte nicht so große Beispiele machen so ist jeder noch immer irgendwas Filter umfasst hier fehlt nicht aber dafür was so da muss jetzt gut so jetzt machen wir nochmal der tiefen Suche aber nicht mehr mit willkürlichen statt Noten sondern mit fein säuberlich gewählten start Knoten nämlich da kommen jetzt kam der 10 Spiele des die PR die Zahlenwerte die Zeitstempel die wir beim letzten Mal bei der bei der Grafen suchen mit eingeführt haben die wir den generischen Algorithmus mitgeschleppt haben ohne bis dahin zu wissen wozu das gut ist sie ändern sich daran aber F und D für jeden Knoten die das 1. Mal wenn besucht wird F das die Situation seiner finnische ist wenn er fertig produziertes also des Werner von Weiß zu Blau und Knoten kommt und
F von blau und 2 roten Knoten kommt und was wir machen ist jetzt in der Reihenfolge umgekehrt er in absteigender Reihenfolge waren die Knoten endgültig fertig Prozess jetzt in das heißt als in absteigender Reihenfolge dieser F härter so das 1. was jetzt betrachtet wird ist da wo wir zuletzt waren ist das Jahr und sie sehen schon von da aus kommt man in keiner nur zusammen Komponente weiterreichen so das nächste was wir betrachten in absteigender Reihenfolge das waren die Grünen das war zuletzt produziert wird das sind die Knoten in dieser Staaten Zusammenhangs Komponente das heißt die haben die größeren F der gegenüber den Knoten hier diesen Jahr bei der Grünen aber die haben die großen F wertet das heißt also hier wird gestartet mit und mit dem Staat Noten der den größten erfährt unter allen hier hat es egal welcher das heißt also was herauskommt bei dieser Grafen Suche ist das so jetzt der Alte andere ursprünglich Grüne ist die hier ja es ist innerhalb der zusammen es kommen werde egal von welchen Knoten sich starten um ihr sie nein sie wissen nicht dass es die gibt wir wissen noch nicht dass es sie gibt aber der Computer weiß noch nicht dass es die gibt was er macht ist blindlings einfach die den Knoten herzunehmen ja gar kein Sommer enden können sagen der nimmt ein Knoten der nämlich den Mitte müssen es wert und wir sehen jetzt hier Zufall oder nicht das hier tatsächlich er sowohl beim beim 1. Schritt also beim zweiten Schritt jeweils eine starke so sein muss comma rauskommt mehr genau also Sie nämlich und dann beliebigen da zusammen kommen sie könnten beliebigen hernehmen nur der Computer ist nicht klug genug das zu machen den nimmt etwa blindlings den er mir den größten erfährt der letztes fertig prozessiert war und kommt hier aus dieser Staaten zusammen es Komponente nicht mehr raus so der nächste ist die hier und Sie sehen schon was hier passiert käme natürlich weiter aber dieser Teil ist ja schon prozessiert kommt auch nicht mehr weiter und so geht es nach derselben Logik weiter also die Semantik der Bilder in der der haben Sie eine andere es bedeutet nicht dass ich zu wenn 2 dieselbe Farbe haben mehr wie nicht mehr so wie im 1. Bild das sie das im selben derselben Suche gefunden worden das bedeutet einfach nur im die Unterscheidung habe ich nur weißt du noch hier das nächste was jetzt wäre wäre die hier und so weiter und sofort jetzt habe noch die als das noch eine die hier zu dem Bereich jetzt aber nur noch die ursprüngliche roten also übrig und auch die gehen in der Reihenfolge so so und jetzt weiß ich nicht mehr weil sie nicht viel rum das hier ist so und soll und Sie sehen es ist die das was bei jeder einzelnen dieser suchen gefunden worden ist es genau eine Stadt Zusammenhangs Komponente weil das wo man noch hinkommt könnte schon vorher gesucht worden war und sie sehen auch dass das Ganze ganz auch unbedingt so sein muss das ist jetzt nicht einfach nur ein suggestives Bild ist sondern also tatsächlich immer so funktioniert der wenn Sie sich ansehen hier nochmal wenn Sie sich 2 starke zusammen es kommen ansehen die aufeinander zeigen wir 2 Möglichkeiten entweder so wie hier die wurden derselben aber so Prozess führt oder beispielsweise wie hier die wurden unterschiedlichen Phasen prozessiert so man denn derselben Phase prozessiert worden sind dann heißt es hier weil der Staat wird mir fast es wäre nicht dahin gekommen und das uns hier der letzte Knoten der prozessiert der der finalisiert wird es war der Start Knoten das heißt also hier oder er hier sind die letzten die auf aufsteigen letzten Club und diese kann sich hier Knoten drin der größer ist als jeder den den großen Prozess Zeitstempel hat endgültig also endgültige Finalisierung als alle hier drin mindestens einer nämlich der Staat wird möglicherweise auch mehr wenn die beiden hingegen die beiden Beine Zusammenhangs Komponenten hingegen in unterschiedlichen Phasen durchsucht worden sind dann wissen wir diese hier und war in einer Phase früher als die das heißt also sämtliche Finalisierung sterbe hier sind größer als sämtliche Finnlandisierung stand hier und damit ist automatisch so wenn Sie 2 egal ob so oder so wenn Sie 2 Zusammenhangs Komponenten haben wenn die prozessiert wird ist die Schule also in der 2. Folge in der 2. groß Phase jetzt dann ist die schon fertig posiert worden der man kommt wenn die Karten und umgedreht werden nicht von hier nach hier man war das schon fertig ist so das ist keine formale Beweise aber ich glaube ausreichend um klarzumachen dass es nicht nur suggestiv sondern es ist tatsächlich die Wahrheit ja ich also wie kann es natürlich kann natürlich diskutieren was ist Wahrheit also ich würde mal so sagen es gibt sehr viele Implementationen dieses Algorithmus und es gibt bis jetzt noch keinen der entdeckt hat das in diesem alle guten sind wieder drin ist das ist natürlich auch keine mathematische Beweis aber auch empirische Weise haben ihre Berechtigung ist bringenden deutlich also sind ein sehr deutliches Indiz dafür dass es gerade bei Sonne einfachen Algorithmus ein sehr deutliches Indiz dafür das ist doch richtig ist so sie sehen hier ist noch mal die wird der transponierte Graf definiert nämlich alle Karten und umgedreht und jetzt sehen Sie den Algorithmus 1. Phase wir das ist das was ich in diesem Bild hier angedeutet habe wir wiederholt berechnen wir tiefen Suche so dass wir am Ende so ein Bild rauskriegen dann drehen wir alle kannten um in dem wir den diesen Graf in hier es wäre doch noch mal gucken ob das alles wirklich so seine Richtigkeit hat mit der Kamera Marion ich glaube das wird gut aufgenommen drehen das um ja und rufen jetzt die es wieder auf in der Haupt- Schleife wobei ich glaube in diesem Fall braucht manchmal die FSB oder sonst was oder auch im in dieser dem dritten Schritt würde auch reiche es geht wissen ja von vorn rein das da nicht mehr viel passieren kann dass wenn der Staat zu haben Komponente bleiben so eben in der Reihenfolge von Absteiger in absteigender Reihenfolge dieser F Werte und bei jedem Baum den wir so generieren am Ende die ich hier jetzt bei diesem Bild einfach unterschiedlich farbig markiert habe also zweimal gleiche Farbe hat keinen Zusammenhang in diesem Bild mehr in diesem vor war in diesem war in jeder dieser Bäume ist eine starke Zusammenhangs Komponente nochmal diese diese Bemerkung unten die stand damals Komponenten von selber und D-Trust moniert sind natürlich identisch so stark zusammen der Komponenten lassen sich damit in die Nähe Zeit ebenfalls lösen denn wir nichts anderes gemacht als als das was wir vorher auch gemacht haben und die Bereiche des transponierten Grafen lässt sich mit entsprechenden Datenstruktur Verkauf natürlich auch in ihrer Zeit machen so jetzt das sind die Dinge die wir alle über springen sie sehen da fangen langsam die griechischen Buchstaben an und immer wenn griechische Buchstaben kommen würde es irgendwie ein bisschen schwierig und dann noch da bitte griechische Buchstaben und so weiter das ist nur ein griechischer Buchstabe aber dementsprechend häufig sie sehen es ist keine Schikane ihnen gegenüber wenn ich diese Punkte die überspringe so ja
nicht wie gesagt wenn Sie wenn Sie mir
das ich einigermaßen souveräner Form vortragen können dann kann es sein dass wir die Prüfung nicht dass die Grünen dann nicht mehr allzu lange dauern würde weil die Note schon relativ stark adjustiert ist also ein geht's an die Zuhörer das Videos die Frage war ob das Auswendiglernen reicht oder ob und wann verstehen muss also ich bin mir sicher das bei mir hat das nur bei mir mit Auswendiglernen nicht durchkommt am Auswendiglernen verstehen sind durchaus 2 Seiten derselben Medaille je mehr sie außen im Kopf haben also und daher je mehr sie von dem Thema im Kopf haben umso so besser können Sie damit spielt ja solange sie immer wieder die Details nachschlagen müssen können sich im Kopf damit rumspielen wenn Sie in den Gesang verstanden habe es auch kein Problem mehr das ist nicht mehr viel zum Auswendiglernen dar so das können wir alles lassen jetzt abschließen zu diesem Thema kommen wir noch einmal zu einer bildhaften Darstellung des Algorithmus das ist die 1. Phase wo wir in irgend einer Reihenfolge DFS Bäume konstruiert haben das möchte ich Ihnen für das Verständnis des Stoffes bis für die Vorbereitung des Herstellers für die Vorbereitung auf die Prüfung überlassen herauszufinden was hier passiert wurde es was die Staaten Noten sind dieses Bild so aussieht wie es aussieht jetzt sind die Kanten auf diesem Bild umgedreht rechts oben und wenn man jetzt die zweite Phase anwendet dann kommt tatsächlich das heraus was sie Staaten zusammen es Komponenten sind das möchte ich wie gesagt ihn überlassen in Vorbereitung auf die Prüfung gibt das nachzuvollziehen dass der Algorithmus der wir jetzt betrachtet haben tatsächlich das leistet und welche Knoten man in der 1. Phase dazu in welcher Reihenfolge Altstadt blutende der DFS er gewählt haben musste so topologische Sortierung hatten wir das also wie sie mit dem Thema Konnektivität damit durch schöne das ist auch nicht so tiefgehend topologische Sortierung ist ein sehr wichtiges Thema in verschiedenen Zusammenhängen das Bild zeigt es vielleicht schon ganz gut es geht darum die Knoten er den Grafen Dinge anzuordnen also nicht einfach nur die Knoten von links nach rechts zu durchzunummerieren oder anzuordnen sollen dann so anzuordnen dass der Graf das in den Grafen sämtliche Karten von einem Knoten längst noch ein Unrechts denn ich glaube irgendwo später kommt noch mal ein schönes Beispiel hier
wir haben einen Hafen links und das Bild das wir eben hatten haben noch mal wir haben denselben Grafen nur anders eingezeichnet nur Einlass in die Ebene platziert so dass alle Knoten auch in einer Reihe sind und alle kannten jeweils von links von einem Knoten längst zu einem Knoten weiter rechts gehen offensichtlich funktioniert das mehr wenn der Knoten Züge frei ist wenn man nicht wirklich Züge frei dann können Sie wenn Sie den Laden gehen in diese Sie vielleicht einmal rechts einmal rechts einmal Nachricht einmal nicht aber man muss immer wieder nach links zurück dann haben sie natürlich eine solche ist eine solche Anordnung natürlich unmöglich wenn der Graf züge frei hingegen ist das werden wir jetzt sehen dann lässt sich natürlich immer eine eine mindestens eine topologische Sortierung Kohle linear Ordnung aber finden das Wirkungen und den Algorithmus an
so dass ist eine topologische Sortierung oder grün ist auch ganz einfach wir rufen DFS auf tiefen Suche wieder in sie einen sich was Sie gesagt haben wir so wir rufen nicht nur einmal DFS auf sondern so lange bis alle Knoten rozent das heißt also wir müssen es keine Gedanken machen welche Staaten wir wenn wir werden einfach irgendein dann sind einige Knoten wenn die Suche wobei es rot nämlich die die Sie von diesen Staaten erreicht worden sind andere sind weiterhin weiß auf einem weißen nehmen und wieder einen Knoten und hoffen von dort wieder DFS auf und so weiter und so fort und wieder spielen die die F werte also der Moment 1 einen Knoten von blau auf Rot geht wenn er fertig prozessiert ist spielen hier die dominante Rolle das liegt einfach daran wie hier schon warum denn dem Kloten waren sind in die gut warum funktioniere nicht die die Quoten gut da die die Werte gut weil wie dieses Bild hier nochmal meine Zeit oder einem Bild kann ich das gut zeigen weil das konsistent ist das wenn ich 2 solchen gibt zu uns kommen da haben ist der Vertigo größer als der und ich 2 solche Gehabe ist auch der für Tiere größer als der der D wert ist nicht in diesem Sinne konsistent gucken Sie sich das wenn Sie wollen an Beispiel an dass es sich tatsächlich so verhält das heißt wir K wir wenden wenn die F Effekte in diesem Sinne Konsistenz in den kann man später im das was wir hier gemacht haben bei der Konnektivität können wir später konsistent absteigender oder aufsteigender Reihenfolge die Knoten durchlaufen und durchlaufen damit den Grafen von links nach rechts und genau darum geht es aber der topologische Sortierung von links erreicht zu durchlaufen so wir rufen DFS auf um die Ecke mit dem Hauptziel nicht den Graben trafen zu explorieren sondern für jeden Knoten ein erfährt denn er führt zu berechnen jedes Mal wenn wir den Effert eines Knoten berechnen sein also vor von den Blauen zu den roten geht wenn fertig prozessiert ist fügen wegen vorne und die Liste an und wenn wir alle Knoten prozessiert haben dann gehen wir die ganze ist aus das ist alles um eine topologische Sortierung zu erzeugen die Behauptung ist für jeden zyklischen Grafen gerichteten atypischen Hafen wird so eine topologische Sortierung erzeugt insbesondere folgt daraus dass es für jeden die sich in der zyklischen trafen tatsächlich auch eine topologische Sortierung geht sonst könnte erzeugen zu warum ist das der Fall na ja da kann man wieder dieses Bild hier nehmen also wenn ich mir schon so viel mehr mit dem Bild gemacht haben so lange gedauert hat dann möcht sitze ich hier gleich zeigen aber sie sehen das ist ja durch das immer noch das praktisch dasselbe Thema ist ja bekannt wieder selber Beispiel denn wir haben hier begonnen statt Noten und haben diesen ganzen roten Bereich gefunden dann haben wir glaube ich hier begründen Staaten und haben diesen Bereich gefunden dann hier in diesen Bereichen schließlich von hier aus und sie nicht weiter gekommen weil alle schon abgegrast war so was bedeutet das jetzt wieder die wenn die Knut wenn die mehr der wir werden die es in dieser Reihenfolge glaube dass was bedeutet das für diese 11 Werte für die Processing Tanz da betrachten wir wieder 2 Fälle den Einfall können wir hier dran betrachten nämlich eine Kante die von einem Bereich in den anderen geht also Wasser Wasser das überweisen so beweisen weder ein Vetter den Grafen nicht mehr für die eingetretene diesen auch für die jene Staaten sein muss Komponenten Fehler kann dem Grafen muss gelten der erfährt vor dem Start Noten es ist kleiner als der wird von den wurden so für diese kannten die hier von Grün nach Rot oder von grün nach gelb oder von weiß nach grün gehen für diese Karte kann sofort das automatisch weil diese Suche war früher als diese Suche also sind alle fertig Position hier früher als alle für die Prozession Jahr das heißt was uns interessiert sind alle anderen kannten nämlich die die innerhalb einer Suche sind da brauche ich jetzt ein bisschen Platz vielleicht morgen Stück Freude mehr wir haben eine Kante die innerhalb wo beide Knoten die in derselben suche prozessiert in derselben mit demselben Staat Noten der Fall dass in verschiedenen Phasen prozessiert worden sind 1 oder an einer Grünen in dem Bild den Hammer gerade eben erledigt das liegt aber daran dass das diese Suchphase später als diese Sofas ist aber wenn sie dergleichen vor ist dann haben wir ein Problem zu lösen aber genau dafür haben wir div es jetzt genommen dass ist jetzt noch einmal der Punkt wo ich er wo wo in dem bereits korrekte denke dass wir die S für verwendet haben erst wenn der Graf azyklisch ist mehr dann heißt das ist besonders gibt keinen Weg von diesem Knoten so diesen Knoten zu seiner Züge das heißt also wenn dieses Prozesses wegen früher wäre als endgültige Processing früher wäre als dieses endgültige Processing dann müssten da es 2 verschiedene suche Phasen gewesen sein das müssten 2 verschiedenen Staaten zusammen Komponenten gewesen sein eben nicht in derselben Stadt zusammen es kommen Inter die das sie früher als das so dass diese Suchphase wenn es bevor diese Phase beginnt dann wenn hier das anderes um es wenn hier diese Phase beginnt hier dann wäre wäre man hier gegangen und wäre hier weiter auf das in groben Zügen die Idee warum er es unmöglich sein kann dass dieses dieser Knoten fertig Prozess ist bevor dieser Knoten fertig prozessiert ist wenn sie in 2 verschiedenen Bereichen sind denn so ein zwar erschienen suchen sind dann hat am Maschener See in dieser Phase später als dieser Phase gewesen wenn sie in derselben Suchphase sind dann nicht der ja es gibt da keine Staaten zusammen es kommen die 1. besonders Kommunisten Knoten ja dann wäre dann wäre die
Suche von hier nach hier gekommen nicht umgekehrt das ist mein Versuch in das näher zu bringen ohne dass wir da in diese griechischen Buchstaben einsteigen weiß nicht sind sie dann überzeugt oder nicht nicht Vorsicht jeder überzeugt es muss sagen warum nicht ja ja okay ok versuchen was für sowas vielleicht einem Beispiel zu machen so zum Beispiel so Frau schöne kannten einfügen so das wir das Beispiel im März als 1. Suche Knoten her und vielleicht den hier da haben sind von hier aus der hier der Herr und der er erreichbar und zwar fertig prozessierte Frauen darunter zurück zu erst der wieder runter zu erst der zurück dann der zurück dann der ja ja okay die Reihenfolge von in der Verhalten gut 1 2 oder umgekehrt je nachdem durch zu erzielen werden 3 und 4 der Stadt würden hat immer den höchsten erfährt genau oder sind wir anders und gesagt haben suchen haben wir das genau jedes Mal wenn man von einem Knoten aus zurückgeht wird der wird gesetzt weil dieser Knoten in dem Moment fällig und sie das und die genau das hat die mir zurück weil nix mehr zu tun es einen Knoten so jetzt uns denn her kommen nun bis dahin dann sind die dann sind die weiteren Werte wir haben 1 2 3 4 jetzt kommen 5 ne halt dann der 5 und hier 6 was niemals das nächstes ist das Beispiel war vielleicht ist doch nicht so so gut Mahnung bis jetzt weiter so dann ich mach mal jetzt keine Farbe mehr weil die so weil weil die jetzt dann falsch sind also das wäre dann zum Beispiel der nächste statt Noten erreicht die beiden und natürlich dann sich selber wo sie immer 6. wir hier 7 8. 9 und dann wäre noch ich mach das mal mit Kreuzen sehen wir halt hier noch sehen 11 12 ist das so weiter über das Beispiel nicht alle nickten so richtig denn es war nicht so richtig klar geworden was ist mit der 12 okay ich glaube das Beispiel stimmt nach so ja wurde alle sie freie überhaupt erst setzen und dann erhöhen oder also E-Plus Plus oder Plus für Sie ich glaube das ist irrelevant das also es ändere nichts an der relativen Reihenfolge der Werte so und so warum warum es gilt das für diesen Knoten die Reihenfolge ja wir hängen die immer Handy die Knoten in immer am Anfang an das heißt also was wir Männer herausbekommen sehr genau in umgekehrter Reihenfolge als diese Zahlen hier das ist richtig um also was muss man so ein dass sie dass die Reihenfolge richtig und wird genau Städte steht auf der Tafel drauf hier Wayne Mike Gluten der finalisiert ist reine die am Anfang der Liste also an einen was am Ende rauskommt ist eine Liste der wo am Anfang nur Freund 12 steht da kommt 11 dann kommt sehen und so weiter in dieser Reihenfolge man muss natürlich nicht die Nummer rein das ist das ist schön das weiß man vorher dass die Nummer 12 11 10 so weiter stehen hat natürlich muss man einer ALDI des Knoten rein kann Pointer auf den Knoten oder was auch immer so warum ist das jetzt korrekt für einen kann für eine Kante hier zwischen 2 verschiedenen suche Phasen haben schon gesehen diese Phase war früher als die denn wenn die früher gewesen wäre dann wäre es eine Suchphase gewesen da von dieser Phase von 8 aus zu viel weiter gegangen wenn die Suchphase von dem Club mit Nummer 8 früher gewesen wäre als sie sofort mit Nummer 4 also es geht nicht um bei 2 Knoten die innerhalb derselben Suchphase was bei der Kandidat derselben Suchphase hier durchlaufen wird muss es nicht jetzt muss man mal kucken der muss nicht genau die die spannende bekannt dass endlich die hier wenn wir sind jetzt wir unsere gelaufen wir sind von hier ist es zu 2 gelaufen und dann zu 3 glaube ich oder im Moment ich was ist hier verkehrt ach gewesen doch von ihr ausgelaufen okay dann ist die Spanne kann sie nicht die von 3 nach 2 sondern die von 4 nach 2 denn wir sind ja hier rübergelaufen wir haben diese Kante gar nicht oder dar die Karten dem Baum drin sind die sind und sparen diesen sind offensichtlich richtig mehr die Kanten sind spannend warum also die richtig rum wenn sie falsch rum wäre wäre sie eine Beckford Art ja wer im Baum wenn der 2 Knoten miteinander das ist okay das ist genau der Fall den wir hier haben wenn das hingegen andersrum ist also der ganze Baum erst der geht hier noch unten winzigen andersrum wir da der Beckwourth kann dass man schon festgestellt dann ist dann Anzüge und sie haben nicht so werden es auch Züge entdeckt also der das kann man auch verwendet Algorithmus zum Auffinden von Zügen zum wird überzeugt okay denn wenn das mit den ganzen fiese auch verstehen können gut an hier mir gar keine fließt mehr vor wir kommen es weiterhin vor ok hier ist das
Beispiel Sie 1 1 Mann der mit einem Beispiel tatsächlich durch Text hier dieses Beispiel ich ihn wieder ans Herz für ihre eigenen Betrachtungen und damit sind wir mit dem Thema topologische Sortierung auch fertig ich will Ihnen sagen wofür das wichtig ist topologische oder eine der wesentlichen würde wichtig ist die ganze Reich Projektplanung es gelegentlich die einzelnen Teilaufgaben die zu machen sind müssen wir sind Knoten und unbekannte bedeuten Abhängigkeit des eines erledigt sein bevor das andere beginnen kann und wenn sie beispielsweise alles auf eine Maschine zum Beispiel machen wollen zum Beispiel diverse Software Programme Schritte auf auf dem Computer oder sonst irgendwas alles auf einer Maschine in der Fabrik oder so machen wollen dann müssen Sie natürlich sehr realisieren anhand einer topologischen Sortierung das jemanden das später kommt was auf das andere warten muss angezeigt durch mehr kannte und wenn sind Züge drin haben in diesem der dann heißt es so B warten wir auf CC muss auf die Weiden die muss auf warten das klappt nicht so jetzt comma zu dem anderen anschaulichen Thema bis überhaupt glaube ich recht anschaulich hier in dieser Veranstaltung Bieber die des Grafen darum ich bin immer wieder eine Rolle wir wollen Sie recht früh einführen auch wenn wir vielleicht nicht unmittelbar Nutzen sofort haben dpa die Art und Weise wie die Partie der Grafen gezeichnet werden ist einfach wollen wir sie haben eine Zeit Knoten Menge sie haben 2. Teil Menge ich glaube wir werden einen Kontext schon mal Bipartite Grafen hier an der Tafel letztes Mal davon dass es mal und alle kannten gehen von links nach rechts tut egal wie Hauptsache von links nach rechts es gibt keine Kanzel von links Nachrichten zu es gibt keine Kanzel von rechts nach rechts Zuweisung das Problem ja sie haben auf der einen Seite der Menge von Aufgaben Flandern sollte der Menge von von Bauarbeitern was auch immer Maschine oder was auch immer und sie wollen beispielsweise jedem hier jeder Aufgabe na gut er umgekehrt das sind die Aufgaben das in die Maschinen sie wollen jeder Aufgabe eine Maschine zu zuweisen oder ähnliches das ist natürlich in der Realität müssen komplizierter aber da steckt als Kernproblem immer drin so dass bei die der Grafen 1 die Partitionen gewannen zurück auf die Folien 1 die Partition eines unehelichen Grafen habe ich vergessen zu sagen wir reden immer von ungerichteten Grafen das eine Partition des Knoten der Knoten Mengen 2 disjunkte Teilmengen als links bis rechts oder umgekehrt jetzt ist die Form ebenso die sog Grafen induziert bei A und B sind beide leer wir hatten so Grafen ganz am Anfang was heißt das das bedeutet der so Graf injiziert fahren das aber dass es Bild zu Graf induziert von aber es sind diese Knoten in A plus ihr Know-how in die kannten die nur innerhalb von sind die gibt es nicht das hat der und das selber des so kann man also alternativ das auch vom denn ich habe gesagt alle kann müssen aber nach rechts gehen hier die formale Definition sagt die kannten sie ihr Diplom längst in kannten frei liegt und Karten frei was er sich dass er ist so und wenn ja wenn ein gab sich so zerlegen lässt wie ich das sie gezeichnet habe dann soll die Partie geht so und da mal gleich schon eine Charakterisierung die auf sagt dazu ist das natürlich nicht jeder Graf Pieper geht ist ein unehelicher genau dann wenn er keinen Kreis von ungerader Länge enthält und der zweite Teil des Lammers ist dass man das auch wieder Lehrzeit rausfinden kann für Beweise es ist nicht schwer bevor wieder auf der Folie weitermachen mache ich das eigentlich einfach mal an der Tafel wenn Sie einen die Partie den Grafen haben denken Sie natürlich Kreise drin haben aber auch wenn man sich vorstellt wie sich den Kreis durchgehen von links nach rechts von rechts nach links von links nach rechts von rechts nach links von links nach rechts und von rechts nach links geschlossen es geht gar nicht anders als dass dieser Kreis gerade länger hat ich denke das einsichtig jetzt die umgekehrte frage wer also wenn ein Graf bedeutet es dann hatte nur Kreise gerade einige wenn überhaupt Kreise hat das ist offensichtlich jetzt die umgekehrte Frage wenn der Graf man müsse man das jetzt sagen wenn der Graf einen Kreis gerade länger Nein wenn dann nur Glück wir ich ich war erst mal an und dann weißt wer weiß ich was ich wirklich sagen wollte mehr
so wenn wir einen kreis ungerader Längen Grafen haben also ungerecht das so ja so so 3 4 5 6 7 8 9 so wurde mir ein Greis und länger haben dann kann der nicht in dem die dortigen Grafen drin sein so rum ist die Logik was beweisen müssen warum kann der nicht im Ibaditen Grafen drin sein na ja wir fangen mal irgendwo an und sagen der zu Menge A danke der zu Menge B Sieger der wieder zu aber der zu B der zu aber worum wird mache ich immer so große Kreise A des ja und jetzt haben wir hier ein Problem also Sie sehen wie ist das wenn ein Graf Pieper Titel ist dann hat er nur Kreise gerade Linie so es jetzt in die Logik von dieser Richtung wenn ein Graf mehr genau das war genau die Kontraposition also das heißt dass ich über meine Sinne Wesen ist das nicht schön wenn ein Kreis nur gerade länger hat so ihr 2 ich glaube ich weiß es kann der Algorithmus ins Spiel schön Sie hatten ich aber die sie nicht abwürgen die ja genau das getan sich nicht schließen aber erst jetzt weiß ich wieder wie machen breiten Sure Start mit um den Knoten der Graf hat jetzt nur Cykel gerader länger so der gibt der Staat nun zu ich meine Nummer dem Baum auf den gebe ich jetzt allen B denn einen so jetzt geht das irgendwie weiter zur nächsten Schicht die wieder zu aber gehört so die ganzen Knoten und die nächste Schicht gehört wieder zu Bild und so weiter also das in diesem Fall bereiten suchen nicht liefen Suche was wir jetzt hier machen und so weiter so welche Kanten gibt es es gibt sie einen sich es gibt 2 Arten von kannten prinzipiellen 1 BFS Baum einerseits Kanten zwischen 2 Schichten sowie der hier oder kannten in derselben Schicht zwischen sollten ohne sämtlich dem andere könnten gar nicht geben eine Karte die eine Schicht überspringt kann es nicht geben dann wäre nämlich dieser Knoten hier gewählt worden und wäre wäre Teil von diese kann gibt es nicht das macht die Sache schön übersichtlich und diese kann der kann es nicht geben oder man denn diese könnte denn immer wenn man meint an diese kann dich ich muss das jetzt mal farbig zeichnen sonst gibt es keinen Überblick mehr Musik diese Kanther hier auf seiner Ebene kann es nicht geben denn wenn ich den einen Weg hier nehme er falsch schon gleich am Anfang falsch abgebogen wenn ich den einen Weg immer hier hier und den anderen Weg hier nehme ich hier hier wir natürlich beide gleiche länger plus diese kannte des Ungarn bitte nicht das heißt also kannten zwischen 2 Knoten derselben Schicht kann es nicht geben wenn der Graf keine Züge hat keine es keine Siedlung Ladelänge länger hat diese kann zwischen 2 benachbarten machen natürlich kein Problem und damit ist es nicht bewiesen sondern wir machen derzeit Algorithmus um 1 die bei den Grafen wirklich Bierparty zuzulegen so im Grunde haben war für heute zumindest das Thema debattiert auch ja durchgezogen das was hier steht sie sehen ab 3 BFS Telekommärkte Komponent ok versichert unterschlagen habe ist dass sie das natürlich zusammen es Komponenten bestehen kann ich denke das ist jetzt ein Schritt den der keine großen intellektuellen Aufwände auffordert oder und so weiter wenn die Distanz wenn dies das Land gerade ist dann soll es zu gehören wenn sie ungerade soll zu Beginn eines genau das Gegenteil von dem was ich gemacht habe oder wie wenn sonst gerade ist sogar das wichtige ist es gerade zum Start Noten gehört zu haben Samsung gerade ist mir zu billig so das ist
damit aber noch heute geht es aber wirklich gut voran aber auch nur deshalb weil ich mich mit den fies und so weiter nicht hier befasse weg weil ich sie nicht damit befassen sonst würde doch mittendrin in den und sie würden wahrscheinlich noch in Frage stellen wo ich Schwierigkeiten habe die sofort aus dem Stegreif zu beantworten so das nächste ist was also bekannte ist schönes Kinderspiele vor kenne ich nehme an auch in Ihrer Generation kennt man noch das ist das Vorhaben die Kohle aus der Mann bei Ihnen der man doch ok es ist es nämlich verdammt alt gefühlt das so warum funktioniert das es funktioniert deshalb ich habe natürlich nicht irgendwo angefangen sondern an einer von 2 möglichen Stellen wo es funktioniert nämlich hier oder hier was ist bei den beiden Toten besonders die über den anderen genau oder gerade ist hier ungerade und gerade gerade und dementsprechend war gerade hier so was jetzt betrachten ist die etwas andere Situation wo das ganze geschlossen wird also wo jeder Knoten geraten gerade hat zum Beispiel so hat die Rettung geraten gerade und offensichtlich können Sie jetzt irgendwo anfangen zum Beispiel hier und irgendwie durchgehen das ist ist das Haus Fällen legt Google aus und jetzt weiß ich nicht mehr so irgendwo durchgehen um und um einmal alle kannten genau einmal durch das Gedicht oft um mich habe jede Kante exakt einmalig durchlaufen das was Briefträger machen muss mit jeder Straße also idealerweise er ist sich keine keine Straße zweimal kommende Renditeziele sie selten vor dass ist bitte ja gut rechts und links okay das nur 2 verschiedene strahlte kann sehr 2 verschiedene Straßen auffassen rechts und links mehr einer wenn alles einmal rechts macht und allen danach also links macht und das 2 verschiedene kannten so warum funktioniert das immer das kann man natürlich auch ein Betrag mir einmal im ungerichteten und einmal auch eingerichteten Fall da haben wir die Situation eine etwas andere damit das Ganze klappt warten müssen so so schon so so nun schon so und so so so auch schon was gemäß einigermaßen sehen kann erklären oder genau das Haus von Wedel aus nach einem Erdbeben in der Tat das zeigen die bisherigen sein die nicht ich habe jetzt ich habe jetzt gerade was gelesen dass irgendwelche promenierte Prominente sich er sollte was darüber sagen was sie wie sie sich gegen Sandy schützen und und eine besonders prominente man 10 Uhr muss er hat von Celle gesprochen statt von Sandy ja gut so was ist hier die Jäger die konkrete Situation die sowas möglich macht die Chor der konkrete Grund warum das hier möglich ist ist sehr ähnlich nämlich an zahlreichen gleich an ausgehende Kanten so und damit müsste damit ist denke ich zunächst einmal einsichtig dass man dass man in solchen Fällen egal ob Zupke im ungerichteten Fall haben hatten hier alle kannten geraten gerade oder eingerichteten fahl wie wir sie haben 1 2 reingehen ausgehende das wir dann sowas hingekommen weil wir starten und worum es müssen sich aber vorstellen gehen ein 2. es habe eine kannte die reingeht aufgefodert wir haben also eine Kante mehr die rausgeht angehen als eine K als die reingehen das heißt wir haben mindestens eine kann die raus Geld nehme eine sehr das Argument haben hier eine Kante aufgefordert die reingeht geht aber noch keine die rausgeht wieder und so weiter und so fort so lange bis sie am Anfang wieder zurückkommen denn danach greift dieses Argument nicht mehr dass wir noch mehr kannte fürs Ausgehen habe oder beim ungerichteten Fall so wie es hier hatten starten irgendwo denn irgendwo hin gut dann die Tante weg und geradezu eine ungerade Zahl bedeutet insbesondere größer 1 vergrößern 0 Störung größer gleich 1 wir haben also bekannt und weiter zu gehen irgendwohin seines Arguments wir haben eine kann weiter zu gehen und so weiter bis wir am Anfang sehr ja habe ich sie davon überzeugt dass man auf die Art und Weise einen solchen Juli wären Work hinbekommen das heißt alle könnten einmal durchlaufen bin habe ich damit überzeugt das ist gut dass ich jetzt ich weiß nicht woran es liegt dass sich keiner meldet aber kann er ich hoffe ich habe sie nicht überzeugt das ist das Problem wirklich was Problem ist es nicht verstanden was davon gesagt worden was eigentlich will oder haben Sie versteuern worauf ich hinaus will genau warum er sich alle kannten und offensichtlich die Antwort die die Frage stellen heißt sie beantworten es wäre natürlich nicht alle Karten mit dieser primitiven Art und Weise gefunden was kann passieren also insbesondere also hier zum Beispiel ja hier so gutes Beispiel ich meine das noch mal daneben ja so und wenn ich jetzt hier los der und dem die nehme die nehmen die nehmen die nehmen die nehmen die nehmen mehr wer nur geht nicht mehr weiter ich habe nicht alles durchsucht ja wirklich man das also besser ein und das Ganze funktioniert natürlich auch im gerichteten nicht wirklich so wie ich das jetzt gezielt habe so wie hier Munichen Fall nicht wirklich funktioniert ja da müssen wir wieder genau hingucken so einer ein Juli wir Work benannt nach jemanden so zu meinem sollten sie auch noch teurer er ist ein geschlossener Weg der jede Kante enthält genau einmal enthält sollte man dazu sagen sich als habe aber ich glaube der Definition von Work war schon enthalten dass jeder kann nur einmal vorkommt so und wenn ein gerade gar eben ungerichteten gaben wenn der wird wenn er grün gar dieses
Knoten gerade ist dann ist der oder lasch dieser Chor Graf und das ist natürlich kein Zufall dass diese beiden Definitionen beide werden so zusammenkommen denselben Namen tragen genauso bei gerichteten Grafen 1 ist der Eulersche so ich das angedeutet hatte hier rechts der Zeichnung wenn die Anzahl der ausgehenden Kanten der außen gerade gleicht dem in gerade ist die Anzahl der reingehen Karten für jeden einzelnen Knoten so und die Behauptung ist also zunächst einmal der ein Graf hat genau dann solchen und so ein oller schon weg mit dem man jede Kante einmal durchlaufen kann genau einmal durchlaufen kann genau dann wenn der zusammenhängend das ist natürlich notwendig wenn ich zusammenhängendes für werfen sie ist natürlich nicht und wenn Eulersche ist in dem Sinne wieder oben ist so die Notwendigkeit ist klar dass Hammer wenigstens sicherlich schon mal einen gesehen wenn wir das nicht haben nein gerichteten Fall das für jeden Kloten Jansa eingehende kann gleich ansah rausgehen Karten ist wenn das nicht haben also wenn wir zum Beispiel zu wenig rausgehen Karten haben eine weniger dann klappt das natürlich dann bleibe um 1 hier hängen und wenn wenn das 1 zu viel gibt es die die rausgeht denken wir die dann können wir eine dieser Karten niemals einen geschlossenen Strecken Zug mit drin haben also dass man notwendig und wieder wie wir es eben hatten bei topologische Sortierung was freudiger mal vorkommt der dass diese war dass diese Eigenschaft hinreichend ist dass der Graf und das ist das ist wieder mal konstruktiv bewiesen worden ist ihn aus der Mathematik der wird der Begriff konstruktiver beweist ist da schon gegen kommen was ist dann einig konstruktiver beweist kann selten auf aber tauchten wieder auf also salopp gesagt es sei nicht konsumtive beweist wenn man ein 1 ein irgendeinen Wert beispielsweise eine reelle Zahl sind ohne genau zu wissen welche das eigentlich ist ja aber wenn man sie nicht konstruiert hat immer sinnlich angegeben hat das ist in manchen Fällen in der höheren Mathematik notwendig bei uns eigentlich in der Regel nicht das heißt bei konstruktive Beweise heißt man konstruiert schon eine Lösung ein Ergebnis im Beweis trennen und dann das bedeute dies aus als das der Beweis der mathematischen Beweis ein verkappter Algorithmus ist wenn das der Fall ist das der beweisen verkappte Algorithmus ist kann auch ein Schritt weiter gehen sowie und sagen okay durch Eingabe eines Algorithmus und dessen Korrektheit natürlich so wie sie diese Algorithmus aus der muss ein bisschen damit härter sein als das was Sie hier gemacht haben mit der das ist das Haus vom Nickel aus seien gesehen schon im ungerichteten fallen hier funktioniert nicht mehr sicher wenn nicht alle kannten so in welcher Form muss das jetzt komplizierter seien der 1. jeder lange weg braucht ein 1. Schritt das wissen Sie ja wir wir haben immer einen aktuellen Knoten x den setzt da irgendwo auf irgendein Staat Noten den wir als Paar mit übergeben bekommen haben ja wir haben können wir keine mehr und um starten und übergeben bekommen muss nicht sein dass der Staaten übergeben bekommen kann auch sein dass wir selber innerhalb der Tour werden hier erlauben Sie dem dem Aufrufer der der Methode Euler dass er den Staat nun spezifizieren kann und das ist unser 1. Knoten und der Weg der Work besteht zunächst mal nur aus diesem Staat Noten und dieser Borgweg wird Schritt für Schritt natürlich wachsen immer weiter durch eine Kante und den neuen aktuellen Knoten auf der anderen Seite dieser könnte so so lange das ist ein bisschen habe ich weil ich in der Schleife wir haben und innerhalb dieser Schleife eine Rekursion so wir betrachten es als im aktuellen Knoten ich sollte noch dazu sagen das kommt da er später wir machen uns das Leben hier einfacher indem wir eine Datenstruktur für Grafen wo wir den Knoten in die Karte die wir haben immer nachdem wir sie jetzt betrachtet haben sofort rausschmeißen so dass wir nicht so dass es nicht das sehen kann dass wir diese kann später nochmal aus Versehen berühren es reicht für diese es würde natürlich für die Korrektheit reichen wenn wir die Kanten nicht rausschmeißen sondern irgendwie als prozessiert leben nur dann mitbekommen Laufzeit Problem weil wir öfters mal zu zusehen kannte kommen würden und jedes Mal wenn wir zu dieser kannte kommen würden wir verstellen die er schon prozessiert das kostet uns unendliche Laufzeit das habe man gerne Datenstruktur wo diese Kante rausgeschmissen würden komme auch später nie wieder zu dieser kannte kommen und Laufzeit verbrauchen so wir man uns jetzt eine kann der die noch da ist also solange der aktuelle Knoten nicht noch Nachbarn hatten den uns sondern Nachbar kann der eine Kante in zu diesem Knoten wir erweitern den die organischen Work um diesen diese kannte und den anderen Knoten die gehen zu diesem Knoten zu diesem können dass setzen sagte der Knoten wächst ja also wir machen wirklich den Strunk ja das ist unsere kann zur Ehe mit dem es gerade haben das ist unser aktuelles X X Arbeit und das ist das Y und das wird unser neues X bespringen sozusagen von einem er wird wesentlich Jahren angefangen in dieser Iterationen und sprechen darüber das wird unser neues X ich denke das es so wird klar hier kommt der Punkt den ich ihm sagte wir schmeißen die kann daraus weil sie nie wieder sehen wollen so jetzt betrachten wir die aktuelle selig werden wie Sie gerade da ist und jetzt kommt der rekursive Aufrufe jetzt rufen wir noch mal mehr jetzt allen Knoten diese hier auf dem Weg haben hinauf diese rekursive mit oder insofern nämlich das zurück was ich früher gesagt habe natürlich keinen oberste Rekursionsstufe kann der Tag der kann der Knoten natürlich durch die durch die Subroutine selber gewählt werden sie mir beim rekursiven Aufruf es ist natürlich keinesfalls so das er in diesem rekursiven Aufruf dann derart der Knoten von dem so starten soll beliebig gewählt werden darf sondern der muss schon jetzt hier vor gegeben werden als dieser V E und das Handy hier ein was wir hier machen ist also eine ganz merkwürdige
Sache die wir keine Sorge alles im Griff ich will versuchen das zu veranschaulichen was hier passiert so was sie einmal hier formal sehen ist das ist der wo auch jene bisher konstruiert haben jetzt wir rechnen wir die rekursiven Aufruf eine ganze Reihe von weiteren boxt und was können die Regeln die irgendwie zusammen so was bei was wie kann man sich das vorstellen wir haben das ist der das ist das ursprüngliche V 1 mit die Kanten werden wie nummeriert das es I 1 das ist V 2 das ist 2 vor 3 und so weiter bis wie sieht es da aus dem Fokker EKV K plus 1 war Eker Fokker plus 1 so bekommt das Volker Plus 1 wäre es egal dass ist die Nummerierung jetzt wird hier über eine ein Wort zur sich welche mächtig kannten ihn noch dran sind die noch nicht ausgeschlossen worden sind da hier über alle und jeder von den ersetzt diesen Knoten er das heißt natürlich nicht dass diese Knoten jetzt jeweils nicht mehr drin sondern natürlich Brockton sogar zweimal dran denn was jetzt passiert ist hier geht's erstmal mal da keine das ist der Rock wie einst war vor allem das der der 14 schließlich hier dann passiert bei vor 2 das selbe hier geht's erstmal mal also immer schon besonderer hier alles machen dass das noch passt vor 3 hier jetzt irgendwie Land und so weiter und so fort bis es muss immer gucken wo ist bei Fokker plus 1 wird nicht aufgerufen das heißt hier bei Fokker ist das letzte und hier ist ein weiteres Fokker plus 1 das Dorf was diese 3 Zeilen vordergründig sagen aber natürlich passiert noch viel mehr als das was ich jetzt gezeichnet habe den das geht ja rekursiv dann weiter ja ich hier irgendwo wenn da noch kannten sind dann geht ja hier noch weiter und von dem aus geht es noch mal hier weiter ich kann das nur so ein bisschen andeuten ja wenn hier noch Karten übrig sind wenn es da weitergeht dann geht es hier noch ein bisschen weiter und hier noch ein bisschen weiter und so fort ja das ist auf die Art und Weise bekommt man das sehen Sie sehen die überall wo noch irgendwo Platz ist durch diese Rekursion über also noch irgendwo kannten übrig sind können wir noch kannten da können wir dann noch das solche weitere kannten einfügen kann mir da noch weitere Works einfügen und sie Rowdys hinausläuft durch diese Rekursionen es ist völlig unmöglich dass sie irgendwo noch danach irgendwelche weiteren kannten untersucht gegeben sind das hört ich habe das jetzt die letzte Zeile vergessen die Sorge ist dann das Endergebnis und würde mit Rede hören zurückgegeben so jetzt die Behauptung wie üblich 2 Behauptungen 1. der Algorithmus arbeitet korrekt und 2. also wie war das korrekte Resultat zum arbeitet korrekt gehören immer 3 Dinge man sich das mal klar ich weil sie weil sie das der GDC 2 sich lagen machen konnten 1. er macht nur definierte Schritte greift beispielsweise nicht auf er Index minus 1 zu oder oder auf eine auf ein Objekt wurde 0 bei der drin ist also Nein auf 1 Kg Jahre Klassen Typ in der 0 Pointer steht versucht den nicht validieren und so weiter 2. terminiert Algorithmen sind keine Ampelsteuerung Ampelsteuerungen sollten nicht terminieren außer durch kontrollierten einge- von draußen Algorithmen sollten terminieren denn sie sollen deren Ergebnisse am Ende liefern bei Determination das Ergebniss unser sehen und drittens natürlich das Ergebnis ist korrekt also diesen Wachs goldgestickten eigentlich 3 verschiedene Dinge drin wobei in den meisten Fällen die wir hier betrachten der 1. period trivial ist das keine undefinierten Schritte passieren der zweite Punkt das ist terminiert das ist manchmal trivial manchmal ich hier ist denke ich offensichtlich weil wir ja in jedem Schritt kann bekannten rausschmeißen und das Land hat sich auch die korrekt mehr geben sie wird es meistens der der Teil der ganzen Sache der müssen komplizierter ist hier noch kleine Erwähnung für Gerichte die Grafen am Sitz in die undichte gaben gesehen für Gerichte der Grafen brauche man eine kleine Veränderung nämlich das wir hier in Schritt 2 nichts sagen es gibt noch eine kannte die die jetzt in sie denn es zu diesem Knoten zum aktuellen wurden sein es gibt noch eine rausgehen erkannte das aktuellen Klotens natürlich das ist natürlich die kleine Änderung die passieren muss gut diese historischer Bemerkung mehr glaube ich brauche das finden Sie über das können Sie ich glaube dass Wikipedia gutgeschrieben diese Historie von von vor er von dem Königsberger Brücken Problem wo er festgestellt hat dass man nicht über alle Brücken das sind die Karten seines Grafen dass man nicht über alle Brücken genau einmal gehen kann und dann wieder an seinem Ausgangspunkt zurück ist so Korrektheit bei in Datschen und die also bei gemeint ist mit dem Deutschen hier immer vollständige Induktion ja eigentlich ist das ein bisschen also oder Induktion versteht man im Deutschen eigentlich gerade was unvollständig ist also ich vergessen wir mal die Sache mit etlichen und so weiter muss auch Induktion unter Induktion versteht man in deutschen im in der Wissenschaftstheorie eben eher schließen vom Einzelfall vom Beispiel auf die allgemeine Regel das natürlich genau das Gegenteil von vollständig es ist gleich unvollständig aber im Englischen hat sich's das bedeutet in Touch natürlich auch normale sehr wie im Deutschen aber es hat sich eingebürgert auch bei Vorschlägen zur im mathematischen Sinne von in Datschen und zu reden so dass hier also eine gewisse Ambivalenz in dem Wort drinsteckt so
okay zum Glück ist die Veranstaltung vor beiden habe ich bis nächste Woche Zeit mit den Beweis zu überlegen gut dann dank ich Ihnen heute
Loading...
Feedback
hidden