Die Mathe-Redaktion - 20.07.2018 06:42 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind Gäste und Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 

VerzeichnisLink vorschlagen Neue Links Meine Links Populäre Bestbewertet Neue Bewertungen Link der Stunde



85841. Link der Stunde.
Einführung in Graphen und Algorithmen:  Populär
Beschreibung: Ein online-Buch, 450 Seiten, aufgeteilt in mehrere .ps-Files. Von Thomas Emden-Weinert et.al.
1 Einführung (51 Seiten, 656kB)
1.1    Grundlegende Begriffe
1.1.1  Partite Graphen
1.1.2  Operationen auf Graphen
1.1.3  Bäume, Artikulationen, Schnitte
1.1.4  Zufällige Graphen
1.2    Die Komplexität von Algorithmen
1.2.1  Entscheidbarkeit
1.2.2  Die Klasse P oder: zugängliche Probleme
1.3    Algorithmische Prinzipien
1.3.1  Breiten- und Tiefensuche
1.3.2  Dynamisches Programmieren: das kürzeste-Wege-Problem
1.3.3  Greedy: minimale aufspannende Bäume
1.4    Die Klasse NP oder: polynomielle Verifizierbarkeit
1.4.1  NP-Vollständigkeit
1.4.2  NP-schwere Probleme und Optimierung
1.5    Zum Umgang mit NP-schweren Problemen: Algorithmen für Independent Set

2 Netzwerkflüsse und Zusammenhang (22 Seiten, 569kB)
2.1    Der Markierungsalgorithmus von Ford und Fulkerson
2.2    Der Satz von Menger nebst Folgerungen
2.3    2-Zusammenhang, Blockstruktur und Tiefensuche
2.4    Die Zusammenhangszahlen

3 Durchlaufbarkeit (13 Seiten, 323kB)
3.1    Eulersche Graphen
3.2    Hamiltonsche Graphen

4 Matching (34 Seiten, 500kB)
4.1    Die Sätze von Berge und Gallai
4.2    Matching in bipartiten Graphen
4.3    Matching in allgemeinen Graphen

5 Färbung (39 Seiten, 1076kB)
5.1    Die chromatische Zahl
5.2    Greedy-Färbung und der Satz von Brooks
5.3    Chromatische Zahl und Taillenweite
5.4    Die Komplexität des Färbungsproblems
5.5    Färbungsalgorithmen
5.6    Kantenfärbung: der Satz von Vizing
5.7    Kantenfärben in bipartiten Graphen

6 Topologische Graphentheorie (58 Seiten, insgesamt 3.886kB, Teil 1, Teil 2, Teil 3, Teil 4)
6.1    Planare Graphen
6.1.1  Ebene Graphen
6.1.2  Die Eulersche Formel
6.1.3  Die Sätze von Kuratowski und Wagner
6.1.4  Dualität bei planaren Graphen
6.2    Ein Einbettungsalgorithmus [Fragment]
6.3    Die 4-Farben-Vermutung
6.4    Graphen höheren Geschlechts
6.5    Der 4-Farben-Satz und Komplexitätsfragen
6.6    Kreuzungszahl, Dicke, Arborizität und Buchdicke

7 Perfekte Graphen (23 Seiten, 314kB)
7.1    Einleitung
7.2    Chordale Graphen
7.3    Vergleichbarkeitsgraphen
7.4    Intervallgraphen [Fragment]
7.5    Graphen mit perfekter Ordnung [Fragment]
7.6    Im Umfeld der Perfekte-Graphen-Vermutung [Fragment]
7.7    Optimierung auf perfekten Graphen [Fragment]

8 Separatoren (22 Seiten, 569kB)
8.1    Einleitung
8.2    Separatoren in planaren Graphen
8.3    Independent Set auf planaren Graphen
8.4    Separatoren für andere Graphenklassen
8.5    Cliquenseparatoren

9 Baumweite (10 Seiten, 206kB)
9.1    Baumweite und k-Bäume
9.2    Optimierung auf Graphen beschränkter Baumweite
9.3    Randomisierung I: Subgraph Isomorphismus [Fragment]

10 Approximationsalgorithmen (42 Seiten, 1067kB)
10.1   Einleitung
10.2   Knotenüberdeckung
10.3   Steiner-Bäume
10.4   Das Traveling Salesman Problem
10.5   Das Zentrumsproblem
10.6   Randomisierung II: Max Cut und Max Sat
10.7   Lokale Verbesserung
10.8   Ein PAS für Planar Independent Set
10.9   Graph Coloring und Independent Set

11 Nicht-Approximierbarkeit (2 Seiten, 86kB)
11.1   MAX-SNP und PCP [Fragment]
11.2   Clique [Fragment]
11.3   Graph Coloring [Fragment]

12 Überdeckungsprobleme (29 Seiten, 427kB)
12.1   Cliquenüberdeckung und Schnittgraph-Darstellung
12.2   Erkennung von Linegraphen [Fragment]
12.3   Primal-dual Approximationsalgorithmen
12.3.1 Der primal-dual Algorithmus der Linearen Optimierung
12.3.2 Hitting Set, Node Cover und Dominating Set
12.3.3 Shortest Path
12.3.4 Das Generalized Steiner Tree Problem
12.3.5 Survivable Network Design mit Mehrfachkanten
12.4   Approximation von Set Cover und Dominating Set

13 Zufällige Graphen und probabilistische Algorithmen (16 Seiten, 273kB)
13.1   Die Cliquenzahl
13.2   Die chromatische Zahl

14 Ein Blick in die extremale und asymptotische Graphentheorie (14 Seiten, 669kB)
14.1   Die Sätze von Turan und von Erdös und Stone
14.2   Fast alle dreiecksfreien Graphen sind bipartit
14.3   Mehr über dreiecksfreie Graphen

A Anhang (20 Seiten, 255kB)
A.1    Grundbegriffe der Wahrscheinlichkeitstheorie
A.2    Hinweise und Lösungen zu ausgewählten Übungen
A.3    Die Grenze zwischen P und NP-vollständig
A.4    Übersicht über Graphenparameter
A.5    Weiterführende Literatur

Literaturverzeichnis (46 Seiten, 335kB)
Entstanden 1996 an der Humboldt-Universität zu Berlin, Institut für Informatik, Lehrstuhl für Algorithmen und Komplexität

Eingefügt am 26 10 2004 Hits: 1356
Selbst bewerten | DetailsUngültigen Link mitteilenUrl/Beschreibung ändern
Kategorie: Mathematik / Graphentheorie


Bisher keine Kommentare



Link in neuem Fenster öffnen  |  Selbst eine Bewertung abgeben



Sind Sie der Besitzer dieser Web-Site? Erlauben Sie den Besuchern Ihrer Web-Seite, diese auch zu bewerten!
 Link auf diese Seite: https://matheplanet.de/default3.html?call=links.php?op=vld&lid=961
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]