Optimal Trees and Branchings II / Shortest Paths I

Video thumbnail (Frame 0) Video thumbnail (Frame 4879) Video thumbnail (Frame 6866) Video thumbnail (Frame 16017) Video thumbnail (Frame 23648) Video thumbnail (Frame 25517) Video thumbnail (Frame 27442) Video thumbnail (Frame 36125) Video thumbnail (Frame 44758) Video thumbnail (Frame 53617) Video thumbnail (Frame 61950) Video thumbnail (Frame 69017) Video thumbnail (Frame 70809) Video thumbnail (Frame 72604) Video thumbnail (Frame 77712) Video thumbnail (Frame 81104) Video thumbnail (Frame 82984) Video thumbnail (Frame 85761) Video thumbnail (Frame 89177) Video thumbnail (Frame 91062) Video thumbnail (Frame 94321) Video thumbnail (Frame 96779) Video thumbnail (Frame 101327) Video thumbnail (Frame 103854) Video thumbnail (Frame 105747) Video thumbnail (Frame 119674) Video thumbnail (Frame 132341) Video thumbnail (Frame 135412) Video thumbnail (Frame 137471)
Video in TIB AV-Portal: Optimal Trees and Branchings II / Shortest Paths I

Formal Metadata

Title
Optimal Trees and Branchings II / Shortest Paths I
Title of Series
Part Number
6
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...
Kante Stress (mechanics) Greatest element Equals sign Maxima and minima Set (mathematics) Weight Subset Connected space Zusammenhang <Mathematik> Network topology Modulform Summation Mathematical optimization
Kante Decision theory Compass (drafting) Weight Graph (mathematics) Complex (psychology) Mathematical optimization Fundamental theorem of algebra
Kante Group action Weight Graph (mathematics) Set (mathematics) Equation Inequality (mathematics) Inclusion map Duality (mathematics) Inclusion map Film editing Subgraph Graph (mathematics) Mathematical optimization Category of being Proof theory
Kante Inclusion map Stress (mechanics) Kopplung <Physik> Subgraph Graph (mathematics) Weight Graph (mathematics) Set (mathematics) Mathematical optimization Category of being Proof theory
Graph (mathematics) Weight Lemma (mathematics) Maxima and minima Feasibility study Theory Airfoil Insertion loss Graph (mathematics) Uniqueness quantification Vertex (graph theory) Mathematical optimization Proof theory
Kante Stress (mechanics) Weight Graph (mathematics) Graph (mathematics) Vertex (graph theory) Mathematical optimization Theory Directed graph
Kante Stress (mechanics) Weight Graph (mathematics) Maxima and minima Theory Connected space Hausdorff space Zusammenhang <Mathematik> Graph (mathematics) Musical ensemble Mathematical optimization Alpha (investment)
Kante Rule of inference Stress (mechanics) Compass (drafting) Graph (mathematics) Weight Equals sign Maxima and minima Binary file Sign (mathematics) Function (mathematics) Graph (mathematics) Theorem Vertex (graph theory) Quote Mathematical optimization Maß <Mathematik> Proof theory
Kante Stress (mechanics) Field extension Correspondence (mathematics) Graph (mathematics) Musical ensemble Quote Weight Mathematical optimization Maß <Mathematik> Number Mach's principle
Stress (mechanics) Series (mathematics) Axiom of choice Correspondence (mathematics) Graph (mathematics) Weight Moment (mathematics) Rekursiver Algorithmus Set (mathematics) Transformation (genetics) Hausdorff space Phase transition Arrow of time Vertex (graph theory) Mathematical optimization
Standard deviation Graph (mathematics) Weight Thermal expansion Maxima and minima Bound state Forest Network topology Phase transition Travelling salesman problem Theorem Negative number Mathematical optimization
Standard deviation Graph (mathematics) Maxima and minima Complete metric space Enumerated type Weight Total S.A. Element (mathematics) Independence (probability theory) Forest Subset Boom barrier Estimation Function (mathematics) Matroid Vertex (graph theory) Summation Mathematical optimization Physical system Length Directed graph
Graph (mathematics) Unit of length Normale Set (mathematics) Subset Subset Function (mathematics) Matroid Set theory Vertex (graph theory) Mathematical optimization Pairwise comparison Category of being Physical system Length Proof theory
Stress (mechanics) Hamiltonian (quantum mechanics) Link (knot theory) Twin prime Graph (mathematics) Desire path Negative number Vertex (graph theory) Matching (graph theory) Directed graph Length Reduction of order
Energie Iteration Direction (geometry) Graph (mathematics) Supremum Vertex (graph theory) Bound state Infinity Mathematical optimization Distance Length
Network topology Network topology Wurzelbaum Uniqueness quantification Category of being Existence Directed graph
Kante Trail Vector space Moment (mathematics) Range (statistics) Length Arc (geometry) Distance Length
Kante Link (knot theory) Twin prime Logic Military operation Network topology Desire path Length Distance
Kante Moment (mathematics) Booby trap Mereology Quote Weight Length Distance Sequence Proof theory
Kante Military operation Wurzelbaum Negative number Directed graph Distance Sequence Proof theory
Operations research Stress (mechanics) Link (knot theory) Wurzelbaum Range (statistics) Equation Distance Sequence Military operation Booby trap Negative number Length Directed graph Proof theory
Greatest element Eigenvalues and eigenvectors State of matter Maximum (disambiguation) Moment (mathematics) Set (mathematics) Term (mathematics) Sequence Mathematics Coefficient of determination Radical (chemistry) Logic Function (mathematics) Ecke Set theory Iteration Length Perimeter Length Directed graph Proof theory
Axiom of choice Weight Laufzeit Ende <Graphentheorie> Square Set (mathematics) Total S.A. Rounding Inequality (mathematics) Distance Insertion loss Military operation Graph (mathematics) Iteration Negative number Factorization Proof theory
Operations research Algebraic structure Maxima and minima Binary file Element (mathematics) Mathematical structure Priority queue Network topology Object (grammar) Graph (mathematics) Queue (abstract data type) Negative number Category of being
Rule of inference
so genau sind die anderen immer so sein dass er verlängert Ferien an der TU Darmstadt so hallo ersetzt
heute wir haben jetzt mal in den sich schon über die gerichtete Variante Formen und vom Minimums bedingte gesprochen und wenn das heute jetzt erst einmal abschließen bevor zum nächsten Kapitel kommen aber schon ganze Menge dort dazu gesagt ich will nur mal ganz kurz für den Einstieg dann ein paar wesentliche Eckpunkte hier nochmal Cook skizzieren was war das noch mal ein Brand Schink 1 die gerichtete Variante das bedeutete sie haben gegeben einen gerichteten dürfen nicht Meinung gerichteten so eingerichteten Grafen wie beim Mini muss banyantree haben sie auf den gerichteten kannten jetzt Gewichte die auch nicht negativ sein sollten und was sie haben wollen ist wieder eine Teilmenge der gesamten Knoten Menge des aber CDs 2 Eigenschaften erfüllen soll 1. natürlich Züge frei allerdings die Gerichte Züge frei also wir wollen in dieser Teilmenge keinen gerichteten Züge drin haben wir wollen aber auch in dieser Teilmenge keine 2 Kanten haben die in denselben Knoten rein reingehen was ergibt sich daraus daraus ergibt sich dann dass sie sich vorstellen können was sie in der G 2 alte Bäume Ge gelernt haben mit der Wurzel und der geht es immer runter die 1. runter bis zu den Blättern dass wir mehrere davon haben wir einen so vielleicht und so dann geht es wieder weiter kann natürlich auch mehr als muss ich bin der sein kann noch beliebig viele Nachfolger haben aber es muss nicht nur ein solch Harbaum sein ob es habe wie das Wort Baum verwendet das natürlich hier nicht Fachterminologie ist Fachterminologie ist für ein solches Gebilde aus mehreren Zusammenhangs Komponenten Bran und das einzelne heißt das von mir gesehen aber es es da hinten drin steckt aber doch dann wieder aber keine Stammbaum und natürlich kann das kann es auch einzelne zusammen es Kommunen geben die nur aus 2 Knoten oder sogar nur einen Knoten bestehen das ist alles erlaubt im Extremfall Allan Graf nur mit Knoten ohne Kanten wäre auch ein Brand Inc so und was jetzt herausfinden einem gegebenen Grafen ein solches Branching eine solche Teilmenge die so strukturiert ist aber maximal das Gesamtgewicht hat wieder wie üblich Gesamtgewicht heißt Summe der die Gewichte der einzelnen kann ja schon beim letzten Mal gesehen einfach so drauflos zu machen so wie auf dieser Folie ja bringt schlechtes Ergebnis wenn wir als 1. die 3 nehmen weil sie schwerste kannte ist dann verbauen wir uns jeden Weg dahin zu einzig optimalen Lösung nämlich dass wir die 3 2 erkannten den und die 3 erkannte vergessen also müssen wir intelligenter hervorgehen oh und
ja das war der intelligente Mensch machen
wir mal einen Sprung hier werden kritische
Grafen sind das Wesentliche ist aber beim letzten Mal auch schon mit der auch schon gesehen was ist ein kritischer Graf nochmals das ist dass das genau klar ist für jeden einzelnen Knoten nehmen wir uns an einer Kante her die die schwerste könnte zum Beispiel hier die Karte mit Gewicht 6 ist die Fresse kannte die in den Knoten Nummer 3 hineingeht also ein sie hineingehen bekannte hier waren Beispiel die 2 das 3 dass 2 Kanten mit Gewicht 3 jeweils hineingehen davon wie uns dann einer von beiden beliebig ja sowieso schon in in gewisser Weise in den mehr von seinem Branching aber wir sind noch nicht einem Anschlägen ja wir haben im Normalfall konstruieren die damit keinen sondern sie sind wir hier 4 6 5 ist ein Zirkel oder hier 0 und 1 ist ein entzücke wollen wir manchen ja nicht haben was aber zu dass man ist die Eigenschaft dass in jeder einzelne kannte maximal ein Knoten hineingeht so und das ist ein kritischer Graf und
was wir uns zunächst mal klarmachen müssen ist das Lemma 10 also um es noch mal die Definition eines kritischen Grafen und eine kritische kannte was ist eine kritische könnte na ja das ist das
genau das was wir hier ausgewählt haben eine schwerste kannte den ein Knoten eingeht dass eine kritische kannte für diesen Knoten seine
steht da und der kritische wird Graf ist ein darf der eben die ihm gesagt nur solchen kritischen Karten besteht in dem für jede Knoten einer schwerste kannte und das habe ich es vergessen zu sagen Inklusions maximal nochmal zurück
Inklusions maximal heißt wir können keine weitere kann den zu nehmen ohne ohne uns hier irgendwas zu zerstören ja egal ich kann sie hinzunehmen ist eine kannte den 1 Knoten zeigt wo schon einmal kannte zeigt hinein zeigt bekömmlich sind zu nehmen das ist Inklusion maximal
so warum das Ganze was ist mit zu tun hat da nähern uns erst einmal an diesem Lemma sehen wobei ich habe hin und her überlegt ich bin mir nicht sicher ob diese Beweise so ohne weiteres wir hier steht wirklich korrekt ist oder eigentlich glaube ich nicht aber vielleicht habe ich auch was übersehen ich will Ihnen sagen was ich für für Probleme mit diesen Beweis hatte und und beziehungsweise was sich daran was ich mir überlegt habe das es dann trotzdem stimmt alles Norderstedt denn hier in diesen Beweis wir betrachten einen Brand legen einen schönen wir betrachten den kritischen Grafen der als ist und wir wollen beweisen dass das ein maximales Baldinis maximal also hat maximales Gewicht also erst einmal wieder zyklisches ist natürlich ein Branching denn was man die beiden Eigenschaften azyklisch und maximal eine Kante geht in jedem Knoten rein maximal eine kantige rein waschen der Definition von als von von dem kritischen Grafen drin und azyklisch wird jetzt hier im Lemma als Voraussetzung gefordert so also es ist ein Branching jetzt gucken wir es vergleiche dieses mit einem anderen waren B und wollen zeigen das Haar nicht weniger Gewicht hat als dieses irgendwelche beliebige Bahnschienen W und der Gedanke hier ist offenbar was hier in allen in dieser in dieser Gleichung steht was steht denn in dieser gleichen was was ist das während der die Kosten von irgendwas wie geschnitten was was ist das denn ein brahmanischen geschnitten mit einer Ende mit der Menge aller kannten die NV hineingehen Jahr wir haben ein Knoten V und wir betrachten alle kannten den vor hineingehen bis eine Braut Schilling das heißt also maximal 1 dieser könnten haben wir hier die aus dem Norden ist oder alternativ keine dieser kannten ist aus diesem Bahn schenkt dann da dann ist dieser Schnitt wäre dann die Kosten einer Menge sind der Definition neue wir betrachten also einerseits einerseits dieses und andererseits nochmal die also derselbe Knoten V somit denselben kannten und haben und kann andere kannte aus maximal eine Kante heraus und die Auswahl ist dass die eine Kante von dem beliebig gewählten manchen B höchstens so hohes Gewicht hat wie die markante vorn von unserem kritischen Grafen Haar das klingt erstmal absolut plausibel denn wir werden ja immer aber immer die Kante mit maximalen Gewicht so klingt also erst einmal auf so plausibel dass diese weiß das schon erledigt hat ich diese Kante ist per Definition die schwerste kannte die reingeht also kann sie nicht weniger schwer sein als die und wenn wir das über alle Knoten haben dann Gesamtgewicht des atypischen haben größer als das Gesamtgewicht dieses dieses Vergleichs a und 1 b ja das setzt natürlich voraus das ist diese Kante gibt das scheint den Beweis vorausgesetzte sein und das ist nicht unbedingt korrekt Mainz 8. also vielleicht habe ich irgendwas übersehen welches sie beweist doch korrekt aber ich habe es nicht gesehen also es ist mal klar wo wo wo die potenzielle Lücke in meiner meiner Interpretation dieses Beweises drin ist dann wenn ich Ihnen zeigen wo ich das Problem dann sehe nämlich in Zyklen im Grafen also das einzig nennenswerte an Aktion was diese Kamera aufnimmt ist das Teufel wünschen ein Aktion natürlich dich die Standbilder die dann immer da stehen bleiben sind sicherlich hoffe ich mal auch von einem gewissen wird so das Problem ist wir gucken uns mal den Zügel im Grafen an nur gucken ist der der Kamera drin ja ich kann in Frage kämen das ist der
Titel im Ausgang des Grafen dem uns angucken und jetzt kann es natürlich sein natürlich kann ich der ganze Züge drin sein wieder in dem Bereich wenn auch in dem Artikel mit dem noch in dem er also muss er muss auf jeden Fall kann auf jeden Fall nicht drin sein er also er kann wieder immerhin noch in dem in den kritisch Grafen hat den Hawaii als azyklisch gedacht das kann es aber so sein das in es muss ich mal sehen ich habe mir das vorher notiert wolle damit ich das jetzt nicht frei ich zeichne so der es kann er zum Beispiel so sein das der Graf aber so aussieht dass diese Karte hier fährt da noch und umgekehrt kann bei kann es bei dir so aussehen dass diese Karte drin ist aber beispielsweise diese Kante fällt ja dann stimmt die Argumentation von eben nicht mehr sie stimmt nicht mehr an der einen Stelle wo B 1 kann hat aber gar nicht ja an dieser Stelle kann man nicht an diesen Knoten kann man nicht mehr sagen das Gewicht der eingehenden kannten in H ist größer als das Gewicht eingehen kann den B denn es gibt keinerlei potenziell keine eingehende kannte wiesen beide so Grafen keine kritischen laufen mehr da wieso war also also B sowieso keine kritischer Graf sein da also mit der mit der haben Sie kein Problem genau wer mit ihren Problemen dass das nicht nur maximal ist genau da ach so dass das ist einer hat es könnte sein also dass jetzt doch wieder dahin kommen dass der Beweis ist wir korrekt ist haben also ich hier geht dann ist es gibt ja mindestens eine könnte die reingeht aber das ist meine nein das ist er okay die genau genau genau diese kann so ist Sie haben Recht diese Konstruktion widerspricht der Voraussetzung dass das was ich hier auf der linken Seite habe Haar ein zyklischer kritischer Graf ist es zwar zyklisch aber nicht mehr kritisch denn ich kann meine kann so ja das ist der Punkt er aus außer die Karte kommt von hier das kann ja auch eine sein aber dann gehen wir die Argumentation die Karte da da diese Graf kritisches kann die Karte nicht leichter sein als diese kannte ok also die Argumentation stimmt hätte ruhig natürlich auf der früher ein bisschen mehr wir haben mehr buttere bei die Fische geben können aber genau das ist der Punkt so wie ich es gezeichnet habe kann das keinen ist war zügig aber kann es keine kritische Graf sein denn dazu müsste man mindestens eine kann den zu nehmen oder wenn die Karte ist hier ist es egal dann und dann kommt so selber raus wenn wir alle könnte ist dann muss das Leck der Definition mit kritische könne sein muss man es so schwer sein wieder okay da stimmt die Argumentation wie es auf der Folie ist vielen Dank gut dann kann man das so weit geklärt aber ich schätze mal mit dieser kleinen 5 Minuten Aufnahme von diesem Thema haben haben haben wir ihnen später bei der Vorbereitung auf die Prüfung einiges an Kopfschmerzen erspart weil wir ja jetzt nochmal genauer gesagt haben warum dass dieses Argument tatsächlich stimmt ist das war klar geworden also mir ist jetzt klar geworden okay ja nun ich meine sie wissen es da das Professor noch nicht allwissend sind wissen so oder aus eigener Erfahrung nämlich an so also dieses Lemma sagt schon mal das kritische Graf eine ganze Menge mit maximalen Branchen zu tun hat einfach nur durch diese Kopplung wenn wenn der kritische Graf schon Artikel ist dann ist das schon ja was also ist die Frage wie weit weg kommen wir was müssen wir noch tun wenn dieser wenn wir einen kritischen Hafen konstruiert haben der sehr leicht zu konstruieren effizient zu konstruieren was müssen wir noch tun wenn der nicht azyklisch ist das ist
ja die Frage so und dann wir mal so ein paar
Sachen überspringen um mal wieder irgendwo müsste jetzt den nächsten Bild Bildchen
wiederkommen ne erstmal kommt dieses Theorien also bitte kommt erst später erst kommt Theorien so habe ich auch nicht was ich meine Fahrplan geschrieben habe übersprungen nee habe ich nicht übersprungen und sucht ich habe jetzt einiges an an allen mathematische Bürokratie übersprungen ich will versuchen indes das wieder ich das schon mal stehen gemacht habe mehr hoffentlich etwas Illustrativer näher zu bringen so ja wenn gesagt wenn der kritische Graf dem wäre uns betrachtet haben wenn er schon fertig dann haben ein maximales Bratsche jetzt komm ein Schritt näher und jetzt haben wir irgendein kritischen Grafen der in der Regel nicht azyklisch ist der also solche kritischen 7 enthält dann wird gesagt dass sie mir immer noch nicht allzu weit weg das dann gibt es ein Branching was sehr eng an diesen kritischen Grafen gekoppelt ist durch das diese Bedingung die hier in der zweiten solle das Theorem steht und was sagt diese Bedingung ist der steht letztlich aber zu Umwelt da was sagt diese Bedingung diese
bedingt sagt ich kann aus ihren Zügen im einem kritischen Grafen eine bestimmte kann rausnehmen ob kann die Züge freimachen durchweg noch vom kannten und wenn ich das richtig gemacht habe dann ist das was übrig bleibt tatsächlich ein maximales Bahn ja es erst mal was was schön ja ich nehme ja ich gucke mir an wo sind hier wo es Graf ich Züge frei ich mir meine kann daraus und das ist dann maximal Problem ist natürlich welche kann aus dem offensichtlich kann die kann ich das nicht beliebig machen und in diesem einfachen Beispiel hier würde es würde schon hinreichend ich jeweils die die leichteste kannte rausnehme das ist dann auf bei weil diese beiden Züge überhaupt diesen einer zu tun haben aber stelle sich vor der lag komplex ineinander verschlungenen Züge Struktur bis 10 im Extremfall das sämtlicher kannten sämtliche Möglichkeiten möglichen Kanten drin sie den Grafen also alles mögliche zügelt ist es mir nicht mehr klar welche kann man daraus nehmen soll und das macht jetzt noch uns diese Arbeit aber als Vorbereitung brauchen wir dieses Theorien zu hier er
sieht es Entschuldigung Theorien 17 wenn ich in kritischen Grafen habe habe gibt es einen Brand Schenk kann ich in Brandschäden B daraus konstruieren aus Haar so dass sich diesen diesen er dass ich Ihnen für jeden Züge in in meine kurz jeden kritische Grafen einfach eine kann doch ausnehmen ziel dieser Züge dieser kritische Zirkeln kritischen Grafen alles mitgenommen was zum Branchen gehört ist 1 1 kann daraus nehmen dann habe ich meine Bartlick so warum ist das so das vielleicht ihnen diese 3 verschiedenen Fälle die wir zu betrachten haben will ich versuchen zu illustrieren so wie hier betrachten wir zunächst einmal hier in dieser Formulierung gehen wir von einem maximalen Boombranchen aus das bestimmen das sehr nah an uns kritischen Grafen ist nämlich so von allen möglichen maximalen Branching S nehmen wir B als einen der so viele kann wie möglich gemeinsam hat mit dem kritischen trafen wir kontrollieren wollen als Trick um irgendwo später ein Widerspruch Herr zu kriegen also wir gehen erst mal von einem Brand in der aus und wir haben schon gesehen die so manchen aus das Zeichen X in der Informatiker immer so nach unten die Wurzeln es ganz oben hier ist der nächste vielleicht ich zahle immer noch einen größeren so'n bisschen schematisch so dass es mir nur so Zusammenhangs Komponente es geht natürlich auch alles runter also und jetzt betrachten unsere kannte die nicht zu diesem Branching gehört und genau gesagt wir betrachten uns mehrere kannten er deshalb habe ich den Grafen was schematischer größer gezeichnet um das um es möglichst allgemein zu halten es gibt es verschiedene Arten wie kann hier verlaufen können eine Möglichkeit ist zum Beispiel so ja von einer kann zu erfahren von endloser Nachfolger irgendwo ist eine andere Möglichkeit wäre genau umgekehrt von einem Knoten zu einem Vorgänger Knoten mehr genau umgekehrt eine andere Möglichkeit die Roten sind kann die ich zum Brunch gehören eine andere Möglichkeit wäre beispielsweise hier so eine Brücke zu schlagen von einem Klon zu anderen Knoten die nicht die nicht im beziehen zueinander stehen oder auch nicht zu vergessen eine Möglichkeit wäre beispielsweise eine Kante hierhin zu zeichnen ist das ganze Bild bis oben drauf ja ich hoffe dass Ruth sieht man dann gut das auf so eine Kanzel hier fällt raus von diesen 4 ich eine Zeichen habe er das also die 4 Möglichkeiten die hieraus für es vor in der die die uns die uns die uns stört nämlich wenn ich zum Beispiel diese kannte er betrachte wenn ich die einfüge Flügel und dafür diese Kante Lorscher die aber da diese diese Karte hier die Reingewinn 7 Knoten er setzte durch diese Kanther dann ist das Ergebnis anfängt aber es ist bei den Zügel frei und es geht weiterhin nur eine kann den irgendwo genau dasselbe hier wenn ich die Kante ein für Grund dafür die andere in diesem eingehende 1. ist das Ergebnis Mann schenke weil ich hier diese Schicht an dann hängt diese ganze der ganze Teilbranchen an dieser Karte nicht nur immer an diese Karte so dass wir hier hier sogar noch einfacher hier habe ich einen eine aber es sind eine andere angehängt es weiterhin ein Brand aber wenn ich das selber hier mache mit dieser Kanther dann funktioniert das nicht mehr denn wenn ich jetzt diese kann einfüge Flügel und dafür diese Kante rascher dann habe ich in Züge geschlossen ja kannten die von einem Knoten zu einem Vorgänger Knoten gehen sind speziell in diesem Sinne ich kann sie nicht einfügen dafür die andere die aber kannte die hier reingehen löschen weil es dann keine Branchen ist ja so und dass das was Sie im Skript finden diese kann hier hat die Eigenschaft wie will also eigentlich heißt wie Sibylle im
englischen durchführbar aber in unserem Kontext hier übersetzt man das meistens mit zulässig erlaubt diese kann ist wie Sobel diese kann die ist wie Sibylle und die ist nicht diese dass der Begriff den Sie in den Folien finden und doch in der Literatur dazu so ja dieses Bild müssen wir uns klar machen es gibt fiese bekannten es gibt nicht diese bekannten jetzt gehen wir wieder zurück zum Beweis keine Sorge wir werden gleich wieder zu dieser Welt kommen wir noch Frage die ja ja gemacht gemacht ja Sie haben recht das müsste maximal sind sie mit den 1. dash vorweggenommen ja der Unterschied ist einfach der wenn wir jetzt die Fallunterscheidung auf der Folie machen dann ist das ein eigener Fall deshalb habe ich diese kann mit eingezeichnet am sie am voll und ganz recht so und wir haben uns jetzt dieses maximale bahnen die an gesehen das so viel wie möglich gemeinsam hat an Kanten mit den kritischen Grafen den wir den wir in der Hand haben den habe konstruiert und wollen das daraus dass zu maximal manchen B konstruieren so jetzt gucken wir uns eine kannte in diesen kritischen Grafen an als eine kritische könnte die nicht in manchen drin ist und dann sind wir genau ja diese wir gucken und eine Kante an die Aust zu Hause dem kritischen Grafen sind mit dem wir los gehen aber nicht in diesem Ranking drin es und dann muss sie eine dieser Möglichkeiten sein so der also dash es gibt keine andere könnte in Braun stehen die denselben Knoten ist genau das es genau das ja diese kannte es gibt keine weil das Wurzel ist es gibt keinen andern kann und der eingehen er keiner keine ihrer Ed das haben Sie zu Recht bemerkt es kann nicht sein er dann wir waren ja davon ausgegegangen dass B Eigengewichts maximales Bratlinge SD-Card nämlich dass sind alle positiv das heißt also wenn wir diese Karte einfach in einfügen habe eine Beßres Panchen bekommen Widerspruch zueinander das Bier schon Maxime ist so also diese Kante kann gar nicht sein hier so betrachten mit anderen Fälle jetzt haben wir eine Kante schon die Reihen gilt und jetzt unterscheiden wir das ob diese kannte diese belässt ja es also wir betrachten die beide noch übriggebliebenen Fälle wo die Kante über ist das ist eine Karte das ist eine kritische kannte ist ja in kritischen Grafen und das heißt also diese kannte wenn wenn die aus aus dem kritischen Grafen drin ist dann ist sie mindestens so schwer wie diese könnte aber da wir waren ja davon ausgegangen das das Branching B die weißen Kanten möglichst viel gemeinsam haben mit dem kritischen trafen das heißt dieses Bild kann man gar nicht sein denn wir könnten diese kann daraus welchen diese Kante einfügen sind nicht schlechter geworden und haben eine Kante mehr gemeinsam mit dem britischen Grafen dass die Stelle wo ich sagte der Track wenn wir einen einen her dass möglichst viele kann gemeinsam hat mit dem von uns konstruierten kritischen trafen dann kommt um ohne Stelle wo Widerspruch haben genau hier dieses Bild kann ich sein es kann keine fiese bekannte weder so noch so aus dem selben Grund geben die außerhalb dieses Band links liegen da keine fiese Bildkante die zum zum König Grafen hat denn wer war davon ausgegangen dass möglichst viel gemeinsam hat und wir können jetzt einfach diese Gemeinsamkeit erhöhen indem wir diese fiese bekannten einnehmen und die entsprechende aberkannter rausnehmen so das was also übrig bleibt ist dieser Fall hier und da sehen Sie schon worauf das Ganze hinausläuft hier wird tatsächlich ein Züge geschlossen bei dem diese kannte der einzige kannte ist die nicht zum maximalen Annchen gehört ja dieses diese Karte ist die einzige die sein kann und die hat tatsächlich er hat dies tatsächlich auch im Zügel der alles gemeinsam hat mit außer dieser kannte mit diesem schenke und damit ist das Theorem 17 bewiesen alles was da vorkommt und diese ganzen mathematischen diese ganze mathematische Bürokratie ist im Prinzip dafür da um dieses Bild vorzubereiten und zu erklären habe ich jetzt hier mir erspart habe ich ihnen erspart wenn Sie es mir nicht mehr Prüfung ersparen wollen bin ich begeistert wie gesagt dann sind Sie schon offen und gut das gute Stück weit auf dem Weg zu 1 comma decimal 0 so das machen wir wieder einen
Sprung hier werden wie kriegen wir
jetzt die richtigen Zügel hin das habe ich beim letzten Mal schon kurz angesprochen gehen wir mal noch ein
bisschen weiter hier die Idee
einer Sache ist was uns stört rausschmeißen also nicht ganz Rauschen weiß ich ersatzlos rausschmeißen sondern ersetzten durch einen einzelnen Claude in dem Fall Shrinking also die Züge zu schrumpfen ja wir wissen nicht welcher wir wissen nicht momentan welche kannte von welche kannte wie auf die von diesen Züge des kritischen trafen rausschmeißen müssen also hier von diesem Ziel es kritisch trafen das wissen wir im Allgemeinen nicht in diesem einfachen Beispiel wissen das natürlich weil die beiden Züge so schön disjunkt sind das sehen sich betrachten können aber wenn den Riesenhaufen von Zügen ineinander verknotet haben wissen wir das nicht mehr so jetzt schrumpfen wir die beiden alle die wir finden zu einzelnen Knoten und lässt das Problem hier hier ist es ganz einfach zu lösen ja ja in dem Beispiel sowieso wir dem muss diese kannte und wir nehmen uns diese Kanther denn die muss beide kannten die da sind zyklisch kritische kannten azyklisch bedeutet maximales Branching es kommt wieder die Frage sondern 2 statt nur 3 steht die warten schon beim letzten Mal das ist der fiese Trick an der ganzen Sache oder was ist wie der geniale Trick an der ganzen Sache und zwar folgendes wir haben jetzt hier rechts eine Lösung im Allgemeinen wissen wir aber nicht wer es also wir wohl den ursprünglichen Graf eine Lösung haben so wir schrumpfen den Züge so mal wieder meine 6. Züge denn und hier gehen noch einen diverse K Knoten rein er also die reingehen nun interessieren uns hier mehr so die diesen Züge vor zu den einzelnen Knoten wo diese kannten alle reingehen so kann jetzt doppelte kannten geben 2 kannten die vom selben Quoten hier einen zeigen das stört uns ja nicht wir einfach nur die schwerste aber hier kommt natürlich noch mehr sein so und jetzt gibt es hier 2 Möglichkeiten eine Möglichkeit ist das wenn wir wir hier ein optimales Brand in den wenn schaffen in diesem geschaffen haben ein optimales Branching zu konstruieren so wie wir das in diesem Beispiel ja sofort auf offensichtlich tun können der Graf es azyklisch optimales Branchen es trivial wenn wir es hier schaffen in diesem geschrumpften Grafen wo natürlich nicht nur die seine Züge des sondern alles mögliche andere noch drin ist da ein optimales Branching drin zu zu basteln dann wollen wir den Weg zurück gehen wollen wir von hier das erweitern auf diese auf diese auf diesen Zielke nur müssen wir jetzt genau aufpassen was wir dann tun es gibt 2 Möglichkeiten eine Möglichkeit ist keine einzige dieser reingehen kannten gehört zu den maximalen Branching das wir konstruiert am keine einzige das kann passieren das Wurzel dann von Warren Schenk was ist dann auch das beste wenn wir das wenn wir jetzt den den den den die Züge wieder n schrumpfen das ist das Beste was rauskommen kann nervigen wir gucken uns die einzelnen Kanten an und wenn das hier zum Beispiel die leichteste ist von allen dann nehmen wir die raus die sind alle drin was besseres kann offensichtlich nicht machen ist es so weit klar wenn wenn keine einzige der eingehenden kann in diesen optimal Mädchen ist von dem wir glauben dass es konstruieren können und wir übertragen das dann auf die ursprünglichen Ziele könne dann die muss die leichteste kann der und wir wissen vieles Patchen können wir gar nicht kriegen ja draußen außerhalb von diesem Zügel bleibt alles gleich sie müssen sich also vorstellen dass hier noch ne Million anderer Knoten darum herum sind durchaus mit Kanten verbunden mit diesem Zirkel der Graf einer gefallen vollständig zusammenhängend sein aber eben keine einzige der eingehenden kannten in diesen Züge beziehungsweise in diesen geschumpfen Knoten gehört zu diesem maximalen Branching dass wir jetzt hier für diesen geschrumpften Grafen konstruiert haben zweite Möglichkeit ist es gibt jetzt 1 solche kannte natürlich höchstens 1 bei einem Brand in geht er in jedem Knoten höchstens 1 rein ich bitte um Entschuldigung dass ich das es gleich
wegwischen aber irgendwie kriegt das sonst nicht alles auf ein Bild und es mal gut dass sich das irgendwie um diese was verlorengegangen zu der hier so ja es gibt die andere Situation der geschrumpfte Knoten hier haben jetzt irgendwie auf magische Art und Weise unser maximales Panchen konstruiert aber der hat eine könnte die zu diesen waren gehört jetzt ist die Erweiterung darauf ein anderer nämlich am es wieder unseren Züge wird zurück und diese kannte es ist das da drüben die zu den maximalen manchen gehört jetzt was ist was bedeutet jetzt die Erweiterung auf die auf den gesamten Süden es bedeutet dass wir diese kannten 3 nehmen und die hier nicht ja so jetzt nehmen wir mal die Kanten Gewichte ja die wir da in diesem Beispiel haben auf den Folien kann man denn noch sehen ja gut ich hoffe man kann es noch halbwegs sehen diese kann kann ich dir das ist alles ein bisschen in Necker werden wenden muss neue kann Gewicht der bedenken Sie was aus so das hier hätte zum Beispiel kann nämlich 3 diese leichteste kannte hätte könnten Gewicht wenn wir das 1 und diese hier hätte kann Gewicht beispielsweise ja ich hoffe dass das jetzt mehr gut illustrative weil es ja nicht könnte doch sein also wenn sie jetzt ja aber dieselben Gewicht hier und 1 wenn Sie das jetzt miteinander vergleichen was ist denn jetzt der Unterschied zwischen diesen beiden Bildern hier haben wir eine 3 plus 1 1 ist natürlich gerade kein gutes Beispiel gewesen so hier haben wir eine 3 plus 1 1 und hier haben wir hat anstelle dieser keine trat mehr Gewicht an dieser keine mehr Gewicht als habe einer sein kann damit Gewicht 7 so das heißt also wenn wir die 3 hernehmen dann kostet und wenn wenn das Mertsching drin ist wenn diese Karte Menschen drin ist dann gibt uns das einen Berner führt von 3 aber kosten von 6 gegenüber der Situation dass diese kann denn ich Imaging drin ist und genau das das ist der Unterschied dieser Bänder fährt muss mit diesen Kosten verrechnet werden und das ist hier auch gemacht worden um diese 2 dass diese Karte nicht mehr 3 hat sondern sogar den wir 2 hat nämlich wenn diese kannte nicht drin ist in maximal Mädchen hier sie ist drin das wissen wir das sehen wir sofort aber dem normalen würden es nicht sofort sehen falls diese Kante von 2 nach 1 nicht drin ist dann ist im Zügel das Beste was man machen kann die 4 raus zu streichen und die also die Karte mit Gewicht herauszustreichen die von Quoten 4 nach Kloten 3 geht wenn wir gegen diese Karte hinzunehmen ist das Beste was wir tun können die kann davon erst nach 4 und die kann davon vor 1 4 1 3 hinzuzunehmen und die 5 nicht das kostet uns gegenüber der dieser Variante hat wie er eine in die Karte mit Gewicht 4 haben wir drinnen die keine Gewicht 5 haben nicht mehr drin das heißt diese Kante von 2 Grenzen zu sehen kostet dort bringt uns 3 Zähler kostet uns einen Zähler und das ist genau hier hinein modelliert dass jedes Gericht 2 vom Knoten des 2. Quoten wie Heinz ist das ist der ganze Trick dafür zu sorgen dass diese Karte eingelegt hat was die was reflektiert je nachdem ob diese Karte drin ist oder nicht wenn sie nicht drin ist dann hat halt keine die dann der Zeit der ganz ganz viel Zeit gar nichts wenn es drin ist die der Unterschied zwischen kannte drin oder kann nicht drin ist gerade diese 2 Einheiten 3 Einheiten weil ist eine Einheit davon abgezogen weil wir im stehen weil wir das Branching im Züge so anders gestalten müssen dass wir da noch mal einzelner verlieren das alles nicht ganz denn jetzt bin
ich also hier sehen Sie das noch mal als Formel habe ich keine Lust so jetzt comma nochmal zum
Algorithmus ist gehen wir aber wir
haben schon ein bisschen wenn man glaube ich betrachtet hier 10 Bild ich
wieder Fluss bildet sich weiter groß eingehen das können sie sich nochmal zu Hause anschauen im stillen Kämmerlein und noch mal ihr Verständnis zu überprüfen aber was dieses Bild insbesondere auch sagt das ist das Beispiel bisher nicht gesagt hat ist wir können jetzt hergehen und und Züge schrumpfen so viel wir wollen im Ausgang Sklaven so dann sind wir hier aber wir haben immer noch Züge wenn es neue Züge also es reicht nicht einmal Züge zu schrumpfen und dann und dann habe man Züge freien Grafen soll es kann sein dass wir neue Züge haben und dann das Ganze wieder machen also rekursiv wieder selber mit dem neuen Grafen da noch gar nix ja wir haben erst mal hier von 1 noch 2 Sinnbezüge geschrumpft es sind immer noch zu viel da also schon wir wieder Züge so lange bis so lange bis das Ganze so einfach ist das wir das ist direkt lösen können also eigentlich müsste man sieht nochmal nochmal Schritt machen weil die Züge drin sind noch mal das ganze schrumpfen aber Sie sehen ja hier was ist optimal Branching ist nämlich die Karte mit Gewicht 3 von den 4 noch wie 3 aber und das Ganze jetzt in diesem Bild zurückzuübertragen hier ist nur 1 diese kann genommen jetzt expandieren wir die die Zügel die wir im zweiten schon Schritt gemacht haben klingt das Bild welches sich weiter erklären das kann sich wie gesagt selber zu Hause noch mal genau ansehen warum das warum das so sein muss und wenn wir noch mal alles diesen Schritt diesen 1. Schrumpfung Schritt rückgängig gemacht haben mit diesem Operation Übertragung des Brunch ins Ausdehnung des längst auf die wieder aufgeblasen Zügel dann kriegt man das raus ein maximales waren schien das heißt ja meine rekursiven Algorithmus ja schrumpfe Zügel ruf rekursiv auf also Nein falls keine Züge mehr vorhanden ist das Problem das der Größe uns Anke falls doch Züge vor er vorhanden schrumpfe Zügel rufe rekursiv auf und expandiert die Zügel wieder und Arbeit das Making-of dies expandierten Züge comma er dass das bricht ab weil in jedem Schritt die Anzahl der Knoten kleiner hat endlich viele Knoten also nach endlich vielen Schritten durch das ab Abwärme Frage okay die Frage war jetzt eine Folie früher eigentlich müsste man jetzt unter Punkt 3 das nochmal 5 über der Züge drin haben oder aber nur einen Punkt sie war an genau das der Punkt kritische na gut aber kritische zieht aber trotzdem wir wir hier kritische könnte noch drin also er hat schon recht das müsste man mal schrumpfen So What was ist das maximale Branching auf einen also ein Knoten dieser Knoten mit einer leeren Menge ihr es wir wir sehen das sofort hier in diesen in diesem Bild unter Punkt 3 sehen wir sofort was die Lösung ist das aber der Stelle so nicht mehr weitergeführt da gutes natürlich darum der Algorithmus muss muss weiter agieren muss diesen kritischen Züge denn der hier drin steckt in den nicht mehr eingetreten ist muss diesen kritischen Züge wieder schrumpfen und kommen zu einem kann Grafen dennoch noch einen Knoten enthält und dieser und dieser eine da ist da ist das trivial und jetzt diese allgemeine Routine der Übertragung funktioniert hier natürlich in dem Fall genauso wie im komplexen Fall also das ist dann schon was wichtig gut also der Algorithmus kann ich bei bei period Reihe stehen bleiben da muss zu Punkt zu dem Bild viel kommen wohl noch ein Knoten drin ist für gut das ist der 1. Moment wo dieses Beispiel azyklisch und natürlich wer im wenn das Beispiel anders gelagert wird es muss nicht immer auf einer einzelnen Knoten reduziert werde es kann auch durchaus was auf einen etwas komplizierteren zyklischen Grafen hinauslaufen so und damit
sind wir so mehr oder weniger fertig parallel kanadischen schon gesagt interessiert uns nicht der 0 könnten oder negative könnten wir sofort an das ist der Punkt noch wo
hielt hat sich das ist ein großer Werbung dabei eben was ich Ihnen eben vorgelesen haben war wurden weiter ist negative kann oder kann ich nur kann natürlich eliminiert werden die wenn man den maximal 1 1 und damit mit diesem mit diesem Schritt Elimination der negativen Karten haben wir sofort hier im Bild 3 1 zyklischen trafen wenn man das machen wenn man sich machen wenn mir nicht negative kann eliminieren und wenn der Algorithmus so dumm implementiert ist dass er es nicht tut dann würde man hier noch einen vierten Schritt Paar also doch noch einen dritten Schrumpfung Schritt brauchen 4. Zustand zu
kommen so ja die können sprechen uns natürlich und dieser Anwendung das haben vorher schon ausgelassen dass wir jetzt auch aus so Literatur wenn Sie wollen haben sie genug zu lesen und damit sind wir mit diesem Kapitel durch und kommen zum
nächsten Kapitel da schon
wieder was was wir kennen uns der kürzeste Wege
aber keine Sorge da gehen schnell durch
er was das gesellige Problemes kennen Sie ich würde jetzt viele kannten hier mehr der weniger schnell durchgehen weil es kann so sind die 2 kennen Sie haben hingerichteten Grafen sie haben kann Gewichte sie haben Knoten S und nun des und sie wollen kürzesten Weg von erst noch die Christa Weg heißt die Summe der kann Gerichte ist minimal natürlich müsse davon ausgehen dass der Graf so weit zusammenhängendes dass es mindestens einen Weg gibt von ist nach die sonst gar nicht von den kürzesten Weg werden daran
gut diese Folie wieder was passiert wenn man alle möglichen Vater in der Maria zu sehen Sie doch 100 Knoten schon dass das ein bisschen ärgerlich wird da nur wenig weiter besprechen
Madrid in das wir hier aus ich habe darüber lange mit Herrn Still gesprochen ist zwar
richtig dass das ganze hier mal Madrid ist aber ich glaube dass er von zu als das ist hier Erkenntnisgewinn bringt so ein
period da wollen wir mal alles voll so kannten Längeneinheit könnten haben alle Gewicht 1 Jahr Spezialfall alle kann haben länger als das heißt der kürzeste vor dass derjenige mit der geringsten zu Anzahl kannten so wenn wir nicht so genau hinschauen wenn sie so und die Augen zusammenkneifen dann wird Ihnen dieses Bild wahrscheinlich bekannt vorkommen nämlich das wird sehr ist dass er genau Augen zukneifen er der er und wird langsam müde nicht damit in dieses Bild bekannt vorkommen sind nämlich sehr sehr ähnlich zu der Xtra und das ist auch überhaupt keine kein Zufall wenn was diese Folie aussagt ist das endlich bei Kantenlängen Gewicht einst könnten in 1 brauchen wir gar keine Partie Kyu was uns ausreicht ist eine eine normale Fifo Khieu eine für hinten rein von daraus warum sie ändern sich das hatten wir am Anfang dieses Zimmers das mal festgestellt wenn Sie bereiten Suche machen also schon also in ihrer Suche eine Fifo Khieu verwenden man das ist genau der und der Unterschied tiefen Suche breiten Sumpfe da extra sie flog die U 4 Tadic Klärung das ist exakt der Unterschied alles andere ist bis auf die exakten Berechnungsformeln identisch so wir haben schon mal gesehen wenn der breiten Suche machen und wir gucken uns die Khieu an die Sie auch mit Q benannt nicht ja zur hier ist vorne hinten und vorne vorne holen herausfinden vielen ein damit diese damit es keine Missverständnisse gibt habe ich das noch mal hingeschrieben so und dann gibt es zu jedem Zeitpunkt wir haben alle Elemente ich hier mir Distanz von ist und von oben period aus haben sie alle Distanz K plus 1 das Bild hat mir schon mal als wir beide Suche besprochen haben zuerst habe es gibt einen K so dass erst die 1. Elemente aller K entfernt sind vom Staat Noten und alle weiteren in man in K plus 1 sind wir natürlich keine diese Teilmenge mit Kabel was die zur Menge mit Kabel 1 auch mal er seien momentan aber so wieder der nächste Knoten kommt haben wir wieder die Sitzverteilung das bedeutet also das fungiert in dem Fall Eisparty Kilo weil wir wissen es kann es kann ja nur 2 verschiedene Distanzen geben K und K plus 1 und die mit Karl comma ist das ist die Aussage dieser Folie die 2. zweite Aussage ist das Ganze doch noch im Namen nämlich Algorithmus von nur so negative
Zyklen er ist mit Sicherheit einige die 2 betrachtet worden können wir jetzt ganz schnell durch durchgehen ja was passiert wenn wenn sie negativen Zyklus haben und hoffentlich von es machte sie gehen rein einmal haben länger gespart GesO nochmal durch haben wieder länger gespart geht nochmal durch dann nochmal durch und nochmal durch nochmal durch es gibt keinen kürzesten Weg weil sie können beliebig oft durchgehen und damit den Weg immer kürzer machen jetzt könnte man sagen OK ist natürlich nicht das was wir wollen wir wollen falls es negative Zyklen dem Grafen gibt wollen wir ein einen fahre konstruieren der eben die Zügel frei ist von erst nach T das Problem an der Sache ist diese Problemstellung ist endlich in Anwesenheit von negativen Zyklen einen Christen die Züge freien Weg zu finden das noch der ist ein Beschwerde hat ich schon mal gesagt was das bedeutet für pragmatisch bedeute das für jeden Algorithmus der Mann den man sich ob ausdenken könnte gibt es kann man Beispiele konstruieren von moderater Größe bei den dieser Algorithmus wesentlich länger braucht als und unseren diversen im zur Verfügung stellt so haben der letzte Punkt hier Herr Mehdorn schon fade einher mit einer Fahrt von ist nach dem Grafen ist einer der alle Knoten genau einmal durchläuft und wenn Sie jetzt alle Kantenlängen zumindest einsetzen Grafen dann sind die S die Pfade der länger 1 minus 1 genau die die alle Knoten die die genauen sprechen viele eines kannten enthalten also Knoten enthalten alle Knoten enthalten ist noch die außer gehämmert und schafft Fahrrads zu brechen ist eine beschwere im Allgemeinen also es herauszufinden ob es überhaupt einen solchen Grafen geht einen solchen Fahrt gibt in einem Grafen ist endlich wer und wenn man mit mit diesem kürzesten Wegen tatsächlich mit dem Küste Wege Problem tatsächlich das immer dann schon vor Probleme lösen kann dann kann dieses gesellige Problem nicht leichter sein so nur der extra das wissen Sie keine negativen kannten für die andern Algorithmen gilt das nicht
ungerichtete Grafen hat ich wenn man glaube ich auch schon mal erwähnt ungerichtete Grafen können Sie prinzipiell natürlich ersetzen durch gerichtete K und ungerichtete kann durch gerichtete kannten eine ohne gerichtete kannte mit Gewicht c können Sie natürlich durch sowas ersetzen beide haben wir nicht sehe außer das Gesicht sehe es negativ dann haben sie mich plötzlich im negativen zügelt oder dann geht das Ganze natürlich nicht aber wenn das Gewicht nicht negativen alle gewichen ich ihr dieses geht die Konstruktion natürlich gerade das ist das was hier steht funktioniert nicht bei negativen Kantenlängen ja gut dass es den Vorausschau dieser Sichtweise betrachten wollen parallele kannten ist in kürzesten wegen Problemen sowieso keine Sache wenn sie Zweig parallele kannten haben die unterschiedliches Gewicht haben C 1 und C 2 der schmeißen sie kann daraus höheres Gewicht hat die bringt ihn ja gar nichts so sie
sich bei Ihnen uns bei den Trials ganz Westen abstrakte gesehen das werden wir jetzt hier auch sehen Unterscheidungen Algorithmen die zu korrekt den heißen da kommen an sich eine Distance Lebensenergie die 2 die man so setzt und er wenn Sie vielleicht so ein bisschen noch Änderung haben an die Algorithmen die der Energie die zur betrachtet worden sind extra bei man fort war war schon vielleicht dann waren diese Distanz Labels befähigen Knoten immer obere Schranken als es war 1 werde die niemals kleiner waren als die echten Distanz Werte weil sie ja schrittweise immer runter gesetzt von sind haben sich in immer nur in die Richtung abwärts verändert und deshalb ist es notwendig dass Sie immer dass sie immer dass sie niemals kleiner sein dürfen diese werden das kleiner sein dürfen als echten das Tanzen so denn dass es zum Beispiel der Xtra wird in jedem Schritt eine wir permanent gesetzt und dann wird sie wieder geändert werden korrekt denn das wäre beispielsweise der man fort und fort war still wer sich nochmal in an wenn man fordere von Asche kein einziges Label keine einzige Distanz die sie da mal zwischendurch berechnen ist für Dauer sollen erst im allerletzten Schritt im allerletzten Durchlauf durch die übergeordnete Schleife werden sämtliche Distanz Werte endgültig gesetzt vorher sind alle temporär dass man den korrekt denke wir bisher Think funktioniert nur mit nicht negativen Kantenlängen da sehen wir gleich noch mal ein
Beispiel dazu so was in
der die 2 noch nicht so genau betrachtet wurde es zumindest nicht bei mir ich weiß nicht wie es bei Herrn Kallenbach oder Herrn Buchmann war wenn Sie sich die ganzen kürzesten Wege anschauen die da von einem Staat nun aus allen anderen wollen sind wie bei der Xtra oder im bei Europäers E bei Europäers eben wenn sich alle anschauen die von einem Knoten zu allen anderen gehen ja das ist wie üblich mein Graf hier ist und wo der Staat Noten zweckmäßigerweise Mitte zeichne und da extra berechnet kühl und zum Beispiel 30. die andern auch berechnet kürzeste Wege aber was er da tut ist diese weniger wegen 1 genau gesagt aber weil sie ihre eingerichteter Baum ist warum tut er das also zunächst mal muss man sich ja klar machen was während sich was merkt man sich bei so einem Algorithmus eigentlich um die der zu rekonstruieren man merkt sich für jeden Knoten die reingehen der letzte kannte dieses kürzesten Weg ist nicht und damit haben wir schon aber was Cents die eine einzige wofür hat nämlich S ja also es gehe ergibt sich automatisch eine solche aber sind solche was er muss gar nicht gespeichert haben man kann natürlich immer so eine aber es sind aufbauen weil wenn sie sich vorstellen der kürzeste Weg zu diesem Knoten hier geht solange und der kürzeste Weg zu diesem Knoten hier geht solange denken können Sie natürlich das sie rausschmeißen und stattdessen gehen denn diese beiden Wege sind offensichtlich gleich von hier nach hier und von hier nach hier
so was hier steht ist etwas was denken sehr sehr schnell einleuchtet hat wenn Sie den kürzesten Fahrt haben von irgendwo zu einem anderen Orten und sie betrachten sich zum Teil Vater zwischen so so in der Weise zu sagen 10 2 Knoten der bei durch auch so lang dann ist das Denken das es von 1. machte das ist von Frauen auch W dann ist dieses Stück natürlich ein kürzeste vor wir fort denn ja das einen kürzeren wollen das lang dann wäre natürlich das hier auch ein kürzerer S Pfad Widerspruch jeder Teil eines Christen ist es Heynckes ist der Weg genau steht hier und das kann natürlich auch noch beweisen
warum ja jetzt kommend 1 die folgende Einsicht dazu auch die sich daraus ergibt dass hat ist ein Corolla weil das bitte nochmal vielleicht ein bisschen neulich sie so wir mal jetzt noch mal das in Kürze ist der Pfad wo nach und wir haben hier eine Kante drauf von nach V und interessieren uns für die Delta Wärter und was dieses Corolla sagt ist dass die Täter werde die Distanz werde sehr sehr strikt es sondern eine Beziehung stehen nämlich dass die Distanz nach Frau exakt gleich ist der Distanz von es nach plus dem Kantenlänge von nach Frau logisch weil die Distanz von vor von es nach Frau natürlich nicht größer sein und weil das ist ja das ist ihren Weg den kann der kürzeste Weg nicht länger klar die Distanz von es nach vor kann aber auch nicht kürzer sein da der im im Moment halt ihre muss sich jetzt beweisen wenn das Küssens verwickelt ist dann ist das auch ein kürzeste Weg von es nach V und dann ist das auch ein Gesetz der Gegner von S Nahrung ganz einfach also diese länger bis es dann nicht von es nach es gerade das hier dieser länger das dieses Teil heiliges das kürzeste Länge von etwa voraus gerade das hier und da Unterschied zwischen beide sind gerade die Kosten des erkannte so und im Allgemeinen das
vielleicht nochmal vielleicht neue Zeichen mit dem etwas ab anderen Bild auf ja allgemein gilt für jede Kante Frau die ich nicht mal so hier unser S wir haben jetzt hier zweitkürzeste Wege irgendwo gehen die auseinander und und die Aussage dieses Kurnaz Nummer 6. 2. Kurs auf dieser Folie ist jetzt dass dieses Bild der SV der Abstand Distanz von es nach V nicht kleiner sein kann als der Abstand von ist nach Plus plus dem Gericht von und noch Frau warum ganz einfach der kürzeste Weg von Essen nach plus dieser kannte ist ein möglicher Weg ihren ja das ist die Länge eines möglichen Weges noch vor die Länge des kürzesten Weges erfor- kann nicht länger sein als die Länge irgendeines Weges nach vor so warum machen wir das weil wir
das jetzt plötzlich weil wir da jetzt plötzlich auf die Idee komme einer Operation durchzuführen Lauf vor und das Algorithmus die das was sie bei der Xtra gesehen haben und das was Sie bei wenn man fort so der gesehen haben alles vereinheitlicht sodass diese ganzen Operation dieser einen ganzen Algorithmen Spezialfälle eines allgemein Schemas sind so wie das bei mir können Kosten auch gesehen haben bloß natürlich etwas anderes so die Logik ist die wir arbeiten wir haben natürlich Distanz lebend im Grafen lassen jetzt irgendwelche Werte und wann immer wir feststellen das ist eine Kante gibt bei der eine Karte Frau bei der die Distanz von vor der aktuelle Distanz wird jetzt in einer nicht die echten es dann so dass die aktuellen Werte die hoffentlich irgendwann am Ende die echten ist unsere werden wann immer dieser Distanz wird größer ist er von Frau größer ist als es dann zur vom Plus Gewicht erkannte wird das entsprechend die dass das ist was da drunter gesetzt und das ist immer die die reingehen erkannte wird entsprechend abgedichtet so war steht hier was hier steht ist ernst im Distanz wird von Frau steht die Länge eines Vaters links rechts steht auch alle die Länge eines Falles von ist noch Frau also den Länge eines Falles von 1. vor Rechte die Länge eines Falles von erst noch Frau und die rechte Länge ist kürzer als die Linke wäre ich länger die etwas gerade für vor gespeichert wird also setzen wir doch die Distanz von Frau Hunter auf die Länge des Pfades der steht nicht mit des Ringes war das steht ja meine neuen Pfad gefunden der größer ist als der Fahrt vorher es nur der Fall würden hier mit dem Pi auch aktualisiert genau und letztendlich ist es genau das was in diesen Algorithmen allen gemacht werden nicht so schön extrahiert Initialisierung ist der in die Distanzen ich habe es immer Deltas genommen und hier auf den vorhin Stätten des aber ich glaube diese keine Abstraktion Sprung dies so sind alle Plus und Plus endlich warum weil wir gesagt haben er die Distanzen soll niemals kleiner sein als die Distanz für die Besprechung sowie müsste also das siedelt tanzen die echten das Tanzen und das dass wir auf der sicheren Seite wenn man mit unendlich anfangen und natürlich habe wir noch kein Baum konstruiert das heißt also die Pie Werte sind alle wollt oder Dschaber neue ja gut diese das nehmen Sie zur Kenntnis die letzte Zeile und nicht zu diskutieren dann so die Aussage
die Städte ist wenn wir mit mit unendlich großen oder mit mit mit Gewichten Anfang mit kann man anfangen Töne mit mit Distanz werden die anfangen die größer als die echten Distanz Werte sind nicht leider ebenfalls dann kann man so oft korrigiert korrekt an wenn wir wollen diese kleine Korrektur wir gehen offensichtlich niemals unter die echten Werte weil wir immer den den Wert immer korrigieren auf die Länge eines anderen Vaters und in dem Moment wenn das erreicht haben wird natürlich nichts mehr passieren wie er wir wissen das natürlich nicht ob das erreicht haben oder nicht weil wir nicht wissen ob nicht vielleicht doch noch mal irgendwann eine neue Kultur kommt aber in dem Moment wenn wir das erreicht haben wo wir es wissen oder nicht passiert nichts mehr mit diesen Quoten so den Beweis glaube ich brauchen wir da nicht das hat sich jetzt mit dem was ich gesagt habe schon so weit
geklärt der gut wir das ja gut ich diese Beobachtung wenn der letzten wenn man letzten Knoten haben auf einen Christen fort und wir werden wir werden auf die Kante von nach Frau das korrekt an ich denke dass das auch sofort einsichtig er die
gut was diese vor jetzt wenn man sie ganz fertig haben kann sagt ist wir wir haben keine negativen Zyklen erst meine Grafen wir werden später noch mal zu negativen Zinsen kommen wir haben es mal keine negativen zu trafen und die von also aus erreichbar sind natürlich in welchen Bereichen die von also gar nicht erreichbar sind können durch negative zeigte sein so viel sie wollen so und wir haben die Kanten Gewicht der entsprechenden 10 visiert und die und die reingehen kannten und die Behauptung ist wir machen also die behaupten es müsse schärfer als es hier formuliert ist igt vor mir ende und ne Sequenz sondern für eine maximale Sequentia machen so aufgeregt wie es geht egal aber in der in welcher Reihenfolge das habe vor in die Sequenz so auf das geht wenn so viel wir korrekt an das heißt so oft wir dann noch die noch mal zurück
hier so viel noch diese Situation haben ein TV größer des plus Kosten wird von der Kante UV solange wir noch diese Situation haben wenn
wir die Korrektur Schritt an und wartete sie gar nicht rein weil wir das machen was am Ende rauskommt ist eine aber was für uns ja mutet ehrt es also mit ein Sieger wozu ist per Definition haben wir natürlich immer nur einer reingehen erkannte dass es man wichtiger Punkt er eine reinigende kannte bei jedem Knoten maximal 1 Jahr sie werden sich daran was was diese bezeichen bedeute nie die reingehen kannten von Frau am kommt und was nicht das Ganze ist
zyklisch der an wer weiß durch Widerspruch wenn dem 1 gibt einen Züge da und dieser genau dieser Züge kann nur wie wird das Argument gut dieser ist natürlich durch korrekt Operationen entstanden wir ja genau genau der das Argument ist jetzt folgendes angenommen es entsteht dadurch ein Züge die Obst und Sorge ein enormes entsteht dadurch ein Züge das sind die Knoten v 1 v 2 und so weiter bis Fokker dann wissen wir Folgendes die V 2 ist gleich für D V 1 Plus Gewicht von dem von vollen vereist vor 2 mehr kann man das so sehen ich glaube ich muss da ein bisschen ja er das kann man noch sehen die vor 3 bis gleich den vor 2 plus kosten wird und so weiter bis Delhi V 1 ist gleich DEVK hier schließt sich der Zügel plus kosten wird so wenn ich das jetzt wenn ich jetzt in die Gleichung auf summiere die linken Seiten aufsummieren und die rechten Seiten auf so mehrere da komme ich am Hof hier auf 0 und hier auf die Länge des Zügels es aber nicht genau das was hier steht hier wird behauptet dass es negative Züge sein muss Gott wenn Sie mir so weit folgen gar nicht mehr was wir gesehen haben ist doch durch die Korrektur die beiden warten Sie mal was ist das Argument jetzt hier an dieser Stelle wenn der Züge haben in dieser aber was in der nicht aber sind in diesem Graf Dinge ganz die eigentlich die kürzesten der Russlands der kürzesten Wege werden soll wenn wir einen Züge haben haben Sie wie das habe es nicht verstanden okay also hier comma M wie von es wahrscheinlicher ja Herr ja ach so aber genau okay gut danke wo man sich Vorlesung haben ich ja dafür bezahlt ja ja okay die gern ich verdient so geht es genau das ist das ist das Argument dass es sicherlich in einem dieser wo man an dieser Stelle wenn wir hier den Zügel fließen hier dann ist diese länger hierüber kleiner als diese Länge also diese Länge einmal rum ist kleiner als die Länge direkt nach V 1 und damit musste Züge negativ sein ich glaube es ist noch kein exakter mathematischer Beweis aber ich denke es ist ist ist einsichtig so was bleibt noch übrig also ich gehe es immer so ein bisschen salopp vor wenn ich sage dass noch keine mathematische Beweis eigentlich bin ich der Meinung dass natürlich oder was Ich bin dann mal natürlich muss alles exakt mathematisch bewiesen werden das heißt es aber nicht dass wir uns gemeinsam mit jedem dieser einer exakten mathematischen Beweise herumquälen müssen sondern sie tun das was sie auch vermutlich tun wenn sie mit dem Finanzberater zu tun haben Sie glauben eben mit dem Versicherungsvertreter und so weiter sie glauben genauso was sie mir ich meine Konsequenzen wenn Sie mir glauben ist das sehen wir gute Leute kriegen die Konsequenzen wenn Versicherungsvertreter glauben sind deutlich schlechter das weiß alles natürlich nicht wissenschaftlich wissenschaftlich aber weiterhin war bitte das soll ich jetzt beweisen dass die Konsequenzen sind weil sie glauben schlecht Polenza schlechter sind als wenn Sie mir glauben okay ich glaube ich ziehe das Ganze wieder zurück so dass wird keine Züge gebildet und macht es es kann man ja die von vorne rein sowieso ausschließen beziehen was es wird von ausgeschlossen weil kleiner als 0 kannst dann nämlich werden und nur so von Anfang an initialisiert also keine es nie was passieren und damit ist mir aber was jetzt geht aber hier doch ein period nicht in den Beweis ja da also warum warum allgemein diese wertet er sämtliche P wird für alle Knoten die von S aus erreichbar sind am Ende 0 nicht nur sind nicht das Feld ist noch in diesem befreit oder wir ihn das nicht diese für den das nicht am Anfang sind alle 0 was macht Sie so sicher dass am Ende alle Knoten Knoten Faro die von S aus erreichbar sind 1 nicht 0 die von Vorhaben er genau also ich würde das glaube ich so begründen so formulieren ja die würde ich das formulieren also es gibt Knoten von es Beginnens wo er hingekommen ist die haben P wird und gleich 0 und dann gibt es im dann gibt es und welche Knoten die erreichbar sind von es aber wohl nicht hingekommen ist so da gibt es aber man sozusagen einen 1. Knoten wo nicht hingekommen ist auf dem Weg zu diesem ja und wie gehen wir gehen davon aus es gibt oder wir sagen es gibt jetzt einen Knoten zu mir was du willst sondern es gibt ein blutender irgendwo draußen in unendlichen Weiten der nicht der zwar von S aus erreichbar ist aber nicht erreicht worden ist dann gibt es ein 1. Piloten hier der nicht erreicht worden ist und hier bei dieser kann dann wie ein Widerspruch denn hier immer noch unendlich und hiermit endlichen wird er das wäre noch hätte noch korrigiert werden müssen Widerspruch also ist alles erreicht was erreichbar ist so der
extra fernsehen weiter
Behauptung ist bei Determination ist extra Algorithmus kommen die richtigen Werte raus wir sehen so ja nix nix zu lachen der der Algorithmus terminiert war ja in jedem Knoten in ihrer dazu neigt und wenn man den geregelt wird das heißt also minus 1 für man keine Iteration willigen viele Staaten wurden für jeden andern haben international 1 einzuschreiten terminiert der Algorithmus und wir haben zu zeigen dass das Ganze hier hat dann die richtigen Werte habe da ich fragen wer von ihnen Hartz hat nicht bei mir die Idee zu wird okay nein gar Dach H E ist dort bewiesen worden dass Geld extra funktioniert bitte ich verstehe ist also bei Herrn Haupt der für diesen bitte ja aber nicht alle von ihnen er sie waren Tutor Sie wissen das natürlich aber nicht alle wir von ihnen hat noch den Beweis gesehen haben muss unter extra bitte wollen Sie einsehen sie wollen einsehen bitte Umfang des Beweises ich versucht den letzten 10 Minuten okay das in die Hände 10 Minuten plus Tafel Bestzeit ich so ich mache sowie in meiner GD 2 sorry aber so viel ich das ein bisschen angenehmer als als die typische Ordnung weil sie wissen wir Torturen so und in Folie viel gemacht wird dies war leider habe ich jetzt nicht die richtigen Farben dar da gibt es grün aber wie ich damit auf der Tafel rummale mit dem denkt den gibt es Ärger so dass es wieder mal mein Graf zur und das ist es zu jedem Zeitpunkt gibt es eine Zweiteilung in der extra eines weiteren der Knoten ja also in mündlichen Prüfungen habe ich das schon öfters mal gefragt spitz das Zauberwort mündliche Prüfung würden stellen sich vor Sie haben eine Million Knoten und der muss hat jetzt 300 Tausend Iterationen der sich beschreiben Sie doch mal was was wir jetzt über den alten den den aktuellen Zustand sämtlicher gespeicherter Werte wissen wer will der Bundesvorstand hat sollte Lage sein das zu beantworten nicht also die hier drinnen diesen schon fertig da schon die aber sind die haben schon die richtigen Werte die da draußen wir haben Folgen der folgende des Werte von Distanz Werte die die haben den er als Distanz aktuellen Distanz wertet den kürzesten Weg die Länge eines kürzesten Weges von S dahin und alle einen Knoten gehören hierzu der fertiggestellten Menge das heißt also einen Knoten der direkt anschließend kommt hier an diesem Bereich der hat einen endlichen wert nicht die Länge des kürzesten Weges von hier durch und dem Knoten der weiter weg ist der keine direkte kann davon hat der hat weiterhin der Welt und endlich was ja auch stimmt die Länge eines kürzesten Weges der der nur kannten in diesem da den inneren Bereich enthält es gibt keinen solchen der die Menge R die Menge es werde man an solchen Dingen sehr und das Minimum über die leere Menge ist unendlich ja ist denn das bewusst wurden so mache ich das in Minimum wäre Menge ist immer plus unendlich Maximum der deren Menge ist minus unendlich das ist so in der Mathematik gesetzt worden aber das funktioniert immer auch so es trifft was jetzt passiert ist das ist die Variante war ja das ihn Variante die haben die richtigen Werte und die Knoten haben kürzeste Weg Längen von von wegen die nur in der Knoten enthalten bis auf den letzten Mann natürlich so was passiert jetzt in 3 extra wir nehmen uns jetzt einen Knoten her den nehmen wir zur inneren zur inneren Mengen zu zu sagen wir wollen diese innere Menge aus wenn Sie so wollen und abdecken die gibt die ihre eigenen Werte Distanz werde der Knoten die von diesem von diesem Klon aus erreichbar sind das ist das so dass wir dieser Vision von dem was Drechsler macht vielleicht nicht willst diese Vision aber ist es ist eine so welche Ecken Knoten ist das hier Jahr wir nehmen den mit dem kürzesten Distanz wird nach dieser Logik warum was wir beweisen es ist dass Variante weiterhin gilt dass dieser Knoten dessen Distanz wird rühren der kann ich in dem Moment mehr an sondern diese Distanz Wärter die ändern wir jetzt diesen bleiben wie wir es das heißt wir müssen jetzt beweisen wenn Sie ich hier den kürzesten den kleinsten es Konzert erleben dann ist das tatsächlich den erfüllt der tatsächlich den Variante für die inneren Knoten das in kürzester ja das ist das ist der Weg länger die Distanz wird von ihr warum ist das so einen Namen dahin muss man das Ganze noch mal neu müssen zeichnen so ich wieder mal Grafen ich zeichne den inneren Bereich jetzt mal mit weniger die Teile und das ist der Knoten hinzunehmen warum ist diese Fahrt Länge tatsächlich die wir jetzt haben die kürzeste Weg länger so dass wir also mit dieser Distanz wert diesen Knoten zu inneren Mengen zu nehmen können angenommen es wäre nicht der kürzeste Weg die länger als christliche denn gäbe es also Obst einen kürzeren Weg hierher irgendwo anders langte könnte zum Beispiel so so so laufen hier mehr wenn das nicht der kürzeste Weg ist gibt es einen kürzeren der irgendwie läuft wir kein Kraut und Rüben auf es uns egal wichtig ist es gibt diese kannte ja mit diesem Knoten hier dieser wird uns die allererste mit dem mit den inneren Bereich verlassen so hier hat aber momentan kürzere Distanz wird oder Wüstensohn klein das das für eine größere Distanz oder müssen so groß ist und wir wieder hier ja der ist weiter weg als der wenn das hier ja dann insgesamt kürzer werden sollte und der es weiter weg denn nur dann ist der Rest hier negativ Widerspruch haben keine negativen kannten und das auch keine negativen verdrängen so einfach ist die Welt wenn man einfach mal diesen zeichnet und nicht fällt natürlich jetzt auch hier Pflug Pflug Pflug Flop da sehen Sie ungefähr dasselbe Bild noch mal es geht noch weiter
Flipflop Flop fortführt Flop Flop und
damit ist der Beweis zu Ende nicht halt Halt Beweise zu Ende nicht vorlesen zu Ende
müssen ja gut also ist was anschaulich ist ja Beispiel von 3 extra brauche ich hoffentlich in dieser Runde hier nicht durch zu durchzugehen oder nein das haben sie ihm egal bei wem sie das gehört haben das haben sie mit Sicherheit verinnerlicht Laufzeit von der Xtra
aber wie sieht wie Sie die Laufzeit und extra aus die einfache Laufzeit von Dextre und so vielleicht mal wieder die einfache Laufzeit von der extra ist in jeder hielt sie haben wovon Iteration Endes ein Situation um genau zu sein da kommt der eine Faktor von dem Quadrat der und das was Sie in 1 Schritt machen was machen Sie in einem Schritt wenn Sie wenn Sie es ganz dämlich anstellen oder baute Kjus und so weiter auch wirklich ganz primitiv machen was machen Sie in einer Iteration sie gehen alle Knoten die noch nicht permanent sind die noch nicht über eine Menge durch sind und nehmen sich den Knoten mit geringsten will der Distanz O von wohnen und von diesem Knoten aus dem sie alles was von da aus auch erreichbar ist auch ab von denen wovon endlos so von 1 so von allen in Idee tration kostet von NO von Indikation gibt insgesamt in Karat so das ist das wenn man es ganz primitiv macht der bei wirklich dichten Grafen die sehr nach an dem er ein mehr an einem vollständigen Grafensohn wird man auch nichts besseres hinkriegen weil man muss ja dann tatsächlich in jedem Knoten und von allen Fehler er andere Knoten betrachten zum Update wenn der Graf dicht ist so fast alle Knoten und so
trauriges haben Sie gesehen da geht's so nämlich an und der Einsatz wird extra brauchen wir jetzt hier nicht weiter durch zu gehen das setzen wir
voraus dass sie das alles gesehen haben und wie man in dem man aber Radicchio da extra formuliert haben sie auch gesehen und mir nicht zu machen bei
einer wie also als prallte Strukturen sie gesehen egal bei wem sie die geht so gesehen haben gehört haben wie lassen aus das ist eine kleine Variation nicht weiter wichtig ist Fibonacci ist er größere war ich weiter wichtig ist wenn man
wenn man nicht so viel Respekt vor den Leuten hätte wie ich es habe würde man sagen so was wie vielen über native befinden zum pervers da da
als Implementation ist hochinteressant ganz ganz kurz ganz witzige Sache und zwar ist die Idee es geht um die Beute Kilo nee die Zeit ist um was es da mal wieder okay tschüss bis nächste Mal
Loading...
Feedback
hidden