wir wollen uns in den folgenden beiden vorlesungen mit graphen beschäftigen dabei soll es zuerst um begriffe und datenstrukturen gehen und in der folgenden vorlesungen dann um algorithmen auf graphen wenn man das einordnen das kapitel wir haben angefangen in diesem semester mit listen datenstrukturen sind dann übergegangen zu räumen in gewisser weise haben sich die listen dann noch weiter allgemeiner verzweigt und wir wollen die bäume jetzt noch weiter verallgemeinern beliebige verzweigungen sozusagen zu lassen und kommen dann zu graphen viele dinge in der realen welt können wir mit graphen modellieren hier ist ein beispiel der u bahn fahrplan
von london bzw ein ausschnitt daraus das heißt wir haben einzelne u-bahn-stationen das werden die knoten in unserem grafen sein und verbindungen zwischen diesen stationen das erkannten in diesem k er sieht das ganze ist eine abstraktion von etwas was es real gibt das u-bahn-netz und man könnte natürlich noch mal anders abstrahieren oder anders drauf schauen wir haben einen ähnlichen plan diesmal ein spielplan von scotland yard auch wieder in london navigieren zwischen einzelnen stationen diesmal sind es nicht nur die u bahnen also einzelnen knoten die mit kanten miteinander verbunden sind und was wir hier schon sieht da
wo wir im baum eine hierarchie hatten von jedem knoten in eindeutigen pfad zu wort so hatten also wir hatten in einen ausgezeichneten parteien einen ausgezeichneten knoten die wurzel an der man den baum aufhängen konnten so haben wir hier im graphen so einen knoten nicht im gegenteil so was wie ein netz aus knoten die mit kanten miteinander verbunden sind und genau so genannten grafen auch vorstellen salopp gesprochen stellen grafen beliebige netze von knoten und kanten da das können zum beispiel wege oder verbindungsnetz sein oder allgemein verkehrsnetze das netz der bahn verbindungen oder ein straßennetz oder flugverbindungen
oder wasser rohrleitungen oder elektrizitätsleitungen die dinge miteinander verbinden oder eben auch ein rechner netzwerk all das können wir auf der einen seite natürlich konkret sehen als das netzwerk dass man tatsächlich als ein ding anfassen können aber auch abstrakt als den bahnstrecken plan oder als die straßenkarte im atlas auf dem wir uns orientieren und die uns ja ein abstraktes abbild der realen welt liefert genau sowas werden mit einem grafen modellieren anderes beispiel das world wide web ist ein graf mit dokumenten als knoten und links oder verweisen zwischen dokumenten als kanten bisschen altmodisch und vielleicht mit der
hand besser fassbar literaturverweise in büchern kann ich mir auch vorstellen als einen grafen das einzelne buch ist ein knoten die literaturliste hinten hat verweise zu anderen büchern und stellt auf die art und weise kanten da wenn man so wollen komme hier schon in die richtung von der datenstruktur wie man so einen grafen darstellen können als ein knoten und eine liste von kanten die von diesen knoten ausging das dateisystem auf unserem rechner ist in der regel hierarchisch geordnet also hat eine baumstruktur allerdings kann ich so genannte hard oder symbolik links noch mit einfügen so dass ich
ja verbindungen zwischen beliebigen verzeichnissen herstellen kann oder auch wieder verbindungen aufwärts der hierarchie oder in richtungen die ich mit im baum so nicht darstellen kann in dem augenblick wo ich das mache wird der baum allgemein zu einem graf mit ein anderes beispiel technische sachverhalte wie die elektrische schaltungen oder die entsprechenden schaltpläne oder kompletter für den herstellungsprozess das platinenlayout kann ich mit graphen darstellen wir machen computergrafik da werden geometrische modelle in aller regel mit hilfe von polygon netzen dargestellt jedes polygon wird auch dargestellt als eine menge von knoten die durch kanten verbunden sind und wenn ich
mehrere polygone sozusagen aneinander kleben dann habe ich auch wieder einen grafen der mir ein komplexes geometrisches objekt darstellt mit diesen geometrischen objekten rechnen wir oft aufwenden zb finite elemente methode drauf an unabhängig davon ob wir das in der computergrafik oder in anderen disziplinen im maschinenbau machen um diese modelle darzustellen brauch ich auch wieder das kritisieren meine domäne in der ich rechne zb der ebene durch einfache elemente die auch wieder aus knoten und kanten gebildet werden ich brauche auch wieder einen grafen und schließlich wie eingangs schon erwähnt haben angefangen mit den listen weitergemacht mit den bäumen
sind vom speziellen zum allgemeinen gegangen und die grafen sind sozusagen der allgemein fall von bäumen oder umgekehrt bäume sind spezialfälle von graphen listen spezialfälle von bäume von bäumen und damit natürlich auch von graphen nach diesen beispielen schauen uns definitionen zu graphen an und wir dann hier in der vorlesung verschiedene klassen von graf betrachten da sind einmal ungerichtete graphen auf englisch an directx gerichtete grafen directed krebs oft kurz tykwer oder auch gewichtete grafen englisch weltkriegs wie können wir uns die vorstellen eingerichteter graf ist ein graf wo ich jede kante in beliebiger orientierung und beliebige richtung vorwärts
oder rückwärts durch laufen kann beispiele sind nett rechner netzwerk oder ein straßennetz in dem es keine einbahnstraßen gibt wenn ich zwei rechner miteinander verbindet dann kann ich in der regel vom einen zum anderen wie auch vom anderen zum einen über die gleiche leitung kommunizieren über diese kante kommunizieren nämlich den straßen jetzt ohne einbahnstraßen hat dann darf ich jede straße in beide richtungen durchfahren für gerichtete graphen gilt das nicht da haben die kanten tatsächlich eine vorgegebene orientierung für die straße würde das bedeuten darf einbahnstraßen geben oder für jede straße gebe ich explizit noch an in welche
richtung ich sie durchlaufen da in dem straßennetz wird es nur einige wenige einbahnstraßen geben wir können uns das so vorstellen alle straßen die keine einbahnstraßen sind die muss ich als zwei verschiedene kanten im graphen darstellen eine in die vorwärts mit einigen die rückwärts richtung ein anderes beispiel so eine förderanlage wir können uns vorstellen förderband oder auch ins system flüssigkeiten durch rohrleitungen gepumpt werden das geht in aller regel nur in eine richtung ich kann das förderband und es macht keinen sinn das förderband rückwärts laufen zu lassen das förderband läuft immer in eine richtung das heißt entlang
jeder kannte transportiere ich material von einem knoten zum andern aber eben nicht zurück gewichtete grafen können sowohl angerichtet als auch gerichtet sein für die gewichteten grafen kommt noch dazu dass wir für jede kante noch ein zusätzliches attribut speichern ein sogenanntes gewicht mit dem er bestimmte dinge modellieren können für die förderanlage könnte das zum beispiel eine angabe der kapazität seien also wie viel masse kann ich mit dem förderband pro zeiteinheit transportieren oder für eine rohrleitung wie viel kann ich in einer bestimmten zeit einheit durch dieses rohr pumpen für ein straßennetz das kennen wir aus dem atlas
da ist es oft so dass die einzelnen straßenabschnitte noch mit einer zahl versehen sind die uns die kilometerangabe für dieses straßenstück liefert auch das ist ein beispiel für ein gewicht also straßen jetzt mit kilometerangaben wie ein beispiel so einen gewichteten grafen hier würde das gewicht und eine weglänge eine streckenlänge angeben wenn man das formal machen dann ist eingerichteter graf ein geordnetes paar aus einer menge von knoten und eine menge von kanten diese menge von kanten enthält jeweils zwei mengen von knoten also eine menge mit genau zwei elementen drin jedes dieser elemente geheißen ii und j
ist in der knoten menge enthalten sinnvoll sind hier nur mengen die tatsächlich echte zwei mengen sind das heißt wir haben zwei verschiedene knoten in dieser menge stehen und diese knoten diese beiden knoten spannen eine kante in diesem graphen auf wir gehen hier in der vorlesung immer davon aus dass die mengen endlich sind was anderes macht im rechner auch wenig sind und wieder ist kurz noch zu der bezeichnung die knoten heißen auf englisch notes aber oft auch wörz ex oder im plural wird dieses deswegen haben wir hier für die knoten menge den buchstaben v und tatsächlich
auch in der regel benutzt um knoten zu bezeichnen das einfach die andere bezeichnung wörz ex wird dieses in coral für knoten wer in der computergrafik vorlesung ist der wird den begriff öfter da ist dass der übliche begriff um knoten oder knotenpunkte zu bezeichnen die kanten sind eingerichtet denn in diesen zwei mengen gibt es keine ausgezeichnete reihenfolge also ist nicht gesagt dass ifo j oder jva i kommt das ist immer die gleiche menge und dadurch dass ich fordere dass sie von j tatsächlich verschieden sein muss darf ich keine so genannten schleifen einfügen oder kann ich keine
schleifen modellieren das heißt es gibt keine kanten von einem knoten von sich selber zu sich selber das ist eine konvention die wir hier für ungerichtete grafen eingehen und die man gleich sind die für gerichtete grafen nicht gilt hier ist ein beispiel für einen angerichteten graf mit sechs wird es dieses ex word dieses oder sechs knoten habe ich durchnummeriert von 1 bis 6 die entsprechende knoten menge enthält die zahlen von eins bis sechs ich werde hier in der vorlesung immer zahlen nehmen und knoten zu bezeichnen tatsächlich kann man irgendwelche symbole nehmen um knoten zu bezeichnen meistens
bieten sich zahlen an einfach durch zu zählen aber es ist erst mal nicht gesagt was tatsächlich hier in dieser knoten menge ist wir müssen mit den einträgen nur knoten eindeutig bezeichnen können dann hier die menge aller kannten als die menge von zwei mengen und hier haben wir die menge mit der einst unter 23 die bezeichnet die kante zwischen dem knoten 12 diese kannte hier drei und fünf die bezeichnet und diese menge 3 und 5 die bezeichnet die kante zwischen den knoten 3 und dem knoten 5 ich habe das ganze hier so geschrieben dass ich in
jeder zwei menge die wird die welt ist es die knoten geordnet hat tatsächlich habe ich auf diesen mengen keine ordnung er schreibt sich nun grad bisschen übersichtlicher genauso wie ich diese menge scheinbar lexika fisch sortiert hat auch dass diese eigenschaft gibt die menge nicht her ich habe sie nur der übersicht halber so gemacht weil man es gleich in gerichten grafen ähnlich dann aber als paare sehen werden eingerichteter graf ist auch wieder ein paar aus eine menge von hört dieses und eine menge von kanten eine menge von knoten eine menge von kanten und im unterschied zum
angerichteten graf hat jede kante jetzt eine orientierung das bedeutet jede kante verläuft zwischen zwei knoten und sie hat eine orientierung das heißt eine richtung in der sie durchlaufen werden darf das heißt ich habe hier eine kante von knoten ii zum knoten j und diese kante stelle ich da als ein paar j da wo wir gerade eben in der definition zwei mengen haben haben wir hier jetzt paare oder zwei top da wo ich auf der menge keine ordnung hat habe ich auf dem top in ordnung der erste eintrag bezeichnet den knoten aus dem die kante ausläuft
und der zweite eintrag bezeichnet den knoten in denen die kante hineinläuft die kanten sind also gerichtet für den gerichteten graphen ist es sinnvoll so genannte schleifen zu erlauben was ist eine schleife eine schleife ist eine kante vom knoten wieder zu sich selber die ich entsprechend darstelle als paar an diesem fall dass ich hier explizit zu hier haben ein beispiel für einen gerichteten grafen die menge der knoten ist die gleiche wie gerade geben und die menge der kanten ist jetzt eine menge von paaren also die kante von 1 nach zwei jetzt nicht mehr zwischen den beiden
knoten sondern von 1 nach zwei in diese richtung das ist diese kannte hier und die richtung die orientierung geben in der zeichnung in einer regel an dadurch dass man teil zeichnen also noch eine pfeilspitze dazu zeichnen wenn man jetzt nicht nur von knoten 1 zum knoten drei sondern auch wieder zurück vom knoten 13 knoten 1 gehen möchte dann braucht man entsprechend 2 gerichtete kann die eine von der 123 und die andere von der drei zur 1 hier in dem beispiel sie immer auch eine schleife dass es diese könnte hier die vom knoten 5 wieder zum
knoten 5 läuft ich werde dieses beispiel immer wieder verwenden und dabei auch immer wieder bilder so ähnlich wie dieses hier zeigen was wichtig ist der graf besteht tatsächlich nur aus der menge von knoten und der menge von kanten was explizit nicht codiertes in dieser darstellung das ist ja die anordnung der knoten hier in der ebene um dieses bild zu erzeugen oder das auf englisch layout des grafen ich kann die knoten hier beliebig verschieben es bleibt immer der gleiche graf wenn ich die pfeile mit verschiebt es bleibt immer ein bild das gleichen grafen ich werde versuchen
diese bilder immer so zu zeichnen dass ich kannten möglichst nicht kreuzen also dass es möglichst übersichtlich bleibt aber diese darstellung in der ebene in 2d die darf ich mir aussuchen so wie ich sie will das ist nicht probiert oder dargestellt in der information die den grafen selbst beschreibt das nur die menge von knoten und kann gleich noch der hinweis sohn layout zu berechnen für eine gegebene knoten menge und kanten menge das ist genau das was grafisch bzw dieses top programm als ein teil von grafisch macht das ist das was wir in den code beispielen benutzen
um bäume oder um grafen einfach zeichnen zu können zuletzt kommen wir zu den gewichteten graphen ein gewichteter graf ist ein graf der kann gerichtet oder um gerichtet sein zudem er zusätzlich eine funktion an geben die jeder kannte ein sogenanntes gewicht zuordnet ich nenne diese funktion hier gama und die bildet ab von der menge der kanten auf eine zahl menge ich nehme hier die natürlichen zahlen einschließlich der 0 wir schreiben sollen gewichteten grafen dann oft auch als tribut von knoten menge krankten menge und gewicht funktion auf welche menge ich ja abbilde oder aus welcher menge meine
gewichte oder die werte für die gewichte kommen das hängt von der anwendung ab das können rehe zahlen seien das können ganze zahlen seien das können natürliche zahlen seien in sehr vielen anwendungen sind das nicht negative zahlen bzw das vorzeichen von diesem gewicht kann es spezielle bedeutung haben in dem sinn dass wenn die kanten der einrichtung durchlaufen wird durch das gewicht positiv und in der anderen zähle ich das gewicht negativ wenn ich entsprechenden gerichteten grafen hat mit zwei entgegensetzen kranken dann hätten die betragsmäßig jeweils das gleiche gewicht was da genau steht kommt auf die anwendung an
was wir mit dem grafen modellieren wollen wie gesagt oft ist es so dass die gewichte nicht negative zahlen sind nicht negativ dass die null explizit mit zu hier haben ein beispiel versuchen gewichteten grafen ich habe hier den gerichten grafen von gerade eben genommen wir haben die gleiche menge von knoten und die gleiche menge von kanten und die funktion gamma die gebe ich jetzt ganz einfach an indem ich über jede kante hier den entsprechenden gewichts wert schreibt die gewichte die sind hier irgendwie willkürlich gewählt wie gedacht wie ich kann man repräsentieren ist eigentlich egal ich mache
hier auf der zeichnung in dem ich über jede kante ihr gewicht schreibe also jeder kannte ein gewicht zu ordnen zuletzt noch einige weitere begriffe zu graphen ich definiere das hier relativ unscharf die meisten begriffe können uns sehr anschaulich auch vorstellen und dementsprechend auch recht einfach eine scharfe definition angeben wenn man sie denn brauchen wir werden sie hier in der vorlesung meistens nicht brauchen bzw einige der begriffe wir haben auch tatsächlich nur selten braucht man mit dem teil graf auf englisch ab graf dass es wie der name schon sagt ein teil von einem grafen der dementsprechend
definiert ist durch teilmengen jeweils von den knoten und kann andere wichtiger begriff ist der grat auf englisch die queen eines knotens der grat zählt die anzahl der eingehenden kanten in ungerichtete grafen das heißt wenn ich hier einen knoten habt dann zähle ich einfach wie viele kannten gehen aus diesem knoten raus oder gleichbedeutend für den angerichteten grafen wie viele kannten gehen da rein eingerichteten grafen muss man ein bisschen aufpassen da ist es oft definitionssache was man mit dem grab meint obmann nur die eingehen nur die ausgehenden oder beide zusammen zählt am besten ist man unterscheidet einfach
explizit zwischen in die knie und audrey also der anzahl einbinden und der anzahl ausgehenden jetzt gerichteten kanten hier in diesen knoten 2 kann dir eingehend und zwei kanten die rausgehen wenn man vom gerichteten grafen sprechen dann können wir einen spezialfall definieren eingerichteter graf heißt symmetrisch wenn es zu jeder kannte auch die entgegengesetzte kante gibt heißt wenn ich an einem knoten bekannte zu den knoten j hat dann ist es für jede kante zwischen zwei knoten ins metrischen gerichteten grafen zu dass auch die umgekehrt orientierte kannte im graphen enthalten sein muss so wie wir bäume rasiert haben
werden wir auch grafen traver sieren also durchlaufen und dazu durchlaufen wir eine regel folge von knoten die durch kanten verbunden sind die definitionen sind hier manchmal so manchmal so ich definiert den weg hier als eine folge von knoten die durch kanten verbunden sind das heißt je zwei aufeinanderfolgende knoten in dieser sequenz finde ich auch wieder in der kantenlänge anschaulich bedeutet das dass ich nehme hier den gerichten grafen nicht quasi von einem knoten zum nächsten zunächst zum nächsten entlang der kanten bewegen kann und diese bewegung beschreibt einen weg manchmal wird der weg auch als eine folge
von kanten definiert an beides ist im wesentlichen äquivalent was man für den weg zu lassen ist das so ein weg sich auch kreuzen darf darf sowas passieren wenn ich so in male dann ist das bild jetzt nicht mehr aussagekräftig oder es ist nicht mehr eindeutig dass ich hier tatsächlich so gelaufen bin ich muss es also tatsächlich als eine folge von knoten angeben wenn ich einen weg ab wo die knoten paarweise verschieden sind das heißt es kommt kein knoten in diesem weg doppelt vor dann spreche ich auch von einem pfad den begriff kinder von den bäumen
auch schon gesagt im baum gibt es für jeden knoten eindeutigen pfad bis zum wurzel knoten ich gehe also immer nach oben und wenn ich das macht ist klar dass ich dabei einen knoten mehrfach durchlaufen kann ein pfad ist ein zyklus wohl entschuldigung ein weg ist ein zyklus wenn der anfangs und der entknoten [Musik] gleich sind wenn wir uns hier das beispiel anschauen dass hier wieder weg malen dann haben wir hier einen zyklus zyklus bedeutet ich bin einmal im kreis gelaufen zyklisch gelaufen eingerichteter graf der wenigstens einen zyklus gesetzt der heißt auch zyklisch wichtiger ist meistens
der andere fall dass er für einen gerichteten grafen explizit ausschliessen dass es zyklen gibt so ein kaff heißt auch ab zyklischer graf oder director patrick graf oft einfach nur abgekürzt mit dakota de ag im beispiel auf der folie gerade eben darf einige zyklen von 1 nach 3 und wieder nach 1 von 1 nach 3 und wieder nach 1 von 1 nach 3 4 nach 1 1 1 nach 31 nach 34 eins von drei nach sechs nach 5 nach 3 36 53 und schließlich die schleife dass es auch ein zyklus wenn man so will ich die
hier von knoten 5 wieder zu sich selber zu 5 dieser begriff zyklus beziehungsweise zyklisch und abzüglich ist nur sinnvoll für gerichtete grafen im un- gerichteten graphen kann ich jede kante in beide richtungen durchlaufen und damit kann ich schon in zyklus generieren ich gehe einmal vor und wieder zurück also typisch oder antizyklisch die attribute verwenden wir für gerichtete graf wir schauen uns in dieser vorlesung nur einige wenige wahrscheinlich die wichtigsten klassen von graphen an es gibt noch viele weitere liste die hier steht ist natürlich auch nicht vollständig nur um kurze idee zu geben was auch noch
gehen kann in multi grafen verbinde ich knoten gegebenenfalls durch mehr als eine kante über graphen sind grafen wo eine kante mehr als einen knoten gleichzeitig verbindet das heißt ich muss diese kanten jetzt quasi als mengen von knoten schreiben die zueinander gehören wie gesagt es gibt noch viele mehr wir betrachten das hier in der vorlesung nicht weiter sondern konzentrieren uns auf ungerichtete gerichtete und gewichtete graphen für die gewichteten merken uns da ist noch nicht gesagt hast gerichtet oder um gerichtet ist