Basic Definitions and Graph Representations

Video thumbnail (Frame 0) Video thumbnail (Frame 9787) Video thumbnail (Frame 19292) Video thumbnail (Frame 21802) Video thumbnail (Frame 32694) Video thumbnail (Frame 44681) Video thumbnail (Frame 52514) Video thumbnail (Frame 64782) Video thumbnail (Frame 74228) Video thumbnail (Frame 83674) Video thumbnail (Frame 85469) Video thumbnail (Frame 97214) Video thumbnail (Frame 110362) Video thumbnail (Frame 123510) Video thumbnail (Frame 136657)
Video in TIB AV-Portal: Basic Definitions and Graph Representations

Formal Metadata

Title
Basic Definitions and Graph Representations
Title of Series
Part Number
1
Number of Parts
15
Author
Contributors
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...
Mathematische Methode Calculation Presentation of a group Content (media) Laufzeit
Quantum state Graph (mathematics) Modulform Set (mathematics)
Kante Multiplication Graph (mathematics) Direction (geometry) Division (mathematics) Infinity Set (mathematics) Infinity Connected space Probability theory Network topology Agreeableness Graph (mathematics) Mathematician Orientierbare Mannigfaltigkeit Vertex (graph theory) Quote Multiplication Arc (geometry) Loop (music) Directed graph Directed graph Identical particles
Kante Zahl Parity (mathematics) Graph (mathematics) Division (mathematics) Equation Subset Incidence algebra Modulform Mathematician Number theory Vertex (graph theory) Summation Arc (geometry) Addition Gradient Set (mathematics) Calculus Inclusion map Schulmathematik Infinite set Film editing Logic Vertex (graph theory) Quote
Kante Greatest element Addition Graph (mathematics) Direction (geometry) Weight Number Sequence Hausdorff space Force Subgraph Velocity Graph (mathematics) Mathematician Directed graph Arithmetic progression Link (knot theory) Twin prime Set (mathematics) Formalismus <Mathematik> Film editing Network topology Orientation (vector space) Hill differential equation Factorization Directed graph
Kante Point (geometry) Stress (mechanics) 12 (number) Norm <Mathematik> Addition Graph (mathematics) Sequence Hausdorff space Connected space Plane (geometry) Subgraph Zusammenhang <Mathematik> Forest Mathematician Vertex (graph theory) Arithmetic progression Hamiltonian (quantum mechanics) Link (knot theory) Compass (drafting) Desire path Set (mathematics) Connected space Network topology Connectivity (graph theory) Directed graph
Kante Graph (mathematics) Division (mathematics) List of anatomical isthmi Order of magnitude Connected space Energie Plane (geometry) Network topology Graph (mathematics) Spacetime Vertex (graph theory) Arc (geometry) Directed graph Lemma (mathematics) Laufzeit Parameter (computer programming) Square Set (mathematics) Mittelungsverfahren Matrix (mathematics) Sequence Forest Sierpinski triangle Film editing Quadratic equation Connectivity (graph theory) Abschätzung Factorization Group representation
Kante Presentation of a group Graph (mathematics) Direction (geometry) Physical quantity Group representation Matrix (mathematics) Insertion loss Vertex (graph theory) Length Arc (geometry) Social class Adjacency matrix Spanning tree Laufzeit Range (statistics) Square Two-dimensional space Statistical hypothesis testing Null CW-Komplex Fluid statics Military operation Berechnung Fundamental solution Darstellungsraum Flux Trail Neighbourhood (graph theory) Real number Kapazität <Mathematik> Number Energie Iteration Spacetime Adjacency matrix Operations research Axiom of choice Theory Set (mathematics) Matrix (mathematics) Existence Sphere Network topology Iteration Musical ensemble Quote Parallelen Matrix (mathematics) Group representation
Kante Operations research Eigenvalues and eigenvectors Graph (mathematics) Direction (geometry) Algebraic structure Laufzeit Set (mathematics) Variable (mathematics) Insertion loss Iteration Graph (mathematics) Quadrilateral Directed set Vertex (graph theory) Length Mathematical optimization Arc (geometry) Group representation
so genau sind die anderen immer so sein dass er verlängert werden an der TU Darmstadt so hallo
allerseits ich darf Sie ganz herzlich begrüßen zur Vorlesung effizienter Graf mal Gründen in diesem Semester mein Name ist Carsten Meyer ich werden hier Profess am Fachbereich Informatik und vertrete das Fach Algorithmik er bevorzuge satorischen kommt nur ein Wort zum inhaltlichen erst einmal gekommen natürlich noch genug zum inhaltlichen hier die Vorlesung schließt sich direkt an die GDI 2 Jahren sowohl was die Inhalte angeht als auch was die Methodiken angeht vertieft das Ganze auch die Methodiken werden intensiviert die mathematischen Methodiken etwa Korrektheit Laufzeit Bestimmungen und ähnliches es schließt sich insbesondere an die Grafen Algorithmen natürlich an die sie aus der Idee 2 können Sie haben sicherlich bei wem auch immer sie gehört haben sie haben kürzeste Wege Algorithmen kennen gelernt minimale sparen wollen mehr und so weiter und die werden sich auch wieder sehen allerdings auch in vertiefter Form und wir noch einige weitere Themen der behandeln ich möchte erst einmal aber aus zu sprechen kommen sie sehen schon komische Situationen den kleinen Raum habe ich Headset Zeit auf und trotzdem geht es über die Lautsprecher das wird hoffentlich wenn alles funktioniert hat jetzt aufgenommen und der gestrigen hier wird ebenfalls aufgenommen und wenn das auch funktioniert hat würde wenn ich hier wieder die linke Seite auf einer Tafel verwenden während die rechte Seite für die für den wie man dann immer bleibt um auch mal ein paar Sachen neben her noch an die Tafel zu schreiben und die Sachen wenden durch diese Kamera hier aufgenommen das weiß alles ziemlich ad-hoc spontan also am Freitag keine Email vom Studiendekan an alle Dozenten es gibt jetzt neuerdings für den Fachbereich Unterstützung vom C und dankenswerterweise seine Mitarbeiter von gilt sie dann auch dabei aber von Freitag auf heute das so organisieren dass es jetzt etwas experimentellen ich hoffe mal dass alles funktioniert und dann müssen wir auch sehen wie wir das Ganze dann für die weiteren Termine organisieren können zum 1. Mal ein Auto Konstellationen wo das aufnehmen können so comma zum organisatorischen da wollt ich eigentlich den entsprechende Webseite hier zeigen aber dass in fremde Rechner ist Versuch ich da jetzt nicht allzu viel die Vorlesung also ich gehe jetzt die Inhalte der der der Informationswert Seite bei uns im Bereich eine gut ich von Tukan aus müssten Sie einen link auf unsere Seiten gefunden haben von da aus auch Links zu sämtlichen Materialien und allen die Vorlesung findet nur zu diesem Termin statt das ist der eine voll Termin pro Woche beginnt heute Dozent bin ich hier am Donnerstag also übermorgen bitte nein übermorgen Beginn noch keinen Termin also ab nächster Woche Donnerstag wir gehen dann die Übungs- Termine diese Übungs- der mir nicht von mir abgehalten sondern von einer studentischen Hilfskraft namens Andreas 10 vor das ist auch schon mein letztes Jahr gemacht hat und vorletztes selber die Lehrveranstaltung gehört hat also ausreichend Erfahrung damit hat wie ja wir erwarten von Ihnen dass es freiwillig aber wir erwarten trotzdem von Ihnen dass Sie die wöchentlich ausgegebenen Übungsaufgaben hier intensiv bearbeiten abgeben und die werden dann auch am jeweils am Donnerstag am Übungs- Termin gesprochen sind freiwillig weil es auch gar keine Möglichkeit gibt das verpflichtend zu machen aber der kleine Anreiz dafür dass sie das auf jeden Fall doch wirklich ernst nehmen und auch sich mit den Übungsaufgaben intensiv auseinandersetzen der kleine Einheit ist der dass die Übungsaufgaben natürlich nicht unwesentlich auch dann für die Prüfungen wichtig sind ja die Prüfung das ist ja 4 Semesterwochenstunden 2 Semester schon ist die Vorlesung da fehlt noch ein bisschen Stoff und das ist der Stoff der Übungen der mit einfließen wird in die Prüfung am Ende und da wird dann auch schon beim Thema Prüfung ich stelle mir wenn sie nicht lauthals pro testieren stell ich mir mündliche Prüfung vor bitte bitte sie wurde okay okay ja ich denke dass dieser Stoff eigentlich gut geeignet ist oder das Schluss umgekehrt das schriftliche Prüfungen Person eigentlich nicht so gut geeignet sind für diese Art von Stoffen insbesondere auch dann wenn wir über die Übungsaufgaben die Übungsaufgaben mit einbeziehen und ich will es mal so formulieren die Erfahrungen der letzten Jahre da hatte der Stelle die Vorlesung gehalten die Erfahrung Mittler Sohn den letzten Jahren war man erst mal durchwachsen und außerdem denke ich ist es sinnvoll dass Sie hin um mehren mindestens einmal wenn möglich mehrere Mal im Laufe ihres Studiums auch mit mündlichen Prüfung Situation in Kontakt kommen der mündliche Prüfung Situation sind das im Gegensatz zu Klausuren was vielleicht ein bisschen lebensnäher dann später ist für Ihre berufliche Weiterentwicklung angefangen beim Jobinterview beim Bewerbungsgespräch guten Präsentationen Vorstands Präsentation und so weiter und so fort das sind mündliche Prüfung sicherlich eine bessere Vorbereitung als Klausuren Klausuren brauchen Sie nur als Vorbereitung falls Sie noch den Führerschein machen müssen oder falls sie noch mal machen müssen dann dafür sind also und sicherlich noch mal gute Vorbereitung gut mit geben kann auch noch den Vorteil dass wir die Termine individuell absprechen können und das meine ich auch wirklich so ich habe im letzten Jahr in meiner Veranstaltung immer also meine der Veranstaltung wie diese hier immer mündliche Prüfungen gemacht und mir ist es eigentlich ziemlich egal 1 die Prüfungen
stattfinden manche Leute wollen es gerne schon am Ende des Semesters oder am Anfang der vorlesungsfreien Zeit haben weil das möglich schnell hinter sich haben wollen andere wollen es vielleicht eher im September Oktober hier 7. Oktober hatte ich für meine altrömischen Modellierung was im Sommersemester eine ganze Menge mündliche Prüfung gehabt es gibt auch welche die wollen das noch später im Laufe der Vorlesungszeit oder oder im Laufe der nächsten vorlesungsfreien Zeit das ist mir alles vollkommen egal das müssen Sie bilateral mit ihren über Zuständen Studienbüro absprechen was möglich ist und was nicht und dann wird sich schon Termin finden ich nicht Karte oder bin oder so wird sich das schon irgendwie regeln lassen da einen Termin zu finden das heißt also Sie haben da völlige Freiheit bilateral mit mir zu entscheiden wann überhaupt ihr Prüfungstermin stattfindet und ich denke dass es nur Annehmlichkeit oder insbesondere ich hatte ganz früher immer versucht habe erstmal gewartet bis alle Leute ihre Klausurtermine wussten und hat dann versucht unseren Klausur Termin dann so zu legen dass es möglichst bei einem passt und es hat natürlich nie so richtig gepasst mündlichen Prüfungen klar passt das natürlich weil die Termine für das ist so die wesentlichen Punkte habe ich dazu gesagt Sprechzeiten noch im ich habe keine festen Zeiten früher hat ich feste Zeiten da habe ich mich da habe ich immer gesessen mich gelangweilt und dann sind die Leute trotzdem und wann bekomme aber nicht zu den Sprechzeiten deshalb ist meine Regelung unmittelbar im Anschluss an die Vorlesung können sie mich immer erreichen außer es ist mal notwendig dass sie kann schnell weg muss aber das ist selten der Fall und ansonsten können Sie mich jederzeit auch per Email erreichen fast jeder Zeit und dann kann man gerne entweder sich über Email austauschen wenn das Problem bei immer lösbar ist oder man stellt fest das Problem ist nicht per Email das Paar da muss man Termin ausmachen um sich zu sprechen gut was gibt es noch zum organisatorischen zu sagen ja ein period eine Kommilitonin eben auf mich zugekommen dass anscheinend Probleme mit der Anmeldungen Tukan gibt da weiß ich nicht was soll zum Problem schon wieder ist ich werde mich aber dann im Nachgang zu dieser Vorlesung darum kümmern dass sämtliche etwaigen Probleme da ausgeräumt werden hat man sonst noch Probleme Tukane also darin ganz ganz kurz noch Bento kann hat immer noch Probleme tuckern das ist hier Foundation Soft Computing nicht dicker Geige wird den beiden okay ja laut tuckern okay dann will ich nicht widersprechen also mich das nicht mich stört es nicht wenn es in beiden vorkommt ach so dann kann es vielleicht sein dadurch dass in beiden läuft dass es da unten Problem gibt bei der Einrichtung okay das ist ein guter Hinweis noch versucht sich über die okay das ist gut denn was dann werde dann weiß ich kann ich ganz gezielt nachfragen und nachforschen lassen Sie sich das Problem beheben ist ich den Ticker ja gut das ist das ist eine gute Hinweise dann wissen wir ganz genau von 8 viel zu suchen haben gut Tukan ist damit hoffentlich für uns hier beendet so jetzt war die Frage kann ohne die hat sich damit auch geklärt also ich muss sagen ich bin ich die auf offiz ich bin ich derjenige der offizielle sagen keinen welche kann ohne nicht dass es offiziell keine Nutoka beziehungsweise Studienbüro beziehungsweise Prüfungsausschuss allen aber so wie ich jetzt gehört habe ist es in Tucheim sowohl in Fock als auch in der KI eingetragen dann ist das so die aktuelle Information ja okay ach so in E aber mit Abklärungen Studienbüro gut ich warte noch ein Studienbüro und Bayern stellen nach damit damit sie dann möglichst keine Probleme haben könnte natürlich der natürlich nicht wissen es doch noch ein Programm gestanden hätte aber gut das ist offensichtlich ein Problem das ich lösen lässt so haben Sie dann noch ich habe jetzt nichts weiter gehen vom Aldi die Übungsaufgaben finden Sie alle schon auf der unter der Matte auf der Materialien Seite sie finden ganz oben das Vorlesungsskript ist ein bisschen klein geraten diese eine linke und da dort unterkommen gleich die großen großen Sammlungen von weiteren Materialien dem bei den Übungsaufgaben steht immer dabei welcher auf einen See abzugeben sind und wann sie besprochen werden das ist jeweils mit hatte um sie gehen die Übungs- bei Aufgaben bitte ab den Sie auf Papier abgeben wollen dann bitte hier einer Vorlesung ansonsten wenn Sie sie nicht aus Papier abgeben wollen sondern in der er sondern er online dann geben Sie sie ab an die Email-Adresse ich sehe die @ Algo dot Informatik und so weiter kann man das lesen also schon eines der Grundprobleme bei mir auch wenn ich in Druckbuchstaben schreibe ist mein Schriftbild nicht besonders gut das hat man sich bitte immer wenn sie was nicht lesen können gut gibt es noch Formen ihrer Seite aus Fragen jetzt zum organisatorischen es gibt auch ein Forum als eingerichtet worden oder es ist sowieso eingerichtet das sich dann auch wo ich dann auch immer reinschauen werde in der 20 vor mehr also mit Mode so was machen wir hier nichts Forum ist der 120 und ansonsten an so weit tuckernd also falls sie noch später in welchen satorischen Fragen haben will ich bin ja nicht aus der Welt dann wird sich das übers Forum oder per Email oder sonst wie natürlich immer klären lassen gut keine Wiese torischen fragen jetzt so weit dann gehen wir zum inhaltlichen effiziente Grafen
Algorithmen Art Nein da wir müssen
natürlich erst mal ganz klein anfangen etwas systematische war als er bei der die 2 wo manche die hopplahopp gemacht worden sind hier nochmal systematische war dazu werde ich dann je nachdem auch immer noch an der Tafel was machen und die Dinge nochmal genau zu klären wie werden heute Dinge machen die eigentlich nicht schwierig zu verstehen sind wären einige Punkte kommen noch für der Vorlesung wo man vorhersagen kann die sind nicht so ganz einfach zu verstehen aber heute denke ich bei bei denen grundlegende Definition und Ge und Grafen Repräsentation wird es noch nicht der Fall sein Sie sie jetzt noch eine Kleinigkeit aber die vergessen nur zu sehen ich rede auf Deutsch es sei denn sie wollen lieber das sich auf Englisch Räder okay keinen für nichtig dann einfach auf Deutsch weiter aller Erfahrung nach findet sich typischerweise keine Mehrheit für Stadt Deutsch aber die Folien sind auf Englisch das ist erfahrungsgemäß oft ein Seite immer wieder ein Kritikpunkt bei Evolution aber auch erfahrungsgemäß oft andern Seite eigentlich eine gute Möglichkeit relativ sanft in das Fach in mich hinein zu kommen und ich meine Informatik ist ja nun ein X in dem Englisch sehr viel wichtiger ist als beispielsweise in Germanistik oder die oder in der Rechtswissenschaft solange es nicht internationalen Rechtswissenschaften sind und so weiter so was ist eingerichtet
da und und gerichteter Graph und und gerichteter Graph ist das was Sie zum Beispiel bei minimal spannen Bäumen kennen gelernt haben sie haben ne Menge davon geworden und Menge von ungerichteten kannten so der muss sich zusammenhängend sein der kann zum Beispiel mehrere zusammen Komponenten haben noch sehen kann noch einzelne isolierte Knoten haben aber er und Gerichte bedeutet eben dass die kann den Richtung war minimal Spannung mindestens ein Beispiel was sie kennen gelernt haben werde die 2 oder okay so war steht hier spezifiziert ist definiert durch die Quoten wenn der V das ist eine kleine und Schönheit in englischen Terminologie man kürzt die Knoten man immer mit V ab für würde ist es aber man redet immer von Notz muss man sich dran gewöhnen der die Karte die die Menge der kann kann er die es da passt es wieder Wartezeit auf etliche ist es kann ja durchaus sein sie sind es dran gewöhnt dass ihn gerade so aussieht aber zum 1. Mal spricht nichts dagegen dass es vielleicht auch mehrere Kanten zwischen 2 in gibt ja ständig vor mehrere Verbindungen Kommunikationswege zwischen 2 Knoten geht es um voneinander sind oder so etwas ja das will man manchmal auch haben deshalb steht hier Multi Site Menge im Gegensatz seiner mathematischen Menge wo es immer nur einmal vorkommen können können einem nur die Menge jedes Element mehrfach vorkommenden mehr Städte steckt da nicht dahinter das wir von einer Multis Verträge Martei SZ reden gerichteter Graph ist jetzt das selber und nur das wir jetzt Richtungen Orientierungen dabei haben bei allen kannten es kann natürlich auch so sein beispielsweise wie das jetzt hier eine Karte so um eine könnte so rum und auch hier wieder am Markt Z natürlich können Sie auch mehrere gerichtete kannten von einem Knoten zu dem andern nahm also das hier ist der Grund für Martha hält zweimal dieser bekannte vom selben Knoten sind einen Knoten das ist natürlich nicht noch nicht mal 3 weil wir hier von 2 verschiedenen kann in einer von den so dem und eine von den Quoten zudem in meisten Fällen werden wir werden wir ja ohne multi betrachten also dass das keine 2 Kanten gleichen Kanten gibt in den meisten algorithmischen Problemstellung kann man auch ohne Beschränkung der Gemeinheit an denen das ist nur einige der stellen sich kürzeste Wege vor wenn Sie hier 2 Wege haben ein Tor zum andern dann nehmen Sie den Kürzung von den Beinen dann an schmeißen aus als ohne Beschränkung der Allgemeinheit bei Christen wegen haben wir eine einfache Menge von kannten also sehen dass es ein bisschen schwierig seit dem die allgemeine didaktische nach Religion sagt das Paar nicht so wichtig sind ist es ein bisschen schwierig an der Tafel zu arbeiten also im Audimax zum Beispiel gibt es gar keine Tafel mehr das macht natürlich besonders schwierig so Grafen können auch unendlich seiner man betrachtet in manchen Gegenden der Mathematik tatsächlich unendliche Graf eine unendliche Knoten Menge oder eine unendliche Kantenlänge das hat durchaus auch konkrete Anwendungen beispielsweise der Wahrscheinlichkeitstheorie wenn die Grafen verschiedene Möglichkeiten bedeuten die man wie man man wie man man zufällig in welche Richtung geht aber das interessiert uns hier nicht bei uns in die Grafen endlich das heißt ja man endlich wieder so wie es gezeichnet aber eine endliche Grundmenge und dann natürlich auch ländliche kann so die Kanten finde kannte haben wir n Punkte das ist das was man sich darunter vorstellen würde sie haben ungerichtete kannte dann sind das natürlich die beiden Endpunkte oder sie eine gerichtete kannte dann sind natürlich das auch wieder die beiden Endpunkte dieser Kanther und was wir jetzt hier haben ist ganz spezielle bei gerichteten kannten das sie noch einer genau vom Unterscheidung haben tägl Schwanz rät Kopf für die kann das stellt sich offenbar die kann das 100 schlagen oder Rum oder was vor und werde deshalb von Kopf und Schwanz und diese kannte wenn wir jetzt hier ein Knoten vor und ein Knoten wir haben also sehen noch eine Mutation wieder VW man denke dann wird es hieß aber wie das englische Wort Knoten wenn das Ausscheiden nutzen und das ist die die könnte aber dann ist aber outgoing Kg das steht dort auf der Folie von Faro und Ingo Link von W also sicherlich eine sehr logischer und und intuitive Begriffsdefinition abgelehnt und in Poing ach so in kann ist genannt also beides ist möglich in K in Going oder in Kamen so die beiden zum dasselbe gut 2 Kanten mit denselben Endpunkten sind parallele kann da komme ist es malt es wird wieder vor glaube ich wohne jetzt nicht weiter zu ein Lob eine Schleife das ist das was man sich auch darunter vorstellen würde das ist bekannt die von einem Punkt sei von einem Klon zu sich selbst kommt gerichtet oder ungerecht es gibt wenige Situationen in denen man wirklich schleifen mit betrachten möchte manchmal gibt es das aber für die ist sehr selten und bei uns spielt es endlich hier in dieser Vorlesung keine Rolle solche Schleifen falls es mal an irgend einer Stelle punktuell eine Rolle spielt wenn sie schon merken so und jetzt noch die letzte Definition wenn ein Graf wieder parallele könnten hat noch also wenn wenn die gibt kann man keine Multis wird ist so wie das eben gesagt haben und wenn es auch keine Schleifen gibt dann heißt der Graf einfach im englischen sind und das ist die Standardsituation mit dem bis zu tun haben so wie man sich in Grafen vorstellt das ist das was wir hier einen einfachen trafen den werden hier
nochmal ein gerichtetes Beispiele noch ein paar Begriffe mit denen wir umgehen müssen also es dann schon für das weitere verfolgen der Vorlesung wichtig dass die Begriffe die jetzt hier betrachten heute dass die dann setzen dass sie die im Hinterkopf parat haben weil ich würde dann einfach von der 10 oder Incident sprechen und will mir nicht die Mühe machen jedes Mal wieder noch mal die immer noch mal zu sagen was das jeweils ist sonnig ich würde davon ausgehen dass sie das Wissen für das natürlich später bei arabischen waren nicht immer voraussetzen dass sie das was wir letzte Stunde gemacht haben so genau parat haben das wäre ein bisschen sehr viel verlangt aber wir müssen uns darauf einigen wir uns darauf verständigen dass diese Basis Definition von heute dass die bei Ihnen bekannt sind weil sie sonst an den Faden verlieren wenn wir 2 eigentlichen Themen kommen so wenn wir 2 Wänden steht hier werden 2 legt Knoten miteinander verbunden sind durch im ungerichteten weil durch ein Etsch kannte im gleichen Fall durch eine arg ich das habe ich noch vergessen zu sagen im englischen schaltet man meistens nicht immer Literatur geht auch da müssen auseinander bei um dich den ganzen sagt der Ch und bei also Deutsch kannte und bei gerichtet sagt man arg also Deutsch Bogen im deutschen Nazis einige eingeschliffen dass meine beiden Fällen von Kanther spricht weil meistens aus dem Kontext klar als optional gerichtete ungerichtete kannte ist so 2 Knoten die also durch unbekannte miteinander verbunden sind sind adjacent das wenn ich mich recht an meinen Lateinunterricht erinnere heißt das so viel beieinander liegend und wir sagen dass die beiden Nachbarn sondern das sind so wenn einen könne nur wenn wir ein Klon und eine damit verbundene Kanther betrachten dann reden wir von Incident und ich glaube mich zu ändern dass was das so was heißt wie einen fallend oder so etwas hat immer noch Latein gehabt und Raub und Auto zig hat jemand Dateien gab und oder sich nicht erhalten werden kann ein so auch hier wieder 2 kannten die die im selben Knoten zusammenlaufen egal ob gerichtet und gerichtet und so weiter 2 Kanten die ein Knoten gemeinsam haben schwer Endpoint teilen sich einen Knoten die heißen auch wieder adjacent beieinander liegend so das sind alles denke ich sehr einfache Begriffe man muss sie sich einfach nur mal in den Hintergrund Speicher laden auch der Grad der Diggory der gerade eines Knotens ist eine einfache Sache dass es einfach die Anzahl der Kanten die mit diesen Knoten verbunden sind das nennt man typischerweise den gerade da die Nachbarn sind die ist die Bezeichnung man typischerweise die Nachbarn es Knoten Faust der mir eben die Nachbarn gesagt dass die die mit dem Kunden V durch unbekannte irgendwie so und so rum oder ungerichtet verbunden sind des Nachbarn bezeichnet man üblicherweise mit Delta V war und das ist so komisch jetzt hier aus sieht der davon Menge von V R haben dazu werden wir später noch kommen aber ich will's mal ganz kurz sagen damit sie da jetzt nicht mit question mark bleiben wir werden später das öfter mal Grafen einfach so zeichnen ja dann stellen sich vor dass ein Punkte Knoten kannten dran irgendwie da drin das ist sozusagen der umreißt so jetzt haben wir zum Beispiel keine zum Beispiel die die Knoten Menge in 2 Teile zu teilen eine Teilmenge X und eine Teilmenge Formen des Ex und zwischen diesen beiden Quoten ging es irgendwelche kann nur über ein Knoten x und ein Knoten nicht in nichts dann würde man diese kann hier der davon X 1 das wir werden später mit solchen schnitten ein sogenannter Schnitt werden mit solchen schnitten später einiges anstellen und dann ist auch logisch was was die Logik was warum das jetzt so komisch aussieht wir haben hier wieder Sohn Grafen wir haben einen Knoten V und dieses Delta zwischen V also X ist gleich dem mehr in diesem Fall X ist gleich die Menge mit dem man V und dass der der zwischen den Fronten zwischen diesen Ex was muss vorgestellt und dem Rest ist gesehen gerade die zu Frau in sidenten kannten und um ich sehe ich schon hier sind jetzt sehe die Nachbarn ok das ist es wenn die Nachbar also sowohl die Nachbarn als auch die Karte zu den Nachbarn damit bezeichnet ja es richtig ich glaube es eine kleine und Schönheit in dem Skript trennen sie noch man stille besprechen aber letztendlich läuft es darauf hinaus dass wir dass wir solche Schnitte betrachten so in ein Gericht in Graf betrachtet man doch noch dann noch die spezieller unterscheidet man wieder die Reihen gegen die rausgehen und Kanten und sagt dann aber sie sehen dass hier schon hier schon diese und Schönheit auftritt ich muss mich ja für unschuldig erklären diesen Teil habe ich nicht geschrieben hätte mehr sie sehen hier schon dass dieser zweite schon period tatsächlich dieser dieser exakt dieser dieser Definition entspricht wie meiner Tafel hatte hier mit mit diesen schnitten denn hier ist die Rede dass die dass die reingehen und die rausgehen und kannten jeweils mit der Terminus beziehungsweise Delta plus bezeichnet wird also denken Sie sich hier um auch das nicht Ebbers sondern die die Kanten zu diesen übers mit der der bezeichnet werden was wird das für die Notation sein so was steht hier also der Terminus sind die rausgehen ne die reinkommen kannten im Vorhinein und der ausgehenden sind älter Plus so oder in der ihnen gerade in die Nikoley ist dann der die die Kardinalität von der Terminus logischerweise und der außen gerade die Anzahl der kann rausgehen ist dann die EKD Naivität von Delta Plus und der Gesamt gerade 1 c't Knotens in eingerichteten Grafen ist da natürlich die Summe Anzahl Einkommen plus an ausgehende Kanten nix großartig zu verstehen da Knoten mit gerade 0 ich in der ursprünglich auch gezeichnet hatte eine solche Tor-Knoten auch intuitive Definition so war die 1. kleine Beobachtung für jeden Graf ist die Anzahl der Knoten ungeraden Grades gerade also das englische Wort Ort bedeutet und gerade im mathematischen Sinn 1 3 5 7 und so weiter und das englische Wort für diesen bedeutet unter anderem auch gerade also beide war da natürlich noch diverse andere Bedeutungen also gerade 0 2 4 6 8 und so weiter so und warum ist das so ich glaube auf den Folien ist kein Beweis dann müssen
wir uns diese Arbeit hier machen und müssen mal schauen ob wir auch mal was zum wir schon haben da sogar noch frisch offenbar wenig der 1. heute der Tafel benutzt wie ist das bei Ihnen vor dem diese hören wenn die Tafel noch viel benutzt oder nur von wenigen und mehr nee ich arbeite lieber mit der Tafel also dass man auch gut ich überlege es mir noch mal aber eigentlich mehr als ich angefangen habe zu der Ente aus Good Old Sie wissen schon da was typischerweise und größeren übersehen hatte man 6. diesen trafen da man sie einmal alle beschrieben aber die eine Hälfte der Zeit darum hat man Pause gemacht also ich studiere nahm Pause gemacht man selber gewünscht und alles noch mal geschrieben und war die damalige anderthalb Stunden um und man hatte eben immer alles noch parat alles auf einen Blick sichtbar dass wir dann groß genug das ganze dass man alle Tafeln auseinanderzerren konnte und alles auf eine Karte so und warum ist die Anzahl der der Knoten mit ungeraden gerade also schauen wir schon was vielleicht das mal einem Beispiel an ist das auch tatsächlich so ich mache mal aus der Hand des irgendeinen dummes Beispiel so so welche sind jetzt ungeraden gerade das haben sie eine ganze Menge der er hat ungeraden gerade der Herr der hier der hier noch und das ist dass ich eine gerade Zahl ist in 4 Knoten warum ist das so ganz einfach man macht sich nur eine einfache Gleichung klar die Summe nein die Summe über alle Knoten ja wir von jetzt ein bisschen an mit der typischen Notation die wir hier so verwendet werden und das ist vielleicht schon mal etwas Neues ich weiß nicht inwieweit ihm das vertraut ist über eine Menge zu summieren also was sie natürlich kennen aus der Mathematik sowas wie Summe II gleich 1 bis n das ist nichts anderes als die so mehr über die aus der Menge 1 bis i durchläuft die Menge 1 bis und so wie es recht steht kann das natürlich auch beliebige Mengen aus sogar unendliche Mengen man will verallgemeinern und kann oder zum Beispiel hier das ist die Summe aller Werte ja gerade aller Knoten ja wir so was hier steht ist für summieren die gerade die Tigris aller Knoten auf Summation über alle Knoten und was ist das mehr wenn wir ich jeden Knoten gerade aufsummieren dann heißt es wir haben jede Kante zweimal getroffen das heißt das ist gerade zweimal die Anzahl der Kanten ja wir haben einmal die Kanten so gezählt und einmal müsse so gezählt so das ist aber eine gerade Zahl so und wenn eine gerade zahlen sich aus sie wissen dass es jetzt nicht mehr Inhalt der Grafen Algorithmen natürlich sondern elementare Mathematik wenn eine Summe sich zu einer geraden Zahl aufsummiert dann können nur gerade viele Summanden und gerade sein ja wenn sie und gerade viele zum nahm die ungerade sind dann ist es Ergebnis ungerade und fertig das ist ein typisches Beispiel typische 1. Einführung des Beispiele wie viel Jahr argumentieren oder beweisen bei den effizienten Grafen Algorithmen wir sind so ein bisschen in der Mitte zwischen beweisen wie sie es von der Mathematiker können und argumentieren wie man es eben ich weiß nicht in Jura oder sonst wo machen würde wir haben nicht dieses strikte Kalkül zur Verfügung wie sieht's aus wenn man immer die gewöhnt sind aber deshalb müssen wir an manchen Stellen eben im argumentieren dass in 1. Einführung das Beispiel dazu das ist aber auch nicht unwesentlich diese Beobachtung müssen Sie jetzt für die weitere Vorlesung heute und darüber hinaus nicht unbedingt im Kopf haben da aber eben falls wir brauchen wir werden sicherlich noch mal drauf zurückkommen dann werde ich das natürlich nochmal in Erinnerung rufen so jetzt
wird es ein bisschen kompliziert da das aber auch nicht so kompliziert wie es so erst aussieht machen wir das mal ein bisschen Platz also es wäre mir recht wenn dann das wenn dann jetzt der zusammen Schnitt meiner Tafel Fisch Station ich auf YouTube erscheinen würde worden so wie Sie das jetzt eigentlich in mit Kreide aus da ist noch ein kleines Stück so wenn sie einen das ist vielleicht ein bisschen untergegangen die Graf schreib ich noch mal hin vielleicht arbeitet Graf also gerichteter Graph wird immer wieder auf den Folien einfach mit die Graf apt-get kürzt bei 3 comma decimal 8 so wenn Sie jetzt einen das Gericht den Grafen haben dem nochmals mal ein bisschen einfach kommt nicht so drauf an so das ist also der gerichteter Graph und dann dazu der ist das hier der der zugrunde nicht der unterliegende dass wir glaube ich es keine gute Übersetzung ich bevorzuge der zugrunde liegende gerichtete Kraft ja also eine ganz einfache Sache Musik Siegringen zugrunde liegen Geräten Grafen in dem sie einfach sämtliche und jungen wegnehmen es kann natürlich auch passieren sollte man jetzt nicht untern Tisch fallen lassen dass die sich hier 2 kann in verschiedene Richtungen haben ja was wir aber dann sagen ist dass der zugrundeliegende gerichtete ihrer Verehrung gerichtete Graf trotzdem nur eine Kante enthält ja er bleibe weiterhin wie es da steht 10. Herbert einfach wenn alles klappt dann können Sie sich das ja auch später noch mal dann zu Hause gemütlich anschauen bei bei der die die 2 übrigens die habe ich letztes Semester auch aufnehmen lassen der haben die Studierenden das dann immer mit Faktor 1 comma decimal 5 Geschwindigkeit Beschleunigung sich an der schaut offenbar so langsam dass das dann wunderbar gut geht damit habe ich kein Problem ich mein Ziel ist es nicht jetzt möglichst viel Stoff zu Blockaden mein Ziel ist es möglichst die Dinge die wir betrachten und dann richtig zu betrachten so dass sie den Stoff den wir ausgelassen haben falls Sie mal irgendwann benötigen sich auch selber auch nicht aneignen können so ein sub Graf eines Grafen das das ist was ganz was einfaches sorgen für so kompliziert steht wer zunächst mal hier schauen Sie mal das werden wir hin und wieder mal machen das wird nicht einfach V E sagen sondern dass wir das jetzt genau unterscheiden wir mit 2 Grafen hier wie wir später vielleicht noch mit mir Grafen gleichzeitig tun wir mit mehr als 2 1 und wenn wir die unterscheiden wollen dann müssen wir den zum Beispiel Subs könnte hier geben der Graf Gross G besteht aus der Knoten Menge V sub Skript gehe und es ob Skript gehen und der Graf besteht eben entsprechend der Knut Menge Voraustrupps Isoz gibt Glatthaar so was besagt dieser diese Aussage hier der das Ganze hier ist groß G und der Sogkraft können sich aussuchen steht hier nicht dabei wir haben diese Menge aller roten Knoten ist ein sub Graf diese mehr alle hier das hier ist also Kraft die wir die roten Knoten die blaue Blume jeweils sehen hier interessanter und wichtiger Punkt bei so Graf nämlich das auch wenn diese 3 Knoten alle zu diesem so brav gehören also oder sogar 4 dass nicht alle Brot zu verbinden keimten gehören müssen die gehärtetes dazu die Geräte zu die gehört nicht dazu während hier ist so gewählt worden zu alle die blau verbinden könnten der gehören jetzt dazu aber hier ist es eben nicht so gewählt worden ist ja das ist klar nahm so Graf müssen nicht anerkannten enthalten sein die die ausgewählten Knoten enthalten also wie kommen zu einem so Grafen in die wir einfach Knoten kann wegschmeißen einfach gesprochen wird ok die Frage war ich ich habe mir angewöhnt immer immer das auch ist wie kurze sprechen die Frage war ob eine auch könnten enthalten sein können also zum Beispiel ob den blauen so brauchen auch keine enthalten sein können die nicht 2 blau K Knoten in einer verbinden nein das gehört nicht dazu sondern er sondern die kann müssen immer dann auch existierende Knoten also nicht geht nicht explizit hier hier gesagt worden aber es folgt aus der Definition eines konsistenten Grafen dass das nicht sein kann bitte genau das ist das was ich eben meinte er steht implizit da er aus der aus der Definition was ein konsistenter Graf ist ergibt sich was das dass solche kann nicht dabei sein kann dürfen die nicht Knoten dieses Flughafens miteinander verbinden so jetzt aber die umgekehrte Situation induzierte Sog auf der blaue ein induzierte Sogkraft der rote nicht und zwar genau aus dem Grund was wir eben besprochen hatten was sich im angesprochen hatte der blau so Graf enthält auch alle kannten alle Kanten des ursprünglichen des großen Grafen die blau Knoten in einer verbinden während der rote sub Graf nur meint hier kannten enthält die rote Knoten miteinander verbinden manche eben nicht das kann beliebig sein ja da kann man beliebig auswählen welche dieser kann dazu gehören welche nicht der induzierte ob Graf ist durch die Knut Menge völlig determiniert war alle Karten enthält die diese Knoten und danach bin und die Ursprungs Grafen enthalten war 3 also gut und da jetzt kommen wir wieder eine einen Anknüpfungspunkt einige die 2 sie ändern sich an Minimums schrie oder auch nicht ja ja okay es scheint so was ist 1 wenn ihm das ist Mindens haben einen ungerechten Grafen gehen Zuse sich noch kannten Gewichte okay aber was sie haben wollen ist ein Baum Pläne eine besondere einsparen Eigenschaft hat nämlich dass wir den ganzen Grafen spannend nämlich genau in dem Sinne Visionen steht dass er sämtliche Knoten enthält nicht alle kannten aber nicht um nicht und wenn ich alle könnten aber auf jeden Fall sämtliche Piloten ja also wenn Sie zum Beispiel hier bei dem Grafen hernehmen und alle Knoten in ihren so Craven tun und gar keine könnten oder alle könnten oder nur aus alle können dann ist das ein spannender ob auf und wenn diese Spanne so Graf auch noch ein Baum ist ein spannender brauche so einfach kann die Welt sein so
also ich weiß ist es ein bisschen ermüdend aber wir müssen noch einiges ich glaube so viel ist jetzt gar nicht mehr was wir noch an an verschiedenen und verschiedene Notation hier brauchen jetzt comma wahrscheinlich zum schwierigsten Teil der Notation heute was aber trotzdem wenn wir mal die Hürde überwunden haben muss man klar gemacht haben was hinter diesen Formalismen steht trotzdem wie eine ganz einfache Sache wird was das einfache was das alles ist kennen Sie auch aus der GT 2 da nur wahrscheinlich wesentlich einfacher man kann doch sagen schlampiger eingeführt nämlich Einschätzung der gute alte Pfad oder weg so war es was durch Grafen durchgeht von Punkte und dem anderen period oder einem ungerichteten Fall und gerichteter Graph so was was durch den Grafen durchgeht er sie kennt das mindestens aus kürzester Wege und noch aus anderen Kontexten einige 2 oder anderswo bei den sicherlich auch bei anderen Themen wie Inzest und so wiederbegegnen nämlich an zum es habe ich Geld von den Ausrichtern dass sie auch da extra und Premium groß können so was noch mal machen gut was hat dieses einfache Konzept jetzt mit dieser komplizierten Definition zu tun diese Ed Sprock beherrschen sehen erst einmal ganz normal wie die Kürze schon andeuten ist das eine Reihenfolge Knoten kann der Knoten kann der Knoten kann und so weiter und so fort das heißt also im Grunde vor 1 E 1 V 2 E 2 Ford 3 und so weiter und so fort bis am Ende wenden wir das dann vor Karplus also hier ist das ist dann E K und das ist dann vor OK plus 1 er hat mit dieser Art Verbrechen für ich keine vernünftige übersetzt und jetzt neu ist Horst vielleicht fällt Ihnen ja was Vernünftiges ein ich weiß auch nicht wie man auf diesen Begriff gekommen ist so mehr ist das nichts wir und zwar genau gesagt es kann natürlich auch sein das so oder so ein Pfad den wir da man da am ausgehen wollen dass der nicht so schön wie er aussieht sondern dass der irgendwie so aus ich da kann ja passieren also sich laufend schneidet in welchen Knoten also sehen ich nehme ich mir die Freiheit ein bisschen zu abstrahieren hier ist auch noch mal ja also das eine derselbe Knoten mehrfach getroffen wird wenn das nicht der Fall ist das sagt dieser 2. Fall ist in irdischen als also warten Sie mal halt halt halt Ich bin weit E I ungleich J falsch ich bitte um Entschuldigung das ist sogar noch einen Schritt zu weit das kann ja noch so einen in dieser Definition von Ed Spur kreischen ist ja noch gar nicht ausgeschlossen dass zum Beispiel auch eine Kante mehrfach durchlaufen wird so vielleicht hier Dank hier lang hier lang hier sitzt und die wir zweimal durchlaufen ist nicht ausgeschlossen durch die formale Definition von 11 tropischen oben da steht ja nur hat das ist einfach der alten in der Reihenfolge Kloten Karten Knoten kann kein noch so aussehen wenn das ausgeschlossen geil wenn diese Karte nicht zweimal auftaucht das heißt also wenn keine 2 Kanten in dieser Aufzählung gleich sind dann reden für vor von einem Work wir von einem Spaziergang ich weiß nicht ich weiß nicht wie man sonst Box sinnvoll über setzen kann dann kann es aber immer noch so aussehen wie sie im gezeichnet habe eine Burg kann immer noch so etwas sein wie viel eben gezeigt die VOB so das kann immer noch ein Rock sein aber keine ich Spruch ich mir doch nicht vergessen schon aber anders rum weil weil es keiner kannte zweimal gibt sondern höchstens Knoten mehrfach getroffen werden ist ein Work so und jetzt comma endlich zum Fahrt sie kennen das aus der Mathematik bis wir endlich zu den Zahlen kommt muss man erst mal gelernt haben was es nur grobe was im Regen was ein Körber genauso machen das ja auch er wir wollen schließlich nicht irgendwie da Minderwertigkeitskomplexe über Mathematikern habe als als Mathematiker darf sowas an so jetzt um endlich zum Vater und was ist dann der Vater sie sehen wir wir gehen jetzt hier im bisher sie sehen wie wir in allen Formalismus hier haben einfach mehr mehr was ist das eine Folge also man damals um eine vor eine endliche Folge mit alter Nieren von alternierenden Typ hier haben wir jetzt
der Pfad ist ein Pfad es tatsächlich ein Graf mit einer Knoten und einer kann man und Überraschung ist in genau die Knoten könnten von dem wir oben gesprochen haben die aber die Eigenschaft sehen Sie hier ungleich VJ also dass dieses Bild nicht mehr auftreten kann sondern dass alle alle Pfade dieser Welt nach dieser Definition egal ob gerichtet oder ungerichtet sehen so schön aus ohne dass es sich aufeinander zurück regelt so was sich jedoch über hier ausgelassen habe wir müssen natürlich auch noch auf zurückgekommen auf Kreise natürlich keine anfangs nur in den Knoten derselbe sein dann dann habe man geschlossen Hamburg erst einmal und geschlossenen Pfad ich denke das ist wenn man sich das vielleicht Normen und nochmal genau Unruhe anschaut zu Hause keine große Sache das zu verstehen was hier abgeht so jetzt sind wir schon bei Zeugen oder sehr Kurt auch da ist die Literatur nicht ganz einheitlich ob sie von Zirkel oder es heikel Circle oder sehr gut sprechen und unter welchen Umstände gerichtet gerichtet aber da das alles mit mit The unten M I Ü laut anfängt ist eigentlich auch egal sei Kristall gezirkelt alles ist selbe so so ein Plus Work also letztendlich das was hier ist ein 1 ein Zeuge der eben nicht Knoten wie hier noch mehr enthalten kann außer dass er sich am ins Knoten wieder schließt das N Knoten leicht dem Alltag so ist so ein wichtiger der Begriff der unser folgen würde einer der Gründe warum wir dieses Büro wohl noch viel gemacht haben ist der Begriff SC wenn ein Graf keine Cycle enthält dann heißt es wirklich für ungerichtete kennen Sie das SEG-2 wollen oder oder oder in einer stehen disjunkte Mengen Menge von Bäumen Wälder ja wenn sie wenn es sein muss comma denn da ein Baum ist dann ist das im und Fall gerade ist die korrekt und er so zyklisch eben gerichteten Fall ist es ein bisschen komplizierter aber das ist eben keinen keinen gerichteten keine orientierten Züge gibt damit kann es immer noch natürlich so sein das ist im zugrunde liegenden ungerichteten Grafen gibt so zum Beispiel ja das ist ein zyklische gerichteter Graph aber der zugrunde liegende und Gerichte gab es natürlich nicht azyklisch in diesem Fall aber trotzdem würde man von azyklisch retten das eine der wichtigsten Grafen Klaus überhaupt für die Anwendung in der Praxis so das ist manchmal wichtig mehr wenn Sie einen Pfad oder Züge haben des eigentlich genau gesagt bei exakt einer Problemstellungen wichtig nämlich Sohn Züge zu finden wir sagen es bei dem das aber selten Gesang typischerweise trauen im Deutschen und im Englischen Anatolien wenn ein Mathematiker hatten wieder der hieß Hamilton und und der Grund dafür warum man sich aus praktischen aus so praktischen sich damit befasst ist das eines der wichtigsten praktischen Probleme den schönen Namen TSB oder China Gsells Basenpaaren oder Handlungsreisen Problem hat sie haben sie haben keine freie Tafel 5 so sie haben zum Beispiel irgendwelche Punkte in der Ebene oder in der industriellen Fertigung beispielsweise bei Auto für Automobilfertigung sie haben diverse verschiedene Punkte auf der Karosse und sie wollen es mit dem Roboterarm alle diese Punkte so in einer Reihenfolge dass die dass der Gesamt weg nach irgend eine Definition von Weglänge minimiert wird weglegen muss nicht unbedingt wirklich die optische länger sein wenn sich vorstellen Roboterarm der hier irgendwie Schweißarbeiten auf der Karosserie an verschiedenen vordefinierten Punkten leistet dann wird der 1. Mal nicht nicht unbedingt gerade geht ich Karosserie durchgehen können sondern mussten Bogen gehen und wir sicherlich eine Beschleunigung abbremst fast dabei haben daraus würde sich dann die länger in also die Zeit Dauer und von hier nach hier zukommen berechnen was wir hier haben ist ein Herr Mehdorn China kreis der jeden jeden Anlaufpunkt wohl Schweißarbeiten Lötarbeiten oder irgendwas zu tun sind genau einmal berührt so hier sind es noch mal ein bisschen abstrakter der ist nicht einmal Tonch dieser Kreis aber dieser Kreise sein und ich der geht hier einmal so herum betrifft trifft jeden blutarmer nicht jeder rauf natürlich habe ich jeder Graf ein Herr mit schon Kreis aber zum aber hier in der Situation geht man typischerweise raus dass sämtliche Kanten zwischen 2 Anlaufpunkten vorhanden sind dass man von jedem sich jemals dieses kommen kann warten Wollschläger auch mit allen möglichen kann und dann hat man natürlich auch jederzeit Sonne kreist so
das ist jetzt eine einfache Sache die hatten haben sie mir geht so auch schon kennen gelernt die habe ich jetzt auch schon den Begriff mehrfach verwendet das hier ist ein nicht zusammenhängender Graf und die ein ungerichteter nicht zusammen Graf weil sie sehen dass es zur meines Komponente ich glaubte nächste Begriff ist genau Connected comma ohne zusammen es Komponente das ist eine zusammen es Komponente das hier ist eine das hier und das hier 4 Zusammenhangs Komponenten haben wir hier wenn Sie genau hinschauen ich habe ich habe genug genau genug hingeschaut ich glaube schon da warum gehört das jetzt nicht auf mit den Definitionen also wir doch jetzt gleich fertig mit der Definition oder
das haben uns damals bloß gedacht als wir das alles
also ich glaube wir werden jetzt mal hier ein bisschen das Auslassen was halten Sie davon im richtigen Thema kommen wir kommen darauf ihn wieder zurück sehr verständlich
wenn sich auslassen ich habe das okay für Sie wenn Sie die den ja durch die Folgen durch den wollen wir das auch machen okay Graf gewisse Nationen ist auch Energie des 2 angesprochen worden wahrscheinlich auch vollständig er der entscheidende Punkt ist immer wieder dass das kennen Sie dicker ist eigentlich das beste Beispiel dafür die andern der falschen DKE auch weil das Datenbanksystem und ähnliches angeht von entscheidender Wichtigkeit für für die Arbeit mit einem mit einer Datenmenge ist wiesen die da sind die Daten so organisiert dass die Zugriffs die Zugriffe die man haben möchte dass die möglichst effizient sind ja bei Datenbanksystem ist ist eines der Hauptthemen dass auch hier Algorithmen und Datenstrukturen 1 ab dem Tag Struktur ist ja nichts anderes als denken Sie an beispielsweise Hashtabellen das ist da Szenario man will einfügen Wandel finden und was ist die beste Datenstruktur wenn man vorher weiß wie viele Element das am Ende haben wird er und man hat die Beine Operation einfügen finde wird man in der Praxis nicht dass das Essen stabile finden was ein Beispiel so wir werden natürlich viel über die Performance von Graf Algorithmen also Laufzeit ist das das ist ist keine artistische Performance oder so etwas von der Laufzeit der Algorithmen reden und die hängt natürlich sehr stark davon ab offensichtlich das haben Sie auch schon er G 2 kennen hängt sehr stark davon ab wie die Daten repräsentiert sind Beispiele sind etwa beim also muss man da extra dass man eine Khieu einsetzt für die Knoten die man die immer noch zu bearbeiten hat oder beim also vom Primus selbe dass man sowie Datenstruktur Mittel rhythmischen Aufwand beispielsweise verwendet und nicht einfach primitiven errei- oder so etwas so deshalb werden wir natürlich kurz auch ein bisschen was sozusagen wie wir Grafen repräsentieren natürliches verschiedene Möglichkeiten Grafen zu repräsentieren ob wir wir werden von der werden wird wir haben natürlich nie das Problem dass man schnell Zugriff hat sondern auch die Frage die das Problem ja dass wir natürlich auch nicht beliebig Speicher verschwenden wollen wir viel Speicherplatz also da Speicherplatz kein so großes Problem mehr aber es gibt viele Situation wir werden leicht auf zu sprechen kommen und es gibt viele Möglichkeiten die man da beliebig Speicher verschwinden kann und sich damit natürlich die Laufzeit verschlechtern kann wenn sie wenn sie für eine kleine Menge Zutaten so sprechen riesengroße Speicherplatz verschwenden Sie und Problem wenn Sie hat sich das alles nicht mehr im Hauptspeicher halten können oder in Cash so große Grafen was in großer Graf ist hängt von den Anwendungen hat es gibt viele Bereiche da wird man erst dann von dem großen Grafen wenn Sinne Milliarden kann halt nur so geht in manchen Bereichen ist es schon großer Graf also beispielsweise hier ist es schon mehr als auf große Graf wenn sie ein paar Dutzend solcher Stellen haben haben Sie auch schon ein Strang zu knabbern so ein wichtiger Punkt wo man über eine dafür befassen ist in in vielen Anwendungen aus der Praxis sind diese großen Grafen sehr dünn diese in der dünn besetzt besetzt sagt man weil die Matrizen dünn besetzten das war er ich will Ihnen einfach so Beispiel geben wenn Sie wenn Sie ein Netzwerk in der in der in der Ebene haben beispielsweise Verkehrsnetz Werkstraße Netzwerk ja sie können Straße sehr vorstellen was Navi drin ist die Kreuzungen und Einmündungen sind Knoten ende von der sage das ist natürlich auch Noten und zwischen zeigt dass der Strasse Apps Schnitt zwischen 2 Knoten seine kannte kann sich vorstellen okay wenn wir mal Brücken und Tunnel außer 8 lassen dann ist Sohn Graf kreuzungsfreien neben eingebettet also Sie haben gerade Brücken und Tunnel um keine also um keine Kreuzungen zu haben in dem Sinne dass eine Kante zwischen 2 Knoten so geht und eine Kante zwischen 2 eingeht geht so und hier kreuzen sich ja kreuzungsfrei eingebettet in der Landschaft wenn man es keine solchen kreuzungsfreien wenn es keine solchen Kursen gibt wenn sie das tatsächlich so eingebettet haben den man dann diesen Grafen ein Beispiel Springorum meiner er den Plan im Deutschen sagt man mich noch geplättet aber das es scheint mir nicht sehr sinnvoll zu sein also danach können hier loslegen beinah könnte zum Beispiel ist das hier zum Beispiel dann aber Graf sich zeichnen ne ne Ebene oder ohne Kreuzung nicht viel anderes Beispiel geben dass sie zunächst mal aus wie nicht planar Graf ist aber dennoch ein kleiner darf denn sie können den Grafen hernehmen und zum Beispiel so zeichnen 6. derselbe Graf ohne Kreuzung ihren Kreuzung Gremien sind keine kotzenden so sind danach auf so was Sie da aber bei kleineren Grafen wissen das wollen wir jetzt hier nicht beweisen ich weiß nicht ob es dann später nochmal kommt ist ziehen aber einfach nur mal die Anzahl der Kanten ist höchstens 3 x Anzahl Knoten minus 6 also höchstens Faktor 3 mehr sie können sich drehen und wenden wie sie wollen sie Klinikring keinen anderen Grafen dessen kann keine Zeit größer als diese Abschätzung ist das bedeutet wenn Sie sich jetzt vorstellen sie haben 1000 Knoten also jetzt in der Situation im Straßennetz haben 7 weil sie nicht 10 tausende 100 Tausend Knoten 10. aus auf jeden Fall das heißt also Sie haben 10 Tausend loten das bedeutet potenzielle könnten sie Größenordnung 10 Tausend Quadrat kann sie haben wo sind wir dann da ungefähr nach 100 Millionen ja nicht 10 Uhr 14 noch 800 Millionen aber was Sie effektiv haben können dass wir maximal 3 mal 10 Tausend 30 Tausend das Unterschied nicht wenn sie Platz reservieren für 100 Millionen potentielle kannten aber Sie wissen von vornherein dass sie höchstens 30 Tausend Karten haben werden egal wie sie sich drehen und wenden dann erscheint es doch als einen sehr starker unnötige Verbrauchern Speicherplatz so und genau deshalb genau wegen solche Sachen weil es eben die typische Situation bei großen Grafen ist ja auch bei anderen Situationen ich weiß nicht viel einige von ich weiß nicht ein Kapitel in ihren betrat man auch zur CAD-Modell also Modellen und somit Dreiecken und fällt mit dem er das haben Sie auch Winword schon mal irgendwo gesehen und auch das ist ein Beispiel dafür ist etwa das des dass diese Grafen sehr ersetzbar sind sehr sehr dünn besetzt es habe Quarterdeck also quadratisch wäre schon so was passieren kann und weit weit unter quadratisch Sie kennen das von Zuber polynomial superexponentielle Subkow drahtiges natürlich das dasselbe ich muss mal gucken wie haben wir haben um halb 2 angefangen nicht das was wir machen sollen und vor uns okay
so natürlich wie üblich Informatik es gibt es nicht die eierlegende Wollmilchsau Auto eierlegende Wollmilchsau ist jetzt eine eine salopp umschreiben von des englischen Worts keine Keller Stein der Weisen oder so etwas sagt man manchmal auch im deutschen dafür ich ich weiß es nicht ob es nur finde wörtlich übersetzen gibt so man muss also bei jeder Anwendung schauen was man da am sinnvollsten macht und dafür müssen wir uns ein paar verschiedene die Standard Repräsentationen anschauen haben das ist glaube ich ein klein wenig schlechtes Englisch der konkret scheues geht aber konkret heißen dass der betont das bisher liegt Scholz würde ich glaube ich eigentlich eher einsetzen wollen ja jemand hier der sich berufen fühlt mich im englische so korrigieren okay wieder senken so hängt immer davon ab was wir eigentlich machen sollen interne PALplus die die beabsichtige Zweck und die Anwendung so wir müssen uns natürlich Gedanken darüber machen ob der Graf ein wahres oder parallele kann passieren können weil nicht alle Grafen Repräsentationen damit umgehen können dass verbale könnten haben sehr wichtig ist der Graf statisch das die Algorithmen die sie Energie die 2 kennen gelernt haben kürzeste Weg minimal spannender Baum oder ähnliches die ändern den Grafen nicht die fügen den gar keine Knoten soll man keine Knoten weg führen keine Kanten einen dem keine kann weg sollen sie machen was mit haben wir sie setzen zum Beispiel Küste Wege setzen wir Distanz Lebens oder berechnen Fahrer oder irgendetwas aber sie ändern den Grafen nicht war hier auch Algorithmen finden die den Grafen ändern wir hatten das Beispiel mit der 1. Bälle eben der stabile funktioniert sehr gut wenn sie Elemente nur einfügen wollen wenn sie vorher wissen wie viele wenn man das in wenn sie alle einfügen und finden wollen aber wenn sie anfangen wollen einfügen und löschen dann sind Hashtabellen vermutlich nicht mehr man kann es noch umbiegen dass man auch in mit 1. Band arbeiten kann aber wahrscheinlich nicht mehr die richtige Wahl so und wie wichtig es ist ist der Speicherplatz Konsum werden eben mit dem Beispiel maximal 10 Tausend kannten können seien aber wenn man Platz reservieren will für alle nur denkbaren die möglicherweise vorkommen kannten dann hat man plötzlich Platz reserviert für 100 Millionen die für 30 Tausend ja also das ist ein Unterschied der beispielsweise bei einem Navi also auf wir haben auf Ihrem PC was wahrscheinlich kein Unterschied machen aber in ihrem Navi möglicherweise schon denn so was werden wir so alles zu B für Operationen haben in einem nicht statischen Szenario also wo wird hat sich den Grafen ändern was heißt der Graf wird geändert dass wir Knoten einfügen Knoten löschen in solchen riechen das wir kannten einfügen kann wenn wir ein Knoten löschen der National natürlich auch die dazu in siedendem kannten mit logisch zu sehen die in der Luft manchmal selten aber manchmal ist auch wichtig dass man sehr effizient testen kann ein Element aber eine könnte drin ist in einem für in einem Grafen gehen Grafen dann das kennen Sie durch das von Alt und wenn der GT 2 dass sie zum Beispiel bei Christel Wege da extra sie nehmen sich einen neuen Knoten her und gucken sich alle Nachbarn an ob deren Distanz werde sich ändern durch das bedeutet jeder welchen auf alle Compiegne überrollt auf einer und sie nehmen sich ein er sehe man sich vielleicht noch eine also muss man da extra in jeder Iteration man sich einen Knoten mehr und die Knoten in der in der die noch nicht bitte er den der nicht beendet worden sind und Sie bitte durchlaufen alle Knoten und die Knoten für die sich der Distanz das lebe dadurch ändert dass sie dass sie versuchen über den hier das über den hier schauen die fassen sie alle an oder vielleicht über die raus rausgehen dem Fall bei der Xtra wenn sogar nur die rausgehen kann die reingehen kann sie natürlich nicht wenn sie gerichteten trafen am kürzesten Wege können Sie natürlich genauso gut auf und Grafen haben das heißt also beide Richtungen dass er so Norden Aurichs Horste darf nicht erschöpfend Chef verschärfen gibt im englischen 2 Worte Exhaust S und X raus denke ich das Haus denn es erschöpfend im Sinne von Ich bin jetzt kaputt Pickshaus der Fall ist im Sinne von erschöpfende Aufzählung also das das englische etwas genau und das deutsche der Sieglinde schon Sache sicher sein was ausschreiben damit okay nehmen die so das sind so die Operation die man die wir typischerweise verwenden werden das werden sie dann immer wieder bei den Algorithmen sehen wie ich weiß nicht wie Sie das sehen aber ich finde die Luft ist ein bisschen schlecht dran Fenster aufmachen das schon sogar draußen morgens auch mehr ist paar Minuten Sie dürfen sich auch gerne beteiligen werden wenn wir schon Teil Raum haben dann sollte dennoch ausnutzen so das sind die Operation mit denen wir jetzt so ein bisschen verschiedene Grafen oder sentation noch diskutieren können was die Vorteile wie es die Nacht der sind eine Grafen Repräsentationen ist am Beispiel der in ja wir gehen gleich zum Beispiel am Beispiel dass sich sowas immer am einfachsten erklären also warten Sie mal hier ist davon es gar kein Beispiel das so oder so aber na gut dann dämmerte es wir nehmen zuerst den Fall vor mit dem Beispiel immer ändern Sie nicht dran wenn ich aus Versehen jetzt in wie will denn immer gleich zu dem war zu dem Fall wo es kein Beispiel gegeben wurde zurück so was eine grundlose Cents Matrix sollten sonstige D 2 kenne egal bei wem sie die Idee 2 gehört haben bin ich mir ein sie haben eine Magd eine quadratische Matrix Knoten Kreuzknoten die es einfach nochmal wird mit 1 bis 5 4 und Sie haben eine die Kante 1 2 finden Sie beispielsweise wieder hier in der Zeile 1 Spalte 2 und die Kante 4 2 finden sie wieder wo wenn Sie die jetzt wieder 4 2 ja genau hier genau hier finden Sie die wieder und der Knoten aus dem Piloten 5 geht nix raus und das sehen Sie daran dass Sie alles neuen sind ein einfaches Prinzip und hier schlägt schon diese Bombe zu von der ich gesprochen habe ja hier reservieren Sie einen Speicherplatz einen Abrissantrag für jede mögliche kannte und das bedeutet dass sie dass sie eben CR 100 Millionen 10 Tausend 13 10 Tausend Einträge haben und nicht obwohl sie wissen dass wir nur 30 Tausend Einträge sein maximal die nicht nur sind so aber das ist auch nur wenig Übung werden zu Anfang wie gesagt als wir angefangen Gare Präsentationen es ist zum Beispiel wichtig ob wir müssen vorher nachdenken ob wir parallel oder nichtparallele kannten haben in dem Fall können wir parallele kannten nicht nicht behandeln wir können müssen so wir sie zählen diese Stelle aber spätestens dann wenn wenn sie hier nicht einfach nur 1 haben als Indikator soll keine der sondern vielleicht in Gerichten Kantenlänge oder so was können sie es nicht mehr waren also dass dieser Darstellungsweise von vornherein nur
sinnvoll für sehr dichtbesetzt Grafen bei denen es keine Parallelen Kanten gibt so dann gehen wir zurück zu dieser Knoten kannten den sie den Smart wissen sogar Beispiel selber basteln haben du so dass ich aber endlich mal ein Stück weiter am Ende um in dabei hat mir Hausmeister vor einiger Zeit gesagt dass es gar keine Folge könne mehr gibt das sie nicht aus wie ausgelegt wird na gut Knoten kannten in sie das Matrix in dem was wir um den Grafen mehr wir machen jetzt relativ einfachen Grafen so vielleicht das wieder 1 2 3 4 so und die Kanten sind aber die bezahlt nicht mal so A B C D E dann haben wir es ist hier was sein was in Spalten also Zeilen sind Knoten das heißt also 1 2 3 4 und Spalten sind kannten A B C D E und sie haben bei hingerichteten Grafen für diese Kante von 2 nach 3 jetzt muss mal gucken wir hatten eine Wahlmöglichkeit wie Roman das definiert für outgoing eine 1 plus 1 und für ihn kommentiert 1 minus 1 also bei der 2 hat die Kante C 1 plus 1 und bei 3 hat sie eine minus 1 und ansonsten Nullen und die kann aber hat von 1 geht von 1 nach 2 habe ich das ist richtig und ich das ist falsch rum mache outgoing ist plus 1 geht aus einem France und geht nach 2 Reihen der Rest ist 0 B kursiert muss ich jetzt zwischen klären wie geht von 1 nach 3 hat 1 plus 1 sie melden sich wenn nicht mehr lesen können sie haben wir die von 2 nach 4 plus 1 ist minus 1 zu 0 0 und E von 3 nach 4 plus 1 minus 1 0 0 auch immer noch ein Schema mit sehr vielen Nullen dran okay und Sie sehen aha das ist aus vom 1. das muss ich mir noch überlegen ob ich dem zustimme war das diese Darstellung nur für theoretische Betrachtung nicht man ins nicht für für reale Anwendung Implementationen sinnvoll ist wenn ich nicht irre ich habe nicht gesagt dass er gerade mal ist hallo ich habe gesagt dass es nur in spezifischen Situation sinnvoll ist ja also ich weiß ich weiß ich vielleicht gibt es eigentlich Situationen denn das tatsächlich die die Darstellung der Wahl ist mir fällt es spontan die Zahlen aber so das haben wir jetzt alles soweit gesagt was steht hier ich helfe das deutliche forme ich Neubauten arg zum Beispiel verkannt ihrer Länge aber das haben sie Energie die 2 immer so gelernt dass hier eben keine 1 steht sondern dann entsprechen die Länge und wo keine kannte steht keine nur soll nun endlich zum Beispiel in und so wo war ich stehen geblieben und sie ja genau das kennen Sie dass man dann hier unendlich setzen würde für kann die existiert und die länger für existierende kannte es gibt auch andere Möglichkeiten der steht hier zu sich Informationen durch Information länger Kosten Kapazitäten wir wenn später mit Kapazitäten und kann zu tun haben wenn es darum geht Flüsse durch Grafen durch zu jagen aber dass man dann vielleicht zu sätzliche Matrizen die dass man das alte kann dass man das zu sich noch separat speichert in der weiteren Matto-Sih genauso aussieht oder auch das ist sicherlich oftmals sinnvoll dass wir 0 Eintrag wirklich als in scharfer etwa als als N NUR allen er nehmen oder in plus bis dann wollt und und wenn die Kante existiert dann ist die Informationen ein entsprechenden Objekt geparkt also keine Panne sondern in bei deren existiert das Objekt zeigt auch dass es eine typische sation wenn sich jeder kann der komplexe Informationen haben dass sie diesen Komplex Information in eine kann dienen Attribute Klasse parken und 0 Pointer in der Matrix zeigt an dass eben diese kannte nicht es geht in dem Gespräch noch keine Information hat ja nicht das beste effizient nicht das einmal eben gesehen Iterationen ist natürlich auch immer ein Problem wir müssen wir müssen wir ohne unheimlich viele Nullen in der ihren das kann ich gut sein für die Laufzeit also im großen ganzen Arbeiter Cents Matrizen nur für sehr dichte Grafen es gibt manche Anwendungen haben Sie kennen Beispiele so wenn fort oder Floyd war schon solche also alle Gründe für und Perschau das passt diesen am Anfang ziemlich dünn was ein war der Graf ist aber wenn sie dann schrittweise dann die Idee dass die Matratzen Elemente der abändern bis sie am Ende des die Wege haben dann wird es natürlich immer dichter dann wird es immer weniger Nullen geben das ein Beispiel dafür wusste also ab wenn man fort und unverwandt also an der Schloßpassage Beispiel dafür wo er der Zins Matrizen sehr sinnvoll sind bei den sich das mal überlegen schneller als in der Winsener zweidimensionale Matrix können Sie seit gewöhnlich implementieren und sie will da sie am Ende eben jeden jede Matrix Eintrag tatsächlich als die Länge eines Christen Weges von einem Club zum anderen haben bauen sich um Speicher das auch keine Gedanken zu machen der spreche wird es bei dieser kubischen Problem Facharzt so agiert im Westen ist in meisten Fällen doch das was man verwenden würde sie haben zum Beispiel ein erregt von Knoten wenn die Quoten Menge sich nicht ändert wenn die Quoten in sich sich ändern wenn Sie einfügen und löschen Oper Knoten haben wollen in einer bestimmten Anwendung wenn Sie das da brauchen dann werden Sie vielleicht hier keine erwei- von Knoten haben sondern sie werden eine Datenstruktur haben die einfügen löschen erlaubt letztere sich Baum oder was auch immer die kannten die aus einem Knoten raus zeigen die sind hier so als Minister organisiert auf der einen Seite haben Sie dann natürlich mehr Speicherplatz verbraucht weil sie wissen eine Listen Struktur diese diese bräunte hier Kosten auch Speicherplatz aber oft andern Seite haben Sie eben nur für die echten real existierenden kannten diese diese Listen diese diese Einträge und diese Speicherplatzverbrauch so dass in den meisten Fällen im Endeffekt dass die kompakteste Form sie kann das noch kompakter machen wenn der Grafs denn sie wissen der Graf wird gar nicht gerne zum Beispiel bei kürzesten Wege Berechnungen das sollte der Graf tunlichst nicht währenddessen geändert werden er dass sie das auch nicht machen sondern sogar zu den Erreger machen schneller geht es dann gar nicht mehr und kompakte auf Speicherplatz will
es auch gar nicht mehr manchmal aber bei so was wie die kürzeste Wege berechnen ist es immer nur sinnvoll von der Kante vom Schwanz zum Kopf rüber zu gucken also in Orientierung der kannte aber wir werden auch eine Situation sehen in denen ist beides wichtig ist in der einen in die Richtung der oder die Unbekannte als auch in Gegenrichtung und in dem Fall macht das durch das sind beides beides zu haben die rausgehen und die reine jeweils als wir eigene Liste von jedem Knoten aus Zivilisten lenkt lässt typischerweise weil man bisher immer nur von vorne durchgehen bis man zu den entweder durch einmal wie wir schon wie es begrüßen sowie oder durch den bis man die keiner Gewohnheit mit der Maus anfangen okay dass das was ich eben sagte meist wenn sie wenn sie wissen dass die Knoten Menge sich nicht ändert in ihren Algorithmus da macht es Sinn die Kloten hier als NRW zu speichern wir falls wir genau der Vorbereitung von heute ist mir das angesehen habe bin ich über diesen Satz ein bisschen gestolpert wir haben wenn wir auch könnten einfügen und löschen wollen nicht nur finden wollen nicht nur durch den wollen in unserem eigenen Sender Algorithmus das will auf gut deutsch wir wollen sich aber auch und was soll das dann sind doppelt verketteten Listen sollten sie aus der GD 2 auch kennen wer kann die nicht okay also nach vorne und nach hinten jeweils ein Pointer aufs nächste man und was von den er meint nicht das funktioniert natürlich nur dann in konstanter Zeit wenn Sie diese wenn Sie dieses Wissen Element das zu dieser kandidiert nicht erst von vorne nach hinten suchen müssen sondern wenn sie gleich wissen wo das ist können Sie haben es hier hatten die einzelnen Knoten oh und haben jetzt hier so eine da wir sind lässt und wenn Sie sich wenn Sie irgendwie aus irgendeinem Grund wissen dass es bei manchen Algorithmen tatsächlich der Fall das die Karte die Sie löschen wollen dass sie dann Pointer draufhaben von außen her dann ist es überhaupt kein Problem diese kannte in konstanter Zeit zu löschen ja bei war einfach verkettete Listen haben Sie das Problem das kann noch dunkel ändern sich vielleicht einige 2 sie brauchen ja dieses Element und dann diesen Pointer hier mit diesen poltert dann dieses Element was Sie aus den Koppeln und zu löschen also müssten sie beide einfach verkehrten müsste dummerweise was falsch Element erreichen müssen vorne dahin gehen um das zu erreichen aber er zur Modefarbe hier also hatten Sie mal hier was auf Arbeit sollen was Sie stattdessen tun können jetzt ist wenn Sie diese genannt haben dann haben Sie über den Point auch dieses Elements und dann haben Sie diesen Pointer das heißt über dieses Element zack können Sie Obst nieder welche nicht in denn verbiegen und den farbigen einfach versehen haben hin verbiegen Händen verbiegen und kann das hat sich in konstanter Zeit machen müssen nicht die ganze letzte durchgehen um dieses Element zu haben das steht hinter diesem Satz setzt aber voraus dass wir in einem Algorithmus sind der in dem vor meiner kann schon wollen von außen her gab heute bekannt ist dass das das Element ist in der da lässt dass wir für diese kann haben dass wir das deshalb wollen so wissen aber Sensation im Gegensatz zum Art unseres dazu unerlaubt parallele könnten wir 2 parallele kann man mal mit 2 einfach 2 Listen Elemente drin mit denselben Inhalt fertig Interaktion einmal durchgehen fertig es ist ja nur ein Listen entweder real existierende kannte drin das heißt also wenn die die Laufzeit ist die Länge der der der letzte dieser Daten die kann gespeichert sind das genau die Anzahl der Kanten die ausgehen und damit es einmal durchgehen genau in den eine Anzahl der Karten die wir sehen wollen besser geht es natürlich nicht und ja ja genau wenn sie das ist noch ein interessanter Punkt bei manchen Algorithmen sie wollen vielleicht das ist hier 3 und das ist 5 und das ist die Ehe das ist die Kante die auf 5 zeigt und hier haben Sie irgendwo trennen eine kannte die auf 3 zeigt ja in manchen Algorithmen wird es interessant sein Fluss Algorithmen die später betrachtet werden von der könnte auf die zu kommen also im Grafen sich das dann so aus 3 und 5 von der Kante auf die zu kommen von der kann doch die zu kommen dazu könnte man hier jeweils dazu sich Informationen dann so einen Pointer so rum und einen Pointer Sohn zu sehr sich speichern und hat sofort unmittelbar Zugriff das ist hier das was mit dem Wort der melde melde Pointer melde im englischen Essen umgangssprachliches Wort für Kumpel Freund Keule wie sowas so erlauben natürlich zu viel Zusatzinformation natürlich gemäß ist wenn man alles mögliche Information einpacken haben Sie einige die 2 gesehen so aber ich habe aber keine Lust mehr auf Leute auf andere Grafen Resignation und das ist auch langsam Zeit dass wir zum Ende kommen ich hoffe wie auch wenn wir uns heute im Wesentlichen bei Definition aufgehalten haben noch keinen einzigen Algorithmus gesehen haben und ein ganz klein beweist mal gesehen haben ich hoffe ich konnte Ihnen schon ein 1. Einblick geben wie das hier sein würde die GT 2 hat ihn ja auch einen gewissen Einblick gegeben ich würde mich freuen wenn möglichst viele von ihnen er sich dafür entscheiden würden diese Veranstaltung durchzuziehen nochmal zur Änderung Wengen ist anzuraten ist sich intensiv mit den Übungsblättern zu befassen und zwar möglichst nicht erst während des Übungs- Termins dann passiv sich das alles vor rechnen zu lassen sondern sie haben wesentlich mehr davon Achtung Prüfungsverband sie haben wesentlich mehr davon wenn Sie das sich vor dem der Abgabetermin intensiv auseinandersetzen und tatsächlich auch etwas abgeben sie brauchen keine Angst haben dass sie sich dann über mir mit ihrer Abgaben so weiter der zum was einiges gewohnt also kein Thema es gibt keine dummen Abgaben es gibt nur die Dummheit nicht abzugeben gut mit diesem Wort zum Sonntag möchte ich Sie für heute entlassen der 1. Termin ist natürlich auch erst dann nächste Woche nicht diese Woche da neues abzugeben haben nächste Woche müsste glaube ich nach dem Terminplan schon des 1. muss notwendig sein dass ich nicht ne ist noch nicht völlig keine Sorge sonnig vielleicht aber Sie können sich da schon Kuchen einige ob sie nicht einige Begriffe die sie auf dem Übungsplatz sehen wiedererkennen im Lichte der Vorlesung heute ja ansonsten ich mich freuen Sie nächste Woche wieder zu sehen bis dann
Loading...
Feedback
hidden