Algorithmische Graphentheorie by Peter Läuchli (auth.)

By Peter Läuchli (auth.)

Show description

Read Online or Download Algorithmische Graphentheorie PDF

Similar german_12 books

Rückengerechtes Verhalten

Der rückengerechte 24 Stunden-Tag! Wie liege ich richtig? Wie stehe ich rückenfreundlich auf? used to be sind die richtigen Hebetechniken bei der Hausarbeit und wie sitze ich richtig am Arbeitsplatz? Zahlreiche Abbildungen zeigen wie es geht und präzise Texte vermitteln die notwendigen Informationen und Kenntnisse.

Extra info for Algorithmische Graphentheorie

Example text

B) Im eben beschriebenen Prozess nimmt p bei der Entfernung von u genau dann urn 1 zu, wenn u auf keinem Kreis liegt. v bleibt also genau bei kreisfreien Graphen konstant. 0 Aus dem bisherigen ergeben sich einige einfache Folgerungen, deren Beweis wir dem Leser als Ubung iiberlassen: • Von den drei Eigenschaften: "zusammenhiingend" (p = 1), "kreisfrei" (v = 0) und "m = n - I" sind beliebige zwei notwendig und hinreichend fiir die Baumeigenschaft. • In der Menge aller Graphen mit n fest en Punkten sind (beziiglich der Teilgraphenrelation) die Biiume genau - die maximalen kreisfreien, und - die minimalen zusammenhangenden Elemente.

Man iiberlege sich, warum die Methode fUr gerichtete Graphen nicht funktioniert. Kapitel6 Wege Das Problem, in einem ungerichteten Graph zu zwei gegebenen Punkten a, b einen kiirzesten a-b- Weg (bzw. in einem gerichteten Graph eine kiirzeste Bahn) zu finden, ist eine der klassischen AufgabenstelIulJgen der Graphentheorie. 1 drei repriisentative Algorithmen zur Bestimmung von kiirzesten Wegen (Bahnen) besprechen, in denen wichtige, auch anderweitig einsetzbare Ideen zur Anwendung kommen. 2 die eulerschen und die hamiltonschen Graphen vorzustellen.

Jede Kante wird genau einmal (im ungerichteten Fall zweimal) examiniert: m-Anteil. Somit ist die Komplexitat =O(n2 + m) = O(n2 ). 1 illustriert werden. 1 (Dijkstra) benotigt 8 Durchlaufe der repeat-Schleife, falls aIle von a = 3 ausgehenden kiirzesten Bahnen verlangt werden. Die an diesen Bahnen beteiligten Kanten sind in der Figur hervorgehoben. Die Resultate sind in der folgenden TabeIle festgehalten; insbesondere die Werte von q[x] und vorg[x] am Schluss: 1 2 3 4 5 6 7 8 4 6 1 3 8 5 2 7 q[x] 25 65 0 15 80 40 10 75 vorg[x] 4 6 7 2 1 3 7 x deJlx] = true im Durchlauf Nr.

Download PDF sample

Rated 4.75 of 5 – based on 5 votes