Download e-book for iPad: Algorithmische Graphentheorie by Peter Läuchli (auth.)

By Peter Läuchli (auth.)

ISBN-10: 3034856350

ISBN-13: 9783034856355

ISBN-10: 3034856369

ISBN-13: 9783034856362

Show description

Read Online or Download Algorithmische Graphentheorie PDF

Similar german_12 books

F. Kelberine, B. Locker, J. P. Bonvarlet (auth.), Dr. med.'s Ellbogenchirurgie in der Praxis PDF

Einen praxisorientierten Überblick über die heutige Ellbogenchirurgie zu geben, ist das Anliegen dieses reich illustrierten Buches. Basierend auf der Anatomie, Physiologie und Pathophysiologie des Ellbogens entwickeln die Autoren therapeutische Konzepte. Moderne Untersuchungsmethoden werden ebenso dargestellt wie die Langzeitresultate der konservativen und operativen Verfahren.

Additional info for Algorithmische Graphentheorie

Sample text

Es wird dabei auch klar, dass fUr die Bildung der Geriiste genau die zusammengezogenen Kanten zu sammeln sind, wabrend man die gelOschten Kanten vergessen kann. 3 Konstruktion eines Minimalgeriistes Gegeben ist hier ein schlichter zusammenhangender Graph G und eine Kostenfunktion w : K -+ R+, die jeder Kante u ein positives Gewicht w(u) zuordnet. Gesucht ist eine Geriist(Kanten)menge T ~ K mit minimalem Gesamtgewicht w(T) = LUET w(u). Ein so erzeugtes Geriist heisst Minimalgeriist. Es lassen sich leicht Anwendungen finden.

Anwendung der Theorie auf Spiele Mit den bisher eingefiihrten Begriffen und Siitzen lassen sich einige Aussagen iiber Spiele machen. Einem beliebigen Graph G liisst sich niimlich das folgencle Spiel zuordnen: Jedem Punkt von G entspricht eine Spielposition; aus einer Position x sind als Ziige genau die Ubergiinge zu einem y E r+(x) moglich. Gewinner ist der Spieler, der den letzten Zug ausfiihrt, indem er in einen Punkt fahrt, cler keine Nachfolger 34 KapiteJ 5. Fiirbbarkeit besitzt ("Endpunkt").

1 Der Graph Gist genau dann 2-farbbar, wenn er keine Kreise ungerader Lange enthlilt. Beweis: Sei G 2-farbbar. In einer 2-Farbung folgen in jedem Kreis abwechslungsweise Punkte verschiedener Farbe aufeinander. Somit ist die Lange des Kreises gerade. Seien umgekehrt keine Kreise ungerader Lange vorhanden. 2. Breadth-First-Search 27 erhalten die Farbe 0, die iibrigen die Farbe 1. Dies ist tatsachlich eine 2-Farbung; denn angenommen, die adjazenten Punkte b und c hat ten dieselbe Farbe bekommen, wiirde der Teilgraph, gebildet aus zwei kiirzesten Wegen a-b und a-c, sowie der Kante bc, einen Kreis ungerader Lange enthaIten.

Download PDF sample

Algorithmische Graphentheorie by Peter Läuchli (auth.)


by Daniel
4.5

Rated 4.35 of 5 – based on 36 votes