Optimal Trees and Branchings II

Video thumbnail (Frame 0) Video thumbnail (Frame 7900) Video thumbnail (Frame 15619) Video thumbnail (Frame 20072) Video thumbnail (Frame 22917) Video thumbnail (Frame 24897) Video thumbnail (Frame 27034) Video thumbnail (Frame 34321) Video thumbnail (Frame 36586) Video thumbnail (Frame 38486) Video thumbnail (Frame 47972) Video thumbnail (Frame 56724) Video thumbnail (Frame 59032) Video thumbnail (Frame 68126) Video thumbnail (Frame 71184) Video thumbnail (Frame 84606) Video thumbnail (Frame 88161) Video thumbnail (Frame 92201) Video thumbnail (Frame 95316) Video thumbnail (Frame 97786) Video thumbnail (Frame 104219) Video thumbnail (Frame 107946) Video thumbnail (Frame 111981) Video thumbnail (Frame 117176) Video thumbnail (Frame 119352) Video thumbnail (Frame 121547) Video thumbnail (Frame 123781) Video thumbnail (Frame 127072) Video thumbnail (Frame 128961)
Video in TIB AV-Portal: Optimal Trees and Branchings II

Formal Metadata

Title
Optimal Trees and Branchings II
Title of Series
Part Number
5
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.
Euclidean vector Direction (geometry) Gradient Spanning tree Inertialsystem Set (mathematics) Element (mathematics) Physical quantity Independence (probability theory) Subset Plane (geometry) Matrix (mathematics) Vector space Finite set Matroid Finite set Object (grammar) Linie Mathematical optimization Physical system
Kante Stress (mechanics) Sequel Decision theory Ende <Graphentheorie> Subset Independence (probability theory) Mathematics Matrix (mathematics) Matroid Vector graphics Absolute value Wiener filter Chain rule Euclidean vector Exponentiation Spanning tree Set (mathematics) Element (mathematics) Subset Independent set (graph theory) Algebra Function (mathematics) Network topology Ecke Optimum Object (grammar) Mathematical optimization Physical system Weight function
Subset Function (mathematics) Network topology Forest Matroid Set (mathematics) Mathematical optimization Element (mathematics) Subset
Kante Subset Stress (mechanics) Connected space Function (mathematics) Forest Matroid Set (mathematics) Mathematical optimization Element (mathematics) Subset Directed graph
Kante Stress (mechanics) Zahl Spanning tree Set (mathematics) Element (mathematics) Connected space Physical quantity Subset Connected space Mathematics Network topology Zusammenhang <Mathematik> Function (mathematics) Forest Network topology Matroid Mathematical optimization Absolute value
Kante Subset Connected space Network topology Decision theory Network topology Set (mathematics) Mathematical optimization
Kante Computer programming Inequality (mathematics) Weight Numerical analysis Connected space Mathematics Energie Film editing Grand Unified Theory Network topology Logic Category of being Mathematical optimization Pairwise comparison
Computer programming Duality (mathematics) Causality Direction (geometry) Dualism Set (mathematics) Computer programming Mathematical optimization Linear map
Kante Stress (mechanics) Zahl Weight Binomial coefficient Square Set (mathematics) Weight Subset Connected space Network topology Zusammenhang <Mathematik> Network topology Modulform Summierbarkeit Iteration Mathematical optimization Pairwise comparison
Kante Euclidean vector Great circle Network topology Direction (geometry) Network topology Special unitary group Mathematical optimization Directed graph
Kante Stress (mechanics) Zahl Logarithm Euclidean vector Laufzeit Set (mathematics) Inverse element Mathematical structure Statistical hypothesis testing Connected space Duality (mathematics) Zusammenhang <Mathematik> Network topology Structural equation modeling Quote Linie Mathematical optimization Factorization Linear map
Kante Logarithm Zahl Block (periodic table) Weight Physical law Letterpress printing Square Connected space Estimation Network topology Zusammenhang <Mathematik> Network topology Graph (mathematics) Vertex (graph theory) Mathematical optimization
Kante Statistical hypothesis testing Series (mathematics) Logarithm Interior (topology) Laufzeit Maxima and minima Connected space Number Radical (chemistry) Causality Network topology Zusammenhang <Mathematik> Network topology Graph (mathematics) Universe (mathematics) Vertex (graph theory) Summierbarkeit Mathematical optimization Curve fitting
Expected value Planar graph Hamiltonian (quantum mechanics) Process (computing) Travelling salesman problem Network topology Graph (mathematics) Cloning Mathematical optimization Pairwise comparison Factorization Linear map
Kante Stress (mechanics) Hamiltonian (quantum mechanics) Weight Graph (mathematics) Maxima and minima Inertialsystem Mereology Subset Forest Sign (mathematics) Mathematics Network topology Zusammenhang <Mathematik> Travelling salesman problem Network topology Many-sorted logic Condition number Set theory Vertex (graph theory) Mathematical optimization Gebiet <Mathematik> Directed graph
Kante Forest Sign (mathematics) Counterexample Weight Graph (mathematics) Many-sorted logic Maxima and minima Mereology Mathematical optimization Directed graph
Decision theory Decision theory Complex (psychology) Mathematical optimization Maß <Mathematik> Reduction of order Fundamental theorem of algebra
Kante Logic Weight Graph (mathematics) Mathematical optimization Directed graph Mach's principle 19 (number)
Kante Weight Graph (mathematics) Graph (mathematics) Mathematical optimization Directed graph
Kante Inclusion map Inclusion map Subgraph Weight Graph (mathematics) Graph (mathematics) Mathematical optimization Category of being
Inclusion map Stress (mechanics) Subgraph Weight Graph (mathematics) Graph (mathematics) Entrainment (chronobiology) Mathematical optimization Category of being Open set
Stress (mechanics) Graph (mathematics) Weight Lemma (mathematics) Feasibility study Theory Insertion loss Zusammenhang <Mathematik> Graph (mathematics) Vertex (graph theory) Mathematical optimization Maß <Mathematik> Proof theory
Kante Stress (mechanics) Graph (mathematics) Weight Lemma (mathematics) Maxima and minima Feasibility study Theory Time domain Thetafunktion Graph (mathematics) Vertex (graph theory) Mathematical optimization Proof theory
Kante Rule of inference Stress (mechanics) Logic Graph (mathematics) Function (mathematics) Vertex (graph theory) Summation Mathematical optimization Number Mach's principle
so genau sind die anderen immer so sein dass er verlängert werden an der TU Darmstadt so hallo allerseits
und vor ab organisatorische ist Herzen zwar bietet er für diejenigen die einen Einigungstermin nicht können auch privat Sprechstunde zu machen 2. 14 Grad auch hier noch auf dem Stapel hier aber ein paar nicht abgeholte Abgaben und 1. Übungsplatz hier eingereicht hier bitte wenn Sie noch abgeben wollen bitte auf diesen Stapel bitte nicht durcheinanderbringen so wir waren hier stehengeblieben wir Generalthema momentan ist immer noch wollen wir in ungerichteten Grafen ein Thema was aus der GDI 2 kennen Stichwort groß Stichwort Brillen minimal spannender Bäume und ich habe mir überlegt wie beim Thema Madrider sich zunächst einmal mit einem anderen Projekt beginnen als mit dem als mit dem das sich er worum es hier eigentlich geht weil ich glaube ich habe mir vorab überlegt dass es vielleicht anschaulicher es dazu gehe ich vor die Kamera obwohl ich eigentlich jetzt nicht unbedingt in meiner Kammer stehen will aber in dem Fall ist es vielleicht doch sinnvoll der Begriff maturiert kommt daher das hat etwas mit Matrix zu tun und zwar stellt man sich die Spalten einer Matrix vor ja das sind schlicht und einfach endlich viele Sektoren in diesem Vektorraum sie haben meistens den er auch irgendwelche RUS kennen gelernt als Vektorräume das heißt und immer auch n daher kommt der Begriff Madrid und ich will versuchen Ihnen passt das plastisch zu erläutern was Makrolide sind nämlich solche endlichen Mengen von Vektoren mit dem Thema Linie Unabhängigkeit dass sie aus der aus den er über keine Abgaben bitte auf dem genau auf dem starken danke so was bilden wir können natürlich immer im er auch 3 sein logisch was anderes kann ich Ihnen leider nicht anbieten dazu reicht meine didaktischen Fähigkeiten nicht aus was bedeutet es dass 3 Vektoren meine 3 Finger sind jetzt die 3 Vektoren was bedeutet dass die wenn unabhängig sind das bedeutet dass sie sozusagen so in 3 verschiedene Richtungen abstellen und eben nicht so planar in einer einzelnen eben nicht das ist in dieser anschauliche geometrische Interpretation von Jahren Unabhängigkeit ist ihnen deutlich mehr genauso für 2 Vektoren was bedeutet dass die Wiener welche sie sind dass sie 12 Bericht verschiedene Richtungen sind und nicht in einer Richtung oder so rum in 2 unterschiedliche Ausrichtung aber immer noch in derselben graben und sind das ist länger unabhängig so womit wir uns hier befassen beim Thema Madrider wenn wir dieses Beispiel jetzt noch weiter verfolgen ist 2 Mengen verliehen der unabhängigen mehr einerseits diese 3 hier er wieder ich Dreher solange ich die die 3 jetzt nicht irgendwie zu der Ebene mache sind die Wiener unabhängig und 2 weitere 2 und 3 ich kann man zwar müssen denn nicht aber vor aber ich hoffe das hilft so was mit was die Eigenschaft eines Macdroid ist die Kennzeichen Eigenschaft als mal prügelt ist sie haben jetzt 2 Mengen von unabhängigen Vektoren die unterschiedliche Kardinalität haben dass eine hat Kardinalität 3 hat Kardinal Kardinalität 2 größerer Kardinalität kleinere Kardinalität und gehen in dem für die wir in der Menge mit größerer gerade Naivität finden Sie immer mindestens ein Sektor gehen Sie Herrn können in die mit einer Karte Naivität und dann ist es immer noch in noch unabhängig ja also was bedeutet es dass diese 2 Finger hier diese beiden Sektoren nicht Herr keiner von den beiden hergenommen werden kann zu den hier dass die Wiener unabhängig sind das bedeutet dass die 4 Vektoren in einer Ebene sind nur dann also die müssen sicherlich nicht so schön parallel sein sondern irgendwie gedreht in einer Ebene nur dann kann ich keine dieser beiden Sektoren hier hernehmen er weder den einen noch den anderen und ihn zu den zu diesen beiden hinzufügen und das ist ja unabhängig egal welche ich nehme es alle 3 sind in einer Ebene so aber wenn diese beiden in einer Ebene sind dann ist da ja auch der 3. der offensichtlich nicht diese Ebene ist und wir war davon ausgegangen dass die 3 Länder unabhängig sind und dann kann ich diesen dritten hernehmen und kann den hier den müssen sich natürlich jetzt nicht Thomas vorstellen sondern dieses mal die gewöhnt sind sehr abstrakt können Sie diesen Mittelfinger hernehmen und dessen Richtung hier zu diesen beiden mit zu nehmen und alle 3 sind länger unabhängig das ist die konstituierende Eigenschaft eines Madrids wovon ist hier die Rede wir haben eine insgesamt endliche Menge von Objekten von Sektoren in diesem Fall wir
haben eine Eigenschaft die unabhängig die 3 sind in der unabhängig die 2 sind unabhängig eine Eigenschaft die sich nach unten fortsetzt der wenig von 3 Wiener oder bringen Vektoren ein bequemer dann ist das immer noch in der auch unabhängig Jahr setzt sich aufteilen man fort welche rein wegnehme immer noch Dinge unabhängig jeder Vektor ist per Definition mit sich die bin nicht noch ein nehmen die leere Menge ist per Definition in der unabhängig aber in China period ist wenn ich 2 wie der unabhängige Mengen habe die unterschiedliche kann die Naivität habe dann finde ich immer egal wie es dreht und wendet versuchen sie es aber egal wie Sie es drehen und wenden sie finden immer unter diesen dreien mindestens 1 denn sie sich ausbauen können für die kleinere Menge für die zu einer Menge hier und die 3 zusammen sind immer noch länger und habe ich das ist entscheidend wichtig hier also ich habe in kleinen Exkurs gemacht in einer ein anderes Beispiel für Makrolide wir der gestartet vom Thema minimal spannende Bäume und das ist auch hier entspannt er entscheidend wichtig weil er auch nie in minimal spannende Bäume mehr eine diese eine in das wenn wir gleich sehen in welchen Sinn der diese Madrid Eigenschaft haben und weil diese Macdroid Eigenschaft entscheidend wichtig ist das habe ich beim letzten Mal am Ende kurz angedeutet entscheidend wichtig ist für dafür dass der greedy Algorithmus der gierige Algorithmus der immer nur eine Karte nach der andern prüft unter wenn's geht Algorithmus Kursker dass der funktioniert also tiefere Hintergründe hinter einem Algorithmus den sie schon kennen so und jetzt gehe ich mal aus der kann aus und wieder hier hin Was ist eine Matruh Aids wir haben es hier nicht gesagt dass er endlich ist es ist aber dass ist immer die Voraussetzung für die Definition eines Madrids die wäre hier ist drinnen ja hat man gesagt hat eine leere Menge von Vektoren ist mir unabhängig so ist definiert und das ist wieder mal ein schönes Beispiel dafür dass solche Reinfelder ja Mathematik typischerweise sehr vernünftig definiert sind vielleicht noch mal andere Beispiele von Rheinfelden wenn Sie definieren 2 hoch 0 wissen Sie das ist definiert als 1 warum weil es die Kette genau fortsetzt soll um 0 2 Uhr 1 2 hoch 2 und so weiter und so fort passt ja einfaches Beispiel dafür dass man solche Anfälle die man eigentlich nur normalen Definitionen wie einer Potenz gar nicht drin hat dass man die sinnvolle Fortsetzung genauso ist hier wenn man die nach Unabhängigkeit auf die leere Menge fortsetzt an allen Ecken und Enden der Wiener Algebra passt es wunderbar und so auch hier ja also irgendwo scheint da doch ein höheres Princip zu sein das ist immer so gut miteinander sind Definition immer wieder so schön aufgeht so 2. was ich gesagt habe wenn ich 3 Vektoren habe und ich nehme einen weg oder auch 2 weg oder auch 3 weg das ist das Ergebnis wieder länger unabhängig wenn 2 Dinge unabhängig war das ist hier formuliert das B sind meine 3 Vektoren meine meine 3 Finger das aber ist nur Teilmenge davon Obst ja also ein Finger weg oder 2 Finger weg noch und wenn die wieder oder wie war wenn ich die in alle gespreizt habe und ich nehme Finger weg dann ist das natürlich auch Ihnen unabhängig klar und jetzt kommt dieser Austausch Eigenschaft diese konstituierende Eigenschaft von der ich gesprochen habe wenn ich 2 linear unabhängige Vektoren man habe und eines kleiner als die andere Betrag kleiner B Betrag dann finde ich in B man muss ja nicht dass zu seiner diesen fertig es vielleicht ausgespart aus Versehen soll ich noch mal vor der Kamera machen ist ist diesen schwierig also der darum rechts ist parallel zum Zeigefinger links oder Zeigefinger recht ist parallel zum darum längst er kann sich das vorstellen gut also Sie sehen diese beiden Mengen sind nicht dass sie und muss nicht sein aber ich finde in dem in der in der in der was das ist das eine Differenz Menge hier die Differenz Menge ist der ist in diesem Fall noch der der das ist das den Mittelfinger also der Finger denen zeigt nicht das ist die Differenz Menge der Mittelfinger und diese in dieser Differenz Menge finde ich tatsächlich einen Vektor der nämlich den Mittelfinger denn ich hinzufügen kann zur kleinere Menge und dann ist es wieder weniger unabhängig so aus das nennt man einmal Droid und was wir uns hier wichtig
ist sind müssen zum 2 Dinge 1. dieser Satz denn ich allerdings nicht beweisen werde falls Sie gerne einen Beweis davon sehen möchten lade ich Sie gerne ein in meiner Vorlesung Optimierungsalgorithmen diesem Semester wird aber doch ein paar Wochen dauern bis wir dahin kommen hier beweisen wir das nicht weil es ein Randthema ist dort bei Optimierungsalgorithmen das ist mehr als nur ein Thema so was hier steht das Folgendes also wir haben endlich immer von Objekten der dieses die ja zum Beispiel die Spalten einer Matrix daher der Name wie gesagt Madrid so und die haben auf jeden Objekten Gewicht und sie werden jetzt Ingrid Algorithmus sagen wir können es vielleicht sogar gehört hat Kruska wieder her nehmen wir haben die Kanten auf wieder kann da mein Gesicht und wir werden Kruska waren das heißt wie die wir gehen die Elemente bis endlich egal wie rum aufsteigend oder absteigend sortiert es eine matschige sondern maximale spannen Baum und jedes Mal wenn eine neue Karte die wir nehmen noch reinpasst noch unabhängig ist also keine Züge hat das war der Begriff Unabhängigkeit sein Züge Freiheit dann nehme die kann der um den es zyklisch schließt also nicht mehr unabhängig wird bei beiden zu nehmen wir dann immer diese kann der nicht das ist der der Kunst ganz kurz kurzsichtig oder eigentlich wie also Greely also direkt was gemeint ist ist man macht Entscheidungen kann der reingenommen kann nicht um und dieser scheinen macht man nie wieder rückgängig ja das ist das ist die Essenz von Kruska einer einmal getroffenen Scheidung reinen oder nicht frei nehmen für die wieder rückgängig gemacht und das ist hier die Algorithmus so und diese Aussage hier diese tief aus aus den fünfziger Jahren entwickelt besagt wenn diese Struktur einmal Droid ist denke und ich finde diesen Algorithmus an egal mit welcher Gewichtung ja egal welche wählen werde ich den Einzelobjekten zuweise es kommt am Ende das Optimum die optimale unabhängige Menge heraus ja das ist richtig die optimale unabhängige Menge die unabhängige Menge mit dem allergrößten Gesicht das gilt auch wenn sie nicht so steht auch umgekehrt werden das Ganze einmal Droid ist dann gibt es immer mindestens eine Gewichtung open bracket in Wirklichkeit unendlich viele close bracket also es gibt immer mindestens eine Gewichtung bei der Kri Algorithmus nicht zu optimalen Lösung kommt wie gesagt der Beweis dafür eine Vorlesung Optimierungsalgorithmen das Ganze wird sicherlich jetzt deutlich anschaulicher wenn wir wieder zurückkommen zu unserem eigentlichen Ausgangssituation nämlich zu spannenden wollen die
Behauptung ist da ist minimal Spanne Bäume haben irgendwas mit trügen zu tun erst einmal nicht was ist damit gemeint also was ist dieses von dem hier die Rede ist dieses Absatzes gleich alle spannend werden nicht mehr bäume sondern Wälder im Grafen ja was Blut was bedeutet das sie nehmen alle möglichen spannen Bäume her und wolle aus Madrid machen na ja Sie wissen Teilmengen müssen dazu gehören also was sind die Teilmenge spannend weil mir das nicht bannen Wälder ja sie nehmen wir kann daraus aus dem Schwan Baum wir haben den Baum zerlegt in 2 Teile 2 Boll 2 Teile wollen wieder ergibt ein Wald mit 2 wollen nehmen wiedererkannte raus wir betrachte immer Spanne als kann man man wieder mehr kann daraus haben es insgesamt liegt in 3 Teile Bäume und so weiter und so fort so lange bis sie alle Karten ausgenommen haben dann haben sie die leere Menge erreicht der spannende Wald besteht aus Knoten aber nicht kannten wir Menge von kannten so und die Behauptung ist dass das einmal Droid ist die Menge aller spannen Wälder in Grafen ist ein Madrid so so hier behauptet wir 1. beiden Eigenschaften sind klar noch mal zurück das 1. beiden
Eigenschaften der Lehrer weit also mit ihrer Kantenlänge ist ein Madrid melden ja gut Zeit man noch mal genau sagen
richtig also E das sind die ist die Menge aller kannten und das ist die Menge aller Wälder verstanden als kann man ja wir brachten hier immer wollen wir Wälder und alles das kann man beide Knoten Menge mit diese ist genau ich sagen sollen vielen Dank so O die 1. Eigenschaft
wäre könnten Menge ist ein weites Züge freier was heißt weit weiter sieht aus als frei eine Teilmenge der Kanten Menge die Grenze keinen einzigen 2. wenn ich aus dem Wald noch könnten rausnehmen welch Züge freien Graf noch kannten rausnehmen und ich anderes muss Tour bleibt der natürlich Züge frei die zweite Eigenschaft ist auch er für die 3. Eigenschaft die machten schon Kopfschmerzen wenn man sie nur lesen jetzt macht uns natürlich nochmal Kopfschmerzen wenn wir sie versuchen zu beweisen aber ich will versuchen ihnen des
Kopfschmerzen möglichst gering zu halten in der Milch einiges an der Tafel versuche zu veranschaulichen was jetzt in den Folien nicht so ganz veranschaulicht worden ist dafür brauche ich jetzt schon wieder so so ich glaube das kann ich weg das passt schon so vielleicht haben wir immer noch mal kurz einen vorlegen wir haben 2 wäre da Imker im selben Grafen und ja wir haben wie üblich sie kann das schon bei mir das ist ein Graf die gleich V die Claude Menge kann man und gerichteter Graph so was müssen wir beweisen wir müssen beweisen die immer noch mal zurück diese Eigenschaft für je 2
Wälder W 2 Schwangere in diesen Grafen gilt wer sie unterschiedliche Kardinalität haben dann geht diese alte diese komische Austausch Eigenschaft so wir müssen uns also Sie kennen das und aus der Mathematik die
Formulierung 2 beliebige aber feste kann sie das beliebig beliebig aber festgehalten der spannende wäre daher eine und wollen zeigen dass dieser Austausch Eigenschaft gilt so jetzt kommen wir mal ein bisschen mehr in die Struktur dieses Grafen hinein also das reicht uns nicht dass wir jetzt hier Sohn so schönen Kringel gemalt haben mehr ein Krieger reicht uns nicht wir mal ganz gleich mehr mehrere Kriege auf einmal so sie kennen auch das auch von mir so was soll die Semantik dieser Kringel sein das sind die Zusammenhangs Komponenten ich kürzlich mal ob das war alles da das kleine und von den beiden wildern wenn es so weit ist also da B R größer ist kein keine Spanier bauen sollen sonst der schon maximale kannten zwar kann es keine größere kann so ergeben also ist aber kein Spanier bauen sondern ein weit ein echter Wald der in mehrere Bäume verfällt und das sollen diese Krise sein also was wir tun haben er zusammen Komponente ist irgendwie so da drin ein spannender Baum wer das nicht zusammenhängend sei also falls es aussieht mehr und mehr die Männchen oder die Tierchen die Bedienung Beschuldigung suche das sind die Zusammenhangs Komponenten von Ar was wir uns klar machen müssen ist das immer wieder zusammen Prominente ist eingeschränkt darauf natürlich ein spannender bauen das heißt hat für alle Züge freien Grafen maximale könnten zahlen ja also wenn wenn das hier VI ist dann ist die kannten Vorwahl VI Betrag minus 1 Jahr kann seinen spannen bauen sie mag nun sein es 1 so jetzt gucken uns Bean B kennen wir jetzt gar nicht wir wissen gar nicht wie viel genau aussieht und wie kann etwas über das Verhältnis zwischen A und B außer was jetzt ist mal wissen ist innerhalb von jeder Zusammenhangs Komponente vor von kann der auch nicht mehr kannten haben als er denn er hat schon maximale keinen Zahl innerhalb der Zusammenhangs comma nennt der Finnen zu befreien Grafen wie kann höchstens genauso viele oder weniger haben Ina wieder zusammen und es kommen aber B ist insgesamt die größere Menge B ist größer als das heißt es muss zwangsläufig irgendwo mindestens eine Kante geben die außerhalb aller zusammen Komponenten liegt die also 2 Zusammenhangs kommen 2 Knoten auf 2 verschiedene zusammen es gebunden verbindet und die natürlich dann auch nicht den sein kann und dieser offensichtlichen nehmen können ohne das winzige schließen und das war schon also sehen das was wir jetzt hier alles schriftlich machen sehen Sie noch mal hier kann kein Spanner bauen seinen zerfällt also in mindestens 2 Zusammenhangs Komponenten BSA Zykliker kann höchstens zu für viele Komponenten haben wie aber sowieso schon also kann er kann die nicht mehr comma mitten in der dieser zusammen das er nicht mehr kann wenn er diese zusammen kommen damals also muss es irgendwo eine andere kannte gegeben und das ist es auch schon genau damit haben wir ist
nochmals also noch mal zurück was haben wir um das abzuschließen was haben wir jetzt
gesehen wir haben noch mal das Thema minimal spannen Bäume eingebettet in ein grösseres Themas gibt die ganze Menge Madrider wir werden hier noch einmal dreht später kennen lernen im Rahmen einer Problemstellung die Sie ich auch schon kennen gelernt habe Idee 2 nämlich kürzeste Wege sehen wir werden feststellen dass sowas wie 3 extra so gut funktioniert lässt sich auch wieder zurückführen auf diesen Satz wenn es Madrid ist dann kann man einfach so vorgehen sie ändern sich bei der Xtra machen Entscheidungen die wir nie wieder rückgängig machen genau aus demselben Grund könnte das aber keine Sorge wir werden hier in dieser Vorlesung fiel auch viele Algorithmen kennen lernen diese nicht aus der geht so gesehen haben Nägeli gesehen haben das ist jetzt hier
keine Aufarbeitung der geht so so ein wichtiger Punkt nicht nur für für Bäume so allgemein oft interessiert man sich oft oft macht man sich das Leben einfacher so wie jetzt auch im folgenden wenn man annimmt dass die dass die Gerichte die man da hat paarweise unterschiedlich sind das keine 2 Kanten in diesem Beispiel dasselbe Gewicht haben ja da macht man sich manchmal 7 einfacher werden es gleich sehen ist aber natürlich nicht immer gegeben was macht man werden es nicht
gegeben ist dass wenn man gleich der wer es zunächst einmal machen uns mal klar dass die dass die beiden Eigenschaft die beiden die wir lässt man gelernt haben kapabel den zeige Property das auch die einfacher werden und auch algorithmisch einfacher werden wenn wir paarweise unterschiedliche kann Kosten haben denn vorher hieß es eine minimale K 1 kleinste bekannt oder eine große könnte jetzt wenn alle kannten oder sich Thomas immer die kleinste oder größte kann davon die wir darin wir haben keine der mit einem Schnitt und beim Zügel niemals 2 Kanten das selben Gewicht weil wir von der Annahme ausgegangen sind das ok 2 gleiches Gewicht haben so in dem Fall könnte überlegt schlecht probiert die beweisen dass wir das dass wir das immer er die eine Kante ein Film bzw. löschen können weil ich 11 Probe die sehen wir keine komme zu und kamen zu einer besseren kommen wenn das nicht die beste gewesen ist wenn ich jetzt hier nicht weiter ausführen was mir vor allem wichtig
ist das geht weit über Bonn hinaus es ist immer wieder sinnvoll dass man paarweise unterschiedliche Gewichte an an verschiedenen Stellen auch in der Mathematik verändern numerische Mathematik und ähnlichen wie kommt man dahin was kann man tun wenn die Gerichte doch nicht alle unterschiedlich sind eine Möglichkeit ist hier auf dem Folien verzeichnet eine andere ich Ihnen mündlich bis zum also an der Tafel kurz darstellen eine Möglichkeit ist dass man dass man an den Gedichten bisschen ruckelt dass man jedes Gericht ein kleines bisschen verändert oh das nennt sich Part Ovationen wenn sie wenn sie Daten oder den Namen hinsetzen Radtour so dass sie tatsächlich alle paarweise unterschiedlich sind und wenn diese Ruck um diese Deltas nur klein genug sind dann heißt es dass die das eine optimale Lösung eine optimale Auswahl von könnten hier beispielsweise wenn Sie mit diesem Forum um die diese der das war ruckelten gelten Werte also jede kann die eigenes Delta wenden diese Vogel dem werde wenn es da optimal ist und die der sehr klein genug dann ist auch das ist auch optimal für die ursprünglichen Werte er wird nur benutzt als Treiber Hacker Sie kennen das Urteil wird vielleicht vom Ternes dass man dass man eine bos keinen keine Möglichkeit mehr uns unterscheiden gibt dass man noch eine Unterscheidungsmöglichkeit einfügt gut und da wie gesagt was sagte wenn es klar wenn jeder das klein genug sind dann passt das schon eine zweite Möglichkeit die etwas sauberer vielleicht ist wenn man dann jetzt nicht mit so komischen kleinen Delta werden um rechnen muss da das ist sie haben kosten für jede Kante i g gegeben ja Sie haben es soll ein Regierung der könnten und sie haben neue Call sie definieren neue Kosten die nicht mal Z Tilde von in diese definiere ich jetzt mal bisschen komisch nämlich als ein Paar bestehend aus den Ursprungs kosten und diese W die Reihenfolge es soll sein Mexiko grafisch sie kennen Lexikographen schoss bringt ja wenn man des 1. Zeichen unterschiedliches entscheide das erste Zeichen das gleiches schon das zweite Zeichen wenn die gleich sind entscheidet sollte Zeichen so weiter und wenn einer von den beiden zu bevor der andere für zu Ende ist ist der kleinere der also der der kürzere der kleinere aber das kann man auch beliebig allgemein sehen es geht gehen wir zum Beispiel auch mit Datensätzen für Personen als 1. entscheidet der Nachname wenn der Nachnamen gleich sind entscheidet der Vorname wenn die Vornamen gleich sind entscheidet keine Ahnung was ja und genau in diesem Sinne das auch lexikografischer am in gewisser Weise ein Kriterium dann das nächste Kriterium wenn beide gleich wenn 2 Datensätze nach diesem Kriterium gleich sind dann das nächste Kriterium man sagt auch nach den gleich sind und das ist der und so weiter zeichnen im strengen Sinne Spezialfall allgemeinen Sicht und die Logik hier ist wenn 2 Kanten unterschiedliches Gewicht haben ist dass die Entscheidung welche von den beiden der anderen in der Sortierreihenfolge vorzuziehen ist wenn Sie welches Gewicht haben ist dass er die Entscheidung und das ist eindeutig ja da gibt es keine Gleichheit mehr einfacher Trick 7 was das bedeutet und Programmieren heißt sie ändern sich vielleicht an solche Sachen wie in Java die geht das in das ist klar aber die Telekom bald da kann sie das ja eine Möglichkeit um Vergleiche ganz generisch auszudrücken und das bedeutet dass sie in den kommt Alter wenn Sie da 2 Karten reinstecken dass sie eben nicht mehr einfach nur die beiden kosten werde dieser beiden Kanten miteinander vergleichen und dementsprechend minus 1 plus 1 oder 0 zurück geben sondern dass sie 1. kosten werde miteinander vergleichen wenn die unterschiedlich sind gehen Sie schon Minus also plus 1 zurück wenn wir gleich sind vergleichen Sie der beiden und geben es ein so plus ein zurück 0 kann die also Gleichheit kann nicht vorkommen weil das war der zweite die zweite Komponente jeweils unterschiedlich sind wir das ist ein allgemeiner Trick immer dann wenn es ein stört das kannten Gerichte gleiche Kosten er gleich sind oder allgemein und welche numerischen Werte gleich sind und bei Ablehnung statt eines öfters mal kann man auf die Art und Weise erzwingen oder auf die Art und Weise wie auf der Folie erzwingen dass man das meint dass sich paarweise in die Gesichter bitte das ist natürlich in gewisser Weise allen nichts zueinander das ist sozusagen in gewisser Weise ist das so kann man sich das so vorstellen als ein rede von Energie Doris Welter Mali ja das ist identisch wenn das der nur klein genug ist also so richtig unendlich klein sie so was meine da ja wenn das der der unendlich klein ist dann ist das dann ergibt das sie beide dieselbe Sortierreihenfolge das guter Hinweis gute Homers damit so ich glaube diese
Folie hat jetzt nicht zu den ganz großen Erkenntniswert die hat den Erkenntniswert werden sie wenn sie nebenbei noch in der Mathematiklehrer Veranstaltungen sowie Optimierung wir haben weil insbesondere gesagt wird dass diese Dualität hier zwischen zügeln und und schnitten er nicht wirklich duale Programme sind aber es hat sehr viel mit Dual in deren Programm zu tun Zügel und Schnitte sind auch in der Programmierung du als und und aber ist es nicht weiter sagen wir einfach diese Folie ist nicht in dieser Lehrveranstaltung Prüfungs- aller Art zum Protokoll dieser vor dir vor der 15 von dem aktuellen betrachteten Foliensatz diese Folie sehen Sie es auch nicht so
besonders aus kräftig mit wobei sind das an dass er mich an etwas anderes was aussagekräftig ist diejenigen von ihnen die bei mir geht's so gehört haben oder gewaschen motivierend letztes Semester sind dran gewöhnt dass ich da immer ein kleines Intermezzo gemacht habe mit logischen Fehlschlüssen das interessanter logischer Fehlschluss ist an den ich mich der an dem ich die Folie jetzt spontan ändert im Beirat im Reich des Placeboeffekts sie wissen lassen was ist also Sie geben zum Beispiel der Arzt gibt dem Patienten Zuckerpillen und wer trotzdem so gesund als aber die richtige Medizin bekommen hätte ist auch tatsächlich nachweisbar dass das physiologische Konsequenzen hat das wirklich gesund werden und sich dies nicht nur einbilden was uns immer hat eine ganze Menge ist boomende gemacht zum Beispiel hat man experimentierte mit roten und blauen Pillen und hat festgestellt dass bei roten der Placeboeffekt stärker wird das blauen Pillen dass das Abkommen nicht auf und hat auch festgestellt dass es vielleicht dann weniger raschen ist wer im die Probanden denken dass die Pillen teuer sind dann wird der Pass über für das als die Probanden denken dass die Pillen billiger sind noch ein interessantes Ergebnis ich letztens gelesen habe ist da gibt es ja Berufe wo die über den ganzen Tag unter Stress unterwegs und Sophie Krankenschwester und so weiter mehr und wenn man jetzt 2 Gruppen hat der einredet man ein diesen ganzen täglichen Stress die Bewegung ist gut fürs Abnehmen oder anderen redet man eine das hat das System aber man gar nix dann stellt man hinterher fest in einer Studie dass deren Durchschnittsgesichter sich tatsächlich verändert haben in der Reihenfolge eigentlich sollte man ja denken dass diejenige man gesagt hat ja das Abnehmen dadurch dass die sich dann eben Lenz machen sich noch an seine Tat mehr nehmen und so weiter und das mehr zu dem nicht aber es ist nicht so sondern das Ergebnis dieser Studie war dass die Gerichte sich tatsächlich zu sein als der 5 erfüllende Prophezeiung in die entsprechende Richtung geschickt haben vielleicht noch ein letzter Punkt dazu bevor in die Augen zu fallen er ich weiß nicht ob die mit wirklich kamen an der Universität Frankfurt Oder wurde vor ein paar Jahren ein Professor berufen für alternative Medizin es gab einen riesengroßen in den in den Medien alle möglichen Wissenschaftlernamen um Gottes Willen wie kann eine Universität Lehmann berufen der sich mit alternativer Medizin beschäftigt und so weiter und sofort Homöopathie Argument Druck und so weiter er war nach heißt der und ich haben wofür letztens von Ihnen gelesen was ganz interessante ist dahin gehend alle erstmal Überraschung er sagt Akupunktur mutet die und so weiter die ganze Erklärung dazu warum das funktioniert zwar scheint alles Humbug interessante also das sind erstmal hätte erst mal den ganzen Kritikern vielleicht den Wind aus den Segeln genommen das mal zugehört hätten aber was ändern was so was Interessantes bringt ist er bringt Beispiele von Studien und nicht wie üblich nur die medizinische Behandlung und das Placebo für 2 vorgenommen wird sondern der dritte Vergleichsgruppe die gar nicht bekommen wieder in das eben auch eine medizinische Behandlung des L einfach in Ruhe lassen würde und wo man dann hinterher feststellt der Unterschied zwischen diesen beiden Vergleichsgruppen Placebo oder gar nichts in der Wirksamkeit der Gesundheit der Gesundung ist viel größer als Unterschied zwischen was über und medizinische Behandlung so dass man zum ist in diesen Fällen davon ausgehen muss dass auch die medizinische Behandlung im Wesentlichen davon Placeboeffekt Brote oder stellt dann die nicht ganz so so dumme Frage ob es wirklich gerechtfertigt ist für teures Geld Medikamente mit vielen Nebenwirkungen vor aber reichen wenn man fast denselben Effekt hinkriegt mit einem billigen Placebo ohne Nebenwirkung wie zum Beispiel Homöopathie ja also Sie sehen die Situation Schulmedizin und alternativ Medizin das ist schon sehr viel sehr viel diffiziler als es in ihnen in den Medien typischerweise diskutiert wird so Schluss damit für heute wenn sie sich weitere logische Sachen ansehen wollen oder unlogische Sachen ansehen wollen kann ich Ihnen die Aufzeichnung von G 2 letztes Semester empfehlen da habe ich etliche Sachen etliche Knackpunkt der diese Art dann immer in dem Intermezzo ja auf der jeweils zum Besten geben so da habe ich das in Art
und erklärt es mit dieser Folie und wieder zurück zum Thema so blaue oder rote blaue oder rote na ja wir haben n Quadrat viele kannten ja in über 2 sehen das klar dass wir in über 2 viele kannten in dem Grafen haben können mit einem Knoten nämlich was eine kannte das ist 1 2 Elemente gibt wurde sie können eine ziehen mit ihren beiden N Knoten wie viele zweimalige Knoten hat man hat wie viele Zeilen wendige Teilmengen deckt dort Menge haben Sie genau das ist der Binomialkoeffizienten über K ist die Menge aller ist die Zahl aller keine mit dem Teilmengen Ende mit dem man also aber immer 2 und den über 2 ist im Wesentlichen im Quadrat ja sie ändern sich was in über 2 ist eigentlich comma dass es nicht das ist n x n plus 1 mehr ich hoffe ich habe da jetzt keine Aufbau einer gemacht so blauer Regel guckt sich genau dieser Karten an dieser einen zu bleiben aber in rote regeln alles rausschmeißen was nicht reingehört zur potenziell über im Quadrat das heißt also bei einem Grafen der wirklich sehr sehr vollständig ist also bei den wirklich die keinen Fall größer 7 Jahre ist ist die rote Wege immer schlechter als als allgemein basieren auf der Blauen regelt
gut wir wir gehen jetzt schnurstracks weiter das wär mal ganz ein bisschen vorwärtskommen hier wenn ich hier schon lange wenn ich hier schon laufend und welche anderen Sachen erzählen sie medizinische Sachen das ist der 1. Algorithmus für minimal Spannung wollen wir so weit wir wissen fängt genauso an wie WWE wie Prem nämlich wir haben am Anfang und Ende Knoten als triviale weder als einführen wollt und was er macht ist jetzt ein bisschen anders solange wir solange mir mehr als einem Baum haben also solange das noch kein Spanner bauen solange Summen zusammen dass mir zusammen es Kommunen verfällt nehmen wir jetzt nicht mehr wie bei Prem oder bei kurz Call 1 kann daher sondern für jedes Sammers Komponente nimmer uns eine könnte er nämlich die die kleinste die von dieser zusammen es Kommunen daraus reicht und die Blumen alle also geben der blau das Label und die blauen kannten diese rauskommen Formen die bilden eine 1 des aber das funktioniert natürlich nur mit Fahrer paarweise unterschiedlichen kannten Kosten stellen sich etwa vor mehr dieser Algorithmus gleichzeitig in einer Iteration werden mehrere kannten blau gefärbt ja wir haben jetzt die Situation eigentlich hätt ich das gar nicht wegwischen brauchen weil ich so im Wesentlichen dasselbe bitte gleich nochmals also wir haben 4. nicht Schnappschuss ja wir haben die Startschusses Algorithmus wir sind mitten drin wir haben diverse Zusammenhangs Komponenten können kann auch mal einzelne Knoten seine zusammen Komponenten oder einzelne kannten ja oder so was hier so dass die Schnappschusses Algorithmus und was wir jetzt machen ist von jeder zusammen es comma denn da aus D die kleinste die Karte mit dem gleichen Gewicht die irgendwo anders hingeht die für alle gleichzeitig ja okay gute stimmt schon sehr wohl und ganz recht sind voll und ganz recht daran habe ich gar nicht gedacht dass dieser Fall so mittendrin gar nicht mehr auftreten kann vor ja muss man sich immer klar gemacht haben ja ich meine die Erklärung sind weiter auf funktioniert aber so dass so haben natürlich noch mal ein bisschen mehr Verständnis erreicht man so jetzt stellen Sie sich vor es gibt keine paarweise verschiedene kann Gerichte sondern es gibt durchaus kann mit gleichem Gewicht zum Beispiel die billigste kannte hier von hier nach hier macht dass man den Fall weil von hier aus Schlange die Brücke hin hat Gewicht 357 ist die billigste würde die noch nicht betrachtet die hieraus komischerweise gibt es noch eine Kante mit Gewicht 357 nämlich die hier auf und die hier und die hier und die hier die haben alle kannten Gericht 357 sind irgendwie zufällig gewählt worden und siehe da es geht schief das geht natürlich nur dann hilft wenn tatsächlich gleiches Gewicht das den wenn beispielsweise diese Wortwahl 2 Kanten unterschiedliches Gewicht hätten es jetzt die Argumentation also es kann sich keinen Zügel bilden wie es diesen das weil also wenn die beiden unterschiedliches Gewicht haben dann kann es immer noch sein dass die beiden genommen worden wären aber zum Beispiel aber der hier vom anders ist E 1 E 2 E 3 E 4 und er 5 so da muss aber 2 das Gewicht von E 2 größer als das Gewicht von E 1 gewesen sein sonst wäre vor von dieser Karte aus der Totenstadt er nach da gegangen sein er kleiner nicht so selber Argumentation hier das Gewicht von 3 muss kleiner als das Gewicht es ist ein kleiner Zeichen sein also das Gewicht von je 2 gewesen sein und so weiter und so fort und wenn sich der sie beschließt comma einen Widerspruch ja sie können nicht zyklisch eine echt kleiner Relation haben und das funktioniert das mit Fahrweise unterschiedlichen kannten richten ja also wenn Sie parallel auf gute das ein schönes Beispiel wenn sie paarweise unterschiedliche kann Gerichte haben können Sie machen parallel machen diese sonst machen müssten das ist eigentlich der Quintessenz was so das sinnvoll ein paarweise unterschieden Gewichtes weil sie wissen dass die Entscheidung von beiden Seiten gleich getroffen zum ist hier Züge frei getroffen so sonst können Züge auftreten sollen am Beispiel gesehen ja fast so schwer zur okay das ist dass die feinen Orden auf welches Aufsehen Welt das ist das was ich hier angegeben habe dass offensichtlich gemeint dass man eine Ordnung angeht indem man die auf Ordnung einfach mit Gewalt einsetzt also wenn 2 kein Ungleichgewicht haben dass man sagt die Kante mit kleinerer auch kleinere Positionen der Ordnung ist dann die kleinerer kannten damals natürlich auch viel aufgelöst ja wiesen und gerichtet dass
sich hier die Pfeile gemacht Pfeiler heißt ich schlage von hier die Brücke nach da die Karte so eingerichtet aber die Richtung von der ich die Karte ziehe das das diese man die dieses falls ich hoffe das klar gewonnen Unterschied wir kommen schon rechtzeitig zu den gerichteten Fall der noch Kopfschmerzen machen vielleicht noch weiter vielleicht sollten wir Heft aber erst bitte die Hälfte der Zeit aber doch es ist genau an wie kriegen wir das so das ist ein Beispiel dafür war das will ich jetzt nicht durchgehen das können sich noch einmal um ihre eigenes ernst überprüfen sich noch mal dann im stillen Kämmerlein ansehen ich habe der den ich habe er die Problematik hier vorgeführt und dann können sie noch so schwer sei bewusst auch ich dass ich das nicht nur ein selbst nachvollziehen kann
Oskar können wir ganz schnell durch den Sie kennen
Algorithmus von Großkreise wir sollten Sie kennen das ist wir sortieren die Kanten in aufsteigender Reihenfolge und was sie kennen ist das was hier unten also gehen Sie nur ruhig immer Bescheid wenn die wir nicht vergessen die Tage unter unterzuschieben sie nicht lesen können er was sie kennen ist diese Formulierung hier unten aus der wir die 2 für jede Kante in dieser so aufsteigenden Reihenfolge machen wir waren falls der falls falls sie erheblichen Zunahme der kannte keine zu beschließen dann für die kann den Suns dass man in der Karte mehr vergessen sie dass sie wolle dieser Serie so kennen kann man auch anders umformulieren nach in unserem Schema falls die beiden entlud selben Baum sind dann ist die Karte rot weil wir sonst zu beschließen würden wir dir einen sonst werden wir die Kanther blau und in sie hinein so und das Ergebnis die Blauen Karten sind wie üblich der Minimal Spanne Baum Kuss
gleichsam Kuska Beispiel worum es nun wirklich nicht durch
zu gehen das kennen Sie das gehe ich mal davon aus wie wir es groß können macht das selbe jetzt gesagt in grün sie kennen den Spruch dass Erwin Grün aber in Wirklichkeit ist ja selben rot wir drehen die Reihenfolge auf von allen kannten und und wenn wir fangen an mit einem kannten im Baum es natürlich dann kein Baum mehr und wann immer wir feststellen dass eine Kante wenn wir die wegnehmen dass der es immer noch zusammenhängt ist dann werden wir die Kante um von blau auf Rot Forst am Anfang haben wir so blau gefärbt es werden also und nennt sich duales groß gar
so Komplexität Kursker sortieren kennen Sie lockern wenn wir unsere Karten weil wir keinen sortieren testen der Züge der der Züge ich weiß nicht ob sie alle also bei mir in der geht zur letzten Semester haben wir die Datenstrukturen betrachtet mit denen wir testen können effizientesten können ob eine kann den Zügel schließt oder nicht ich weiß nicht ob in früheren Semestern das auch betrachtet worden ist Stichwort Seljunin fallend okay dass man auch nur ganz kurz ja bitte also sie wollten ich das nicht so ein so was müssen wir tun für jede Korb für jeden Knoten pro wir brauchen einer Datenstruktur die uns für jeden Knoten zurück in welcher Zusammenhangs Komponente will sie diese Bilder dieser Knoten gehört momentan also Songs von Kommunen haben über Identifikation und unter Umständen müsse Zusammenhangs Kommunen war schon vor einigen zu jener seit Juni in das Abi und den Feind dieser Test ist das vereint das Juni an deshalb habe ich das der G 2 auch in Franken an unsere Sonne Literatur genannt so hier ist ein Gag dabei die nicht auch in Linie in der AG 2 besprochen hatte aber Sie haben ja nicht alle bei mir gehört so worum geht es das Problem beim Algorithmus von Kuss Calvo die Laufzeit ein echtes Problem wird ist wir haben ein Schnappschuss ja Sie haben ein paar einsamer Knoten noch sie haben vielleicht ein paar einsame kannten sie haben kompliziertere Strukturen so um so vielleicht irgendwie und jetzt gibt es 2 Möglichkeiten wenn sie die nächste kann der betrachten eine Möglichkeit ist sie schließt einen Züge so wie diese kann wenn das in ist es die sie in der Reihenfolge brachten zweite Möglichkeit ist sie schließen keinen Züge was heißt das in dem Fall die beiden Entwürfen so sein Zusammenhangs Komponente und dem Fall gehören sie zu unterschiedlich zusammen Komponenten so was Sie brauchen ist eine Datenstruktur die solche zusammen es comma netten strikt voneinander getrennt verwaltet und und die 1 2 Möglichkeiten bietet 1. mal Zusagen für jeden Quoten für den Knoten vor diesen Knoten weg seid ihr beiden Hunden derselben Zusammenhangs Kommunen oder nicht hier ja nein hier die Antwort 1 die Antwort ja und natürlich dann wenn wir uns dazu entschließen diese kann einzufügen hier diese beiden zusammen Komponenten zu vereinigen zu einer also aus 2 Listen von von Knoten und Kanten eine zu machen und der Gag der jetzt hier steht ob es musste komponiert Osttimors versendete komponiert Auflage das heißt das bedeutet das war die Situation vor ja bevor wir jetzt diese Kante betrachtet haben wenn ich jetzt feststelle diese beiden die ich für diese kannte einen vor einige diese beiden Zusammenhangs Kommunen zu einer dann ziehe ich durch wie viele Knoten habe ich hier 1 2 3 4 5 6 7 wie viele Knoten habe ich hier ja nur 6 und ich hänge die kleinerer an die größere als Zusammenhangs Kommunen ich muss bei der kleine bei diesen 6 Knoten muss sich alles um alles umorganisieren mir zu merken dass das jetzt nicht mehr die CD zusammen aus Komponente Nummer 3 Tausend 768 ist sondern Nummer 2157 hier bei diesen 6 Knoten muss ich ne Menge umorganisieren wenn ich hier hängen bei diesen sind Club muss ich gar nicht zum organisieren der Gag daran ist jedes Mal wenn sie dass Google sich oben Knoten an zum Beispiel den Jahr jedes Mal wenn sie den umorganisieren müssen den anfassen müssen um um die zusammen es kommenden zu vereinigen mehr 6 plus 7 bis 13 und das ist größer gleich zweimal in dieser Zeit nichts die zusammen es comma der in der in dieser Knoten drin ist nach ich angefasst haben wächst die um mindestens Faktor 2 durch diesen Trick dass sich die kleine eine größere Menge und nicht umgekehrt jedes Mal wenn ich diesen Knoten oder irgendeinen Knoten an Verse sexy Zusammenhangs comma um Faktor 2 also nach zweimal um mindestens Faktor 4 Nacht 3 dreimal mindestens Faktor 8 und so weit und sofort wie hoch kann er seinen na ja höchstens an verknoten das heißt wie oft kann mir das passieren dass ich diesen Code anfassen können zweier Logarithmus Anzahl Knoten wenn wir aufgerundet und so was ja öfter kann mir das gar nicht passieren dass ich diesen können Anweisungen und zuordnen und wenn ich das für jeden Knoten habe und dann kommt so was Schönes wieder raus so schön bekannt ist das ist der Gag auf dem dass sie anspielt ich glaube Hersteller hat das ein bisschen weiter ausgeführt genau ist mir stimmte komponiert auf liest weiß dass alles zweimal die größte tut heimst war im Englischen das heißt jeder Knoten muss 0 logarithmisch oft angefasst werden und insgesamt kriege n raus das ist natürlich gerne zusammenge- Grafen da es Diknu bekannten Zahl also methodisch mindestens so groß wie Knoten Zahl ist das also auch in diesem Lock-in drin was uns sowieso schon eingehandelt gehandelt haben sortieren da hat also aber immer so das ist das ist nur der Hinweis auf die Literatur jungen vereint Datenstrukturen gibt es mit also methodisch Komplexitäten also was ich Ihnen jetzt gezielt hatte es lockern er gibt es mit also methodisch und Komplexitäten die viel viel näher dran sind an Genialität als nur einen Ort die Implementation also wie die Datenstruktur funktioniert es gar nicht mal so kompliziert aber die Beweise für die Laufzeit sind abartig also Laufzeit selber als abartig falls es Sie interessiert dann schauen Sie was die Laufzeit ist das schaut er er die Laufzeit ist was wie mal 1 vor von allen und vor das finden Sie unter dem Stichwort inverse Ackermannfunktion wenn Sie irgendwas perverses aus theoretischen formatik mal sehen wollen sich die inverse das Ackermannfunktion aus keine Aussage den Herrn Ackermann der wir diesen Herrn Ackermann oder noch über überwiegend ein an und Herrn Ackermann so weiter Komplexität
also allen hat ihm festgestellt ist müssen so groß wie also methodisch hier noch mal interessanter Punkt dabei wie möglich und so weiter es kleiner in Quadrate können wir können diesen quadratisch groß sollen das heißt mit rücken Gesetzen ich hier hier wenn ich an dass der Logarithmus streng monoton wachsend ist hier wenn nicht Logarithmen Gesetz an funktional gleichen des Logarithmus im im einfach bezahle und hier bin ich und Notation an das heißt also interessanterweise obwohl die keinen sind muss man sich immer klar und obwohl die kann seine Garage ist mehr Knoten Zahl ist der Logarithmus der selber also also tun Wachstum das heißt also wir eben gesagt er ist alles unter einem Block wir noch Look schreiben können alles ist so Brem das
ist in der also muss von Print ist wenn sie da dagegen gelernt haben es in dieser historisch gewachsen genauso wie Amerika nicht nach Kolumbus benannt ist sondern auch ein eigenes Boot der so und so vielte der Amerika entdeckt hat nicht der 1. aber meinen glaube ich der Erste der der sich klar gemacht hat dass es Amerika entdeckt hat also sehen gute Ideen comma öfters mal wieder vor zumindest bei mir nach ich hatte Prellungen parallel zu da Extras Algorithmus für Christel Wege eingeführt und so war das Dextrose auch gemacht weil die beiden Algorithmen sehr sehr ähnlich sind in ihrer Vorgehensweise und in in ihrem beweisen also den Beweis der Korrektheit können kennen Sie comma nicht weiter durch zu gehen was macht treffen sie haben wir am 1 wachsende Zusammenhangs Kommunen da wo sie immer von dieser zusammen es kommen und daraus ist dieser zusammen uns Komponente woanders in eine Kante hinzufügen aber das ist hier so funkt formuliert ist das die anderen Knoten sie bis jetzt da noch nicht diese Songs Komponente haben eben blaue triviale Bäume sind die aus ist keiner kann und einen Knoten stehen Brandt Robin
da steht hier daran werden ist ein allgemeines Prinzip in der Informatik finden Sie bei Betriebssystemen beispielsweise beim Multitasking oder so dass sie dass sie immer wenn sie verschiedene wenn sie ein völlig verschiedener Akteure jeweils Aufgabe zu erfüllen haben dass sie immer der Reihe nach zyklisch durch den mehr ist das nicht keine Ahnung woher der Name kommt ich glaube mein Studium als mir mal umgeben und nur 10 gesagt ob ich es wieder vergessen aber steht bestimmen Sie die Bilder wenn da steht das ist der effizienteste Algorithmus dann ist das natürlich eher eine empirische Erfahrung als etwas was man mathematisch ableiten kann so wir fangen wieder an mit mit dem leeren Baum wäre Kantenlänge was machen wir hier bitte muss man hier endlich solange wir also noch nicht fertig sind wenn wir irgendeinen Baum wie bei Bremen das bei Primal derselbe ist und hängen dann erkannte an Unternehmen wie der nächsten Wochen wie der nächsten Baum und so weiter also Surrey um die also stellen sich vor Sie haben eine Liste der von Zusammenhangs Komponenten des langsam wachsenden weil es und an und sie dem vorne 1 1 1 zusammen was kommen dann doch aus hängt Kante an und packen das was Sie daraus Geschichten wieder hinten das ist ist dran aus irgendwelchen Gründen ist das funktioniert das empirisch besonders gut beziehungsweise ich hätte jetzt gesagt dass mathematisch nicht keine mathematische Begründung hat hat doch auf die wir nicht eingehen werden also meine Marsch Erklärung dafür wenn wir nicht Raum drauf eigentlich nicht trauen Sorgen machen nämlich immer streng in der Reihenfolge wer zuerst wer zuerst also jeder der fertiggestellt wieder hinten an sondern wenn wir so etwas anderes machen das immer einen Baum nehmen mit der kleinsten Anzahl von Knoten also das für die dieses zu sortiert halten dann kann man beweisen machen wir nicht das wär besser sind als er noch genehmigt ist indes klar das locker gehen was dramatisch besser es ist als lockern sowie N dramatisch besser als n ist es laut wird er mal dramatisch besser als Flop also lag schon dramatisch gut das heißt also locker gellendes Maler sind der praktisch schon linear in die Enge im Rahmen dieses Universums tschüss so darauf will ich jetzt
hier nicht weiter an den Laufzeiten das ist das ist was mal was mal irgendjemand auf das Baxter Herrchens nur so 95 mal gemacht hat sie sehen so komische kleine Zahlen vor wurden von Megahertz und Megaflops Flops und so weiter okay 2009 Wiederholung des ganzen so schon mal deutlich die intuitive zahlen gelber zahlen genau solche Tests haben natürlich nur bedingte Aussagekraft werden vor allem wenn es nicht dabei steht was das für Instanzen waren ja was das für Beispiele waren ja Sie können sich natürlich vorstellen allen Algorithmus die die die Primm dass der auf auf Beispielen die die und wie ja er hat dem wie wie die Beispiele gebaut sind ob das jetzt Straßenverkehrsnetzes sind oder oder komplex ineinandergeschachtelt aber was auch immer das ist natürlich er Effekte auf die empirische Laufzeit hat er auf die theoretisch Laufzeit also deutsche Komplexität natürlich nicht hinter sich auf über SGIs Komplexität aber auf die empirische Laufzeit natürlich schon insofern sind solche Tests nur bedingt aussagekräftig aber sie sehen schon dass das Verhalten wenn Sie sich mal hier würde vergleichen Hosen bei denen 4 und das Songs für Algorithmen wie geht der von 10. 20 Tausend wurden verdoppeln die die könnten Sorge und gut da steht natürlich nochmal der Logarithmus drauf dass es nicht proportional das zu dem es sich hier um als verdoppelt hier aber natürlich mehr als nur verdoppelt
gut können Sie sich ausdrucken und an die Wand hängen klar von von wäre nicht schlecht wenn man es erreichen würde Verifikation das heißt in der festgestellt ist tatsächlich der der spannen Baumes geht tatsächlich in den ja zu alt dafür zu bieten Arbeit die zweitgenannte Monika Rauch war übrigens mal zwischenzeitlich noch nicht so lange her Forschungschefin von Google aber das war noch vor der Zeit davor war sie Algorithmik gehören so Kanal Grafen also was ist das Sie randomisiert das heißt im Erwartungswert dass der Wartungs- wert dafür dafür wie viel Zeit man braucht ist linear abschätzbar und es gibt auch Algorithmen mit denen man das mit dem man dem Beispiel der worden und dann an der Hafen derzeit schaffen kann und das letzte was er steht die das Vergessen Sie vielleicht irgendwann einmal was das Modell was dahintersteht ist das wie so viele Prozessoren haben diese Klonen könnten haben das ist rein theoretisches Modell offensichtlich und in diesem rein Modelle schaffen sie tatsächlich den Aufwand auf Logarithmen ist und einer und noch N oder in vor als Faktor zu drücken bitte ja also das Modell sehr theoretisch das Wort Signallaufzeit hat da keine Bedeutung das das schmeißen wir raus' 1
bei mir schmeißen wir heraus genau und wir wollen nicht weiter
ich habe mich extra noch nochmal vergewissert dass
1 mehr wie bin ich denn jetzt hier das
einst Bäume nicht in den Übungsaufgaben vorkommen also können wir das Rauschen wie jetzt
comma endlich mal weg von der G 2 ist comma was neuen war schön ist gewichtet erfahren also so was ähnliches wie ungerichtete minimal Spanne beim oder maximal schwanden Bäume ja jetzt Branching zahmer gesehen dass das ist ein Brand schien das heißt im Prinzip wird glaube ich noch mal irgendwo noch definiert wenn die muss ich das genau das den Rekord was ist ein Braun Schenk das ist eine Kantenlänge gewesen gerichteten Fall so das so dass diese so dass die diese Karten meiner keine Züge enthält und in jeden einzelnen Knoten gibt maximal ein kann rein das ist nicht unbedingt ein Baum wie sehen aus der GD 2 kennen gelernt haben wie Suchbaum oder oder so etwas denn ist sondern etwas was potenziell in mehrere solche Bäume zerfallen kann nämlich habe das hier zum Beispiel ein wenn ich jetzt noch so was dann dem Zeichen irgendwie also ich bin jetzt hier müssen einfallslos sieht jetzt sehr ähnlich aus dann ist das zusammen immer noch im Branching und wenn ich jetzt noch so was daneben zeichne und vielleicht so die und vielleicht das noch dann ist das alles zusammen was einer ist dafür steht immer noch ein paar schicke bestehend aus aber Essenzen jedes ein von den ist eine aber es Trends versah keiner haben Sie vielleicht für sie zu merken aber es nur für Teile der Baum so was muss der Lateinunterricht auch nutzte seine so zum Thema Lateinunterricht und und nutzen einer der Bildungsforscherin namens er einen Exploit Stern die damals Direktor des Max-Planck-Instituts für Bildungsforschung in Berlin war hat man eine Studie durchgeführt ob Lateinunterricht tatsächlich ein Nutzen hat im Hinblick auf Intelligenz Intellektuelle K Fähigkeiten also Übertragbarkeit auf auf andere Kontexte außerhalb des Lateinunterrichts und was sie rausgekriegt hat war in ihrer großangelegten Studie wenn man noch die sozialen Hintergrunds herausrechnet offensichtlich gibt es an unterschiedlichen sozialen Hintergrund in der Tendenz zwischen Schülern die Dateien als Fach und Schülern die sich haben wenn man den sozialen Hintergrund rausrechnet bleibt eigentlich keine Ergebnisse mehr übrig das heißt das war die Lateiner hatten wer ist in vielerlei Hinsicht besser später abschneiden lässt sich vollständig aus dem sozialen Hintergrund erklären ohne ohne weitere Erklärung dafür dass Latein und irgendwie das Denken Schuld oder so etwas denken Sie mal darüber nach im Zusammenhang mit anderen mit anderen Gebieten denn man das ja auch nach sagt Schach Mathematik und so weiter in so zurück das ist ein Brand stehen und was wir wollen ist ein maximales minimales Page mache keinen Sinn bei positiven kann gewichten das manches mehr okay so was ist das Problem wir haben so eingerichteten Grafen die Graf sehen sich damit etwa auf mit kann Gerichten und die sondern Branching eine Teilmenge der Kanten die an solche waren hin geben mit maximalen Gesamtsumme des Gerichts
so jetzt haben wir die 1. Idee und sowieso sich ein führt hier ist es natürlich schlechte Idee aber so sehr auch nicht Idee eines dabei stehen sondern die Idee würde das stehen so etwas muss doch mal wie groß wir sortieren die Kanten nach absteigendem Gericht und kucken fügen kannten ein jeder kannte die wir betrachten fügen wir ein wähnen das Ergebnis weiter Handling ist also wenn ok wenn wieder Anzüge geschlossen wird noch werden wenn dann plötzlich 2 kann noch dieselben Knoten zeigen und wenn wenn es keine Wahnsinn mir wirklich ein führender könnten dann das Mitte kann dann vergessen sie wieder so wenn wir das machen das ist
jetzt ein kleines Gegenbeispiel das ist natürlich nicht funktionieren kann wir wissen doch inzwischen warum es nicht funktionieren kann weil es keine Madrid ist als keine Madrid Struktur hat das können Sie gerne nachprüfen im stillen Kämmerlein dass es keine Madrid Struktur hat vielleicht kann muss auch während der mündlichen Prüfung thematisieren auch an allen Spiegel in Aufmerksamkeit so was würde jetzt groß machen aber erst mal die Kante einfügen und die einzige weil die schweres Gewicht ist und die einzige kannte die eingeführt werden kann ist die denn wieder die Kante die sowohl die nachdem wir diese Karte eingefügt haben die mit dem 3 man sich 3 sowohl die Karte von 0 bis 1 also die Karte von 2 bis 3 kann man nicht mehr einfügen weil die würde dann die Branching Eigenschaft kaputtmachen also halt ne als die von 2 bis 3 bis nicht kaputtmachen aber die von 0 bis 1 auf jeden Fall wir haben die Wahl entweder die kann von 1 bis 2 oder die von kann von 2 bis 3 noch einzufügen eine von den beiden nur hier ist entschieden worden die Kante von 1 bis 2 einzufügen und danach geht nichts mehr was aber natürlich viel besser was ergeben dass er vieles ist übertrieben aber was das Ergebnis liefert ist wenn ich die 3 2 nennen und die schwere kannte einfach vergessen war dann krieche noch mehr raus also es ist ganz die Idee eines ist keine gute Idee wir so soll so mehr anstrengen wir werden uns noch mehr anstrengen so ja gut das ist
das ist der derjenige der sich für uns angestrengt hat Jack Erdmanns ich weiß nicht ob er noch lebt auf jeden Fall ist es sicherlich garantiert schon in Pension
das Bild es auch glaube ich schon älter also sehr als ich in den neunziger Jahren gesehen habe es auch schon so aus
so was nicht funktioniert ist dieses Krimis jetzige Entscheidung treffen und nie wieder rückgängig machen es gibt 2 Möglichkeiten wie man das Vorgehen kann die eine Möglichkeit ist Entscheidung treffen später doch wieder möglich machen gar keine Entscheidung treffen ist natürlich auch eine Möglichkeit danke für den Hinweis aber nicht so richtig zielführend er nicht okay die andere die zweite Möglichkeit die zielführend ist wäre die Entscheidung so weit wie möglich aufzuschieben so lange bis wir wissen wie die Entscheidung sein sollte und das ist das was hier gemacht wird wir verschieben kritische Entscheidungen so lange machen Sie es dann treffen sie erst dann irreversibel wählen wenn wir wissen was wir tun gut wir weil wir ja um zu wissen was sie tun transformierende dieses ursprüngliche Problem in eine Serie von einfache Teil Problemen die die wir durch schrittweise Reduktion des Grafen hinkriegen kann keine Sorge dass das wird alles klar was der Fall ist da kommt der schöne bunte Bilder würde 2 ok die Frage ob das dann nicht auch ist wenn wenn Entscheidung treffen der später aber nicht wieder zurücknehmen es ist nicht das was wir normalerweise unter greedy bezeichnen oder oder die wirklich kurzsichtig also oft übersetzt man deutscher plädiere mit kurzsichtig auf ob er kurzsichtig sofort Entscheidung treffen gut dass ich das nicht will comma stand da kommt jetzt wieder Khedira rein da können wir jetzt wieder richtig regelmäßig Vorgehen kurzsichtig das Beste tun das was am besten aussieht und daraus dann für das Original Problem eine Lösung zusammenbrauen keine Sorge wird heute noch klar auch wenn wir nur für die schöne Zeit haben wir wenn ich in allen Details mir kommen heute denke ich aber was das bedeutet denke ich wird auf jeden Fall klar so wir
brauchen ganz kleines bisschen Terminologie nur und das ist mit zu also ich erkannte habe haben das ist die Kante Idee das ist dieser Knoten es von den Start das ist das Ziel Tal wird von E und das Gericht es wie üblich C von LG mehr besagt diese Terminologie hier nicht das reicht uns auch schon jetzt völlig um Feuer zu gehen das interessiert uns ist nur dann nicht so kritische Grafen
das Ganze mit sämtlichen wurden kannten ist als eine Eingabe das Essen gerichteter Graph mit Kanten Gerichten wurde die hier wie üblich einen kannten abgetragen sind und wir wollen hier ein maximales Bahnschienen finden und was uns dabei interessierten wir werden gleich sehen warum uns interessiert sind kritische Grafen Was ist ein kritischer Graf ich will's zuerst an diesem Beispiel versuchen zu erklären bevor er auf der nächsten Folie eine formale Definition kennen lernen also der kritische Graf ergibt sich aus den Gefährten den blau und dem grün gefärbten kannten ja nur blau und grün gefärbt so weit ist er ja und zwar warum ist die Kante von 4 nach 3 in diesem kritischen draußen drinnen weil sie Gewicht 6 hat und alle anderen könnten den 3 Reihen gehen das ist noch die 5 hat kleiner das Gewicht warum sie kann davon 4 der 6 trennen und sie hat Gewicht sie 7 und alle sonstigen kannten die nie 6 reingehen die fiel die von von 3 von 0 ja das wars auch schon die haben kleineres Gewicht ja das ist die Logik bei 5 nehme die kann davon 6 nach 5 die hat Gewicht 4 es sowieso die einzige kandidieren Zeit also das ist mit Sicherheit auch die schwerste kannte hier sehen Sie bei 0 und 1 die kannte die von nur noch 1 geht hat das schwerste Gewicht von allen kann die nur reingehen und die kann der wie von und nach 1 1 die von den formuliert habe ich einen Vorschlag die von nur noch 1 geht hat was ist das Gewicht von Ali 1 reingehen hier sehen Sie das sondern kann grau gezeichnet anstelle der Grünen kann davon nur noch 2 mit Gewicht 3 hätten wir natürlich auch die die Kante mit dem Gewicht von etwas vornehmen können aber die nur einer von beiden nicht 2 so um das sind so will so ist der kritische Graf definiert ist vielleicht noch mal ganz genau was das heißt was
ist ein kritische könnte Was ist ein kritischer Graf Mitglied der Soko auf wir haben ein Gericht den Grafen sowie eben das ganze Bild 1 gerechtere traf mit Kanten richten ja also kritischerer also unten gerichteter Graph mit
Kanten richten und Kante ist
kritisch wenn Sie in dem Beispiel gefärbt ist nämlich wenn Sie überhaupt dass mal positives Gewicht hat weil kannten mit negativen oder Gewicht oder Gewicht gleich 0 kann man auch rausschmeißen offen von vorne weg bei dem maximalen 9 schenkt wenn man es sowieso nie einfügen und es gilt für alle kannten hier komme jetzt diese Terminologie hinein nochmal für alle kannten die derselben denselben Ziel Knoten haben unter allen könnten diesem Ziel Knoten haben ist das eine schwerste genau so habe eben diesen Grafen konstruiert ja immer noch
mal den Knoten 3 Herr von allen kannten die rein zeigen in die 3 habe ich die Karte von 4 bis zu 5 4 zu 3 genommen mit Gewicht 6 war das das größte Gewicht ist und hier wie gesagt hat mir die Auswahl von nur noch 2 davon 1 noch 2 damals für einen von beiden entschieden die von nur noch 2 so ein
sub Graf als kritisch werden wenn es muss Kritik kann wenn er nur aus kritischen kannten besteht werden in jedem Knoten nur höchstens eine dieser Karten rein geht das ist das was wir hier hatten mit
den mit der Auswahl kannte von 0 bis 2 oder von 1 bis 2 das wir ein von beiden sehen kann aber nicht beide das war die zweite ist dass die zweite Bedingung die wir jetzt hier haben
er will nur dass man dort davon muss man auf diese Art des und 3. H dieser Krise der ist nur dann kritisch nennen wir dann kritisch wenn wir ihn nicht aus den können wir der maximaler Inklusions maximal sie können keine weitere kannte hinzunehmen sehen das ist noch ein Beispiel an ja es gibt ja noch ein
vakanten hier drin die Idee schwarzen dünnen beginnt gezeichneten kannten aber egal welche sich anschauen sie können keine mehr hinzunehmen ohne dass sie die Bedingungen verletzen das die schwerste kannte reingeht und das auch nur eine Kante immer in den Fluten geht also wenn überhaupt nur kann da geht dann ist es eine der schwersten und mehr als 1 geht nicht ein egal welche der der den den schwarzen kann sie reinigen diese Eigenschaften sind verletzt das Inklusion maximal
sie können sie können nix Kursus haben was das jetzt inkludiert also bisher hatten so warum interessiert uns das zunächst einmal
interessiert es uns wegen dieses was wär doch den Beweis heute nicht zu sprechen kommen sollte versuchen ihnen das große Bild erstmal mal zu geben der Beweis auffordern bis mehr als die 3 Zeilen an als so aussieht mit diesen Draht sein er ein wenn sie einen kritischen Grafen haben und der zufällig auch noch Artikel statt keine Züge dann ist maximales Braunsche dann haben damals schon das war schon fertig das so dass die gute Nachricht die schlechte Nachricht ist schon so auf das Beispiel zurück da ist ein
Zügel und da ist ein Zühlke die schlechte Nachricht im allgemein kriege keine kritischen Grafen hin der Züge frei ist aber immerhin schon ein Anfang das ist mir
auch was uns ärgert was wir womit wir umgehen müssen nämlich Züge kritischen trafen weil es keine Züge gibt es immer schon fertig Beweise wie gesagt ist das war so ich habe mir einen Fahrplan gemacht wo es jetzt weitergehen sollen weil wir nämlich einige Punkte hier
überspringen ich will das Folie 48 weiter da das
muss aber heute nicht machen weil sie die Beweise reichen
geht das heißt ich gehe jetzt bis vor 50 weiter das was ich überspringe ist wie
üblich wenn ich hier kommen wir schon mal einen andern Stelle komplizierte Weise das bedeutet sie können auch über n 1 0 bei mir kriegen in der mündlichen Prüfung oder sich diese Teile überhaupt anzuschauen sofern sie eben das nachvollziehen können was ich hier sage aber wenn Sie sich die Sachen anschauen und mir plausibel rüberbringen können dass das so aussehen muss wenn man so die formal beweist ist dann sind sie schon auch ziemlich weit auf der Straße zu 1 comma decimal 0 so darf vor der 50 da genau ein Schritt weiter der
Zusammenhang ist noch interessanter wenn wir diesen kritischen wenn einen kritischen Grafen haben gibt es einen gibt es einen Brand schenke der mir diese Eigenschaft hat dich anders formulieren will das was hier stehe bedeutet nichts anderes wenn ich einen kritischen Grafen habe dann komme ich zu einem maximalen Bran Schenk in dem ich geschickt aus eben Züge in diesen kritischen trafen ist geschickt ausgewählt eine kann daraus das das was in diesen Theorien stellt etwas anders formuliert war steht hier es gibt wenn ich ein kritischen Grafen habe sie haben eingerichtet haben gesehen dann gibt es einen wahren schön von maximalen Gewicht so dass sie eben jeder Züge die Eigenschaft hat das hätte ohne das dran stehen 1 ist das heißt also nur eine kann Züge sich überraschend wenn das kommt muss noch mal an dem Beispiel von nebenan also
Kommando zurück da wir die
kann wie gesagt die grün und blau gefärbten Kanten bilden das Paar bilden den kritischen trafen und die Auswahl dieses des Orients ist ich muss nur nur in Anführungszeichen aus jeden dieser beiden Züge die hier drin sind um 0 und 1 und der unten 6 5 4 6 aus eben dieser beiden zügeln muss sich nur eine schlau gewählte kann daraus nehmen und das Ergebnisse maximal Bahn stehen das hat dieses Theorien deshalb beschäftigen wir uns mit kritischen trafen das habe sie kritische Grafen intressant so wie man das jetzt mit den Zügen des Problemes jetzt hier an dieser Stelle wir können diese Entscheidung nicht regelmäßig treffen an dieser Stelle wissen wir nicht welche kann wer ich keine der außen auf herausnehmen müssen um um ein maximales Bahnschienen zu kriegen das
wird gehen wir dann noch ein bisschen weiter geht der geht
wohin muss ich gehen jetzt so Folie
52 habe ich mir notiert dar das nochmal die kritischen Züge das Beste von eben er hier nochmal um eine Überschrift notiert welches die beiden britischen zügeln sind und was machen wir
jetzt da gehe ich auch wieder zu dem Bild überspringen weil erst mal diese ganzen Sachen
das Bild ist das entscheidende was wir machen ist das übliche was ein störte schmeißen heraus ja das kann sie vom Privatleben da ich es nicht ich lasse mich nicht auf fest liegt dass es gemeint habe der wir ersetzen diesen Cykel hier zum Beispiel Zügel 1 3 4 1 1 4 3 1. Züge ersetzen wir durch sollen 9 Knoten den wir sie einzeln Forum der soll ist und diesen anderen Züge hier 2 und 0 ersetzten wir durch einen anderen Knoten diese kritischen Züge und haben den Grafen dadurch vereinfacht die Struktur ein bisschen einfacher geworden bisschen erst einmal also in diesem Beispiel sehr einfach geworden aber mal gemeint ist es einfach sagt eine Wortmeldung warum die Karte an Gewicht verloren hat gut das gute Beobachtung weil das so zum Algorithmus gehört das würde ich beim nächsten Mal noch mal genauer sagen oder vielleicht kann ich das ganz kurz andeuten nehmen Sie sich diesen kritischen Züge R 1 3 1 4 3 er endgültigen Branching gibt es 2 Möglichkeiten entweder die Kante von 2 nach 1 gehört zum manchen dazu oder die Karte von zu einer 1 gehört nicht dazu ja also entscheiden sie über die könnten die Züge Zeiten weil da Dame die Bedingung es dürfen es dürfen keine 2 Kanten gleichzeitig eine sind wo wir sein so jetzt gucken wir das an was du was in jedem der beiden Fehler passiert wenn die kann von 2 noch ein nicht reingehört was machen wir dann als als bestes was kann wir als bestes machen und so macht so kommen die kann mit kleinstmögliche rauszuschmeißen das heißt also von 1 4 3 Gehalt ins spanischen dazu diese Kante mit Gewicht 6 und diese Kante mit Gewicht 5 ja und diese kann dann rausgeschmissen das das Beste was man machen können wenn diese wenn diese wenn wir diese Züge für sich isoliert betrachten können wenn wir aber die Situation haben dass diese Kante von 2 nach 3 zum Branching gehört dann können wir das nicht so machen ich sollte hier dass die 5 nicht um klingeln weiß nämlich keine Knoten Name ist sondern das kann Gericht dann kann man es nicht machen kann man diese kann der nicht drin haben was ist dann das Beste was wir tun können 4 3 und hier mit Gewicht was war das 4 ja was ist der Unterschied also hier komm nicht vor hieß hier Klima insgesamt Summe 11 aber auch diese Karte noch zu ne mit betrachten die aber nicht drin ist gegen das Gewicht 11 hier das Gericht das ist nur 3 6 und 4 wie kriegen wir das Gericht 9 13 raus ja 2 Unterschied das heißt also wir können nicht einfach die Ursprünge das ursprüngliche Gewicht dieser kannte hier hier lassen wenn wir das denn wenn diese Kante zu maximalen an gehört hat das Konsequenzen ich hoffe ich habe das ist alles nicht falsch gerechnet hat das Konsequenzen wenn die Karte nicht so manchen gehört haben wir hier insgesamt Gewicht 11 drin wenn die Kante zu manchen gehört haben wir Gewicht 13 drin das heißt der Unterschied ist sind genau diese 2 ja der Unterschied ob diese Karte drin ist oder nicht und das ist nicht ihr Gewicht weil wir hier noch Konsequenzen haben der Unterschied ist der zwischen 11 und 13 und das ist genau diese 2 es macht 2 Zähler Unterschied insgesamt inklusive der Betrachtung dieses geschonten zu das macht das 2 Zähler Unterschied ob dieses kannte schon drin ist oder nicht und deshalb wird ihrer Hinzunahme mit 2 wenn man die mit dem Gericht 2. und es ist klar war so weit die Formel dazu finden Sie unten wenn man das Gewicht der erkannte ja was machen in diesem Fall wenn die kann ich so manchen gehört dann nehme die Kante mit kleinsten Gewicht raus und er und und das war es wenn die ganzen Wahnsinn gehört nehme stattdessen diese Kante heraus wenn die zumarschiert muss man stattdessen die rausnehmen und das ist genau in dem variierten Gewicht drin wenn man die Karte die die die aber kannte die rein Zeit von 3 nach 1 der man kann ja auch also zeigt den Gewicht ziehen wir ab und das Gewicht das ganze Gewicht der kann ziehen addieren drauf und kriegen damit das neue Gewicht das ist die Idee dahinter ich doch genial oder genial einfach und ein letztes Wort wer mir heute mal pünktlich angefangen dieses in diesem Fall hier in diesem kleinen Beispiel ist das gebnis tatsächlich schon Züge frei das heißt maximales Branching hier Max in kritischer Graf hier bis er ist schon die Lösung was sehr kritische Graf hier das ist wenn wir sowohl die kann davon wie zwar nach während er sowohl die von der einfach 5 hinzunehmen dann amerikanische gaben dass die Lösung die würden wir dann wieder rückwärts wir n schrumpfen die Zügel würden wir dann hier wieder er dann entsprechen diese das Übertra- als ebenso beitragen wie sie im skizziert habe im Allgemeinen wird man dich diese Operation noch nicht alle Züge los geworden sein man wird diese zügellos gewann seine Mannen schon fad aber so wie der neue griechische Züge geben deshalb würde man das ganze und das ist der das ist das ist die Logik des Algorithmus man mir das Ganze rekursiv weitermachen nachdem man hier auf der rechten Seite dieser Folie gelandet ist im Normalfall hat man noch kritische Züge wieder in diesem Beispiel nicht im Normalfall schon wird man wieder rekursiv das Ganze machen und so weiter und so fort und da wenn man beim nächsten Mal zu sprechen kommen es gibt noch einen verstehbaren Satz beweisbaren Satz also weiß man versteht was mir gar nicht so weit auseinander geht die für alle Beweise 1 1 1 verstehbare Aussage die sagt wenn ich hier ein optimales dorthin gefahren habe und so von vom ihrer dass auch hier optimal so das Wort zum Sonntag dann darf ich mich für heute von Ihnen verabschieden und werde immer noch was abgeben möchte hier bitte auf diese Stimme auf diese Stabel und dennoch noch was abholen welche vom letzten Mal das ist das ist der Stapel ich jetzt in der Hand haben also wo und sich das ab
Feedback
hidden