## Basic Definitions and Graph Representations

Video in TIB AV-Portal: Basic Definitions and Graph Representations

 Title Basic Definitions and Graph Representations Title of Series Effiziente Graphenalgorithmen WS 2012 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 10.5446/21486 (DOI) Publisher Release Date 2012 Language German

 Subject Area Computer Science 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.
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