- Titel: Algorithmen auf Graphen
- Organisation: UNI BREMEN
- Seitenzahl: 48
Inhalt
- Algorithmen auf Graphen
- NPvollstndige Graphprobleme a
- Kapitel Graphen in der Informatik
- WARNUNG Graph ist nicht gleich Graph
- Verbraucher Speicher Erzeuger Verbraucher
- Verkehrsuss auf Kreuzungen
- Kapitel Eulersche Graphen
- Wege und Eulersche Kreise
- Einfache EulerschTests zu aufwndig a
- Beobachtung zur Gradgradigkeit
- Beobachtung zum Zusammenhang
- Konstruktion eines Kreises in gradgradigen Graphen
- v e v e v e v e
- Lschen eines Kreises in gradgradigen Graphen o
- Konstruktion einer Kantenuberdeckung fur gradgra dige Graphen
- Konstruktion Eulerscher Kreise aus Kantenuber deckungen
- eq Ekn Damit gilt vq V kn
- V ki so dass k kn eine Anordnung
- Auch dazu eine Skizze
- Kapitel Frbungsprobleme a
- Kapitel Kurzeste Wege
- dist und diste en
- dist ek distp
- Kapitel Minimale aufspannende Bume a
- Kapitel Maximale Flusse
- Es gilt dann
- valow val ow min
- Kapitel Ein merkwurdiger Dialog uber merkwurdige Graphprobleme
- Wochen spter a E Here we are
- G V E s t dist E N
- mintour falls mglich o sorry sonst
- Wochen spter a E Wir haben es
- mintour falls Heuristik was liefert sorry sonst
- Kapitel NPvollstndige Graphprobleme a
- j n en in i E und
- E dh v v E
- Aufwand Zahl der melementigen Teilmengen nentiell ist
- Reduktion und NPVollstndigkeit a
- NPvollstndige Graphenprobleme a
- Kapitel Was tun solange das Orakel fehlt
- Lokale Suche und Optimierung
- Abschwchung der Lsungsanforderungen a o
- mindiste se v mindiste te v
Vorschau
Algorithmen auf Graphen
Hans-J¨rg Kreowski o Universit¨t Bremen a Studiengang Informatik kreo@informatik.uni-bremen.de Wintersemester 2003/04
Inhaltsverzeichnis
1 Graphen in der Informatik 1.1 1.2 1.3 Wohlstrukturierte Flussdiagramme . . . . . . . . . . . . . . . . . . . . . . . . . Erzeuger-Verbraucher-System . . . . . . . . . . . . . . . . . . . . . . . . . . . . Verkehrsfluss auf Kreuzungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4 6 7 9
2 Eulersche Graphen 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9
Ungerichtete Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Wege und Eulersche Kreise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Einfache Eulersch-Tests – zu aufw¨ndig . . . . . . . . . . . . . . . . . . . . . . . 10 a Beobachtung zur Gradgradigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Beobachtung zum usammenhang . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Eulersch-Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Konstruktion eines Kreises in gradgradigen Graphen . . . . . . . . . . . . . . . . 12 L¨schen eines Kreises in gradgradigen Graphen . . . . . . . . . . . . . . . . . . 13 o Konstruktion einer Kanten¨berdeckung f¨r gradgradige Graphen . . . . . . . . . 13 u u
2.10 Konstruktion Eulerscher Kreise aus Kanten¨berdeckungen . . . . . . . . . . . . 14 u 3 F¨rbungsprobleme a 4 Kurzeste Wege ¨ 5 Minimale aufspannende B¨ume a 6 Maximale Flusse ¨ 7 Ein merkwurdiger Dialog uber merkwurdige Graphprobleme ¨ ¨ ¨ 17 19 25 29 34
1
8 NP-vollst¨ndige Graphprobleme a 8.1 8.2 8.3 8.4
37
Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Reduktion und NP-Vollst¨ndigkeit . . . . . . . . . . . . . . . . . . . . . . . . . 39 a Erf¨llbarkeitsproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 u a NP-vollst¨ndige Graphenprobleme . . . . . . . . . . . . . . . . . . . . . . . . . 42 44
9 Was tun, solange das Orakel fehlt? 9.1 9.2 9.3 9.4 Lokale Suche und Optimierung
. . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Abschw¨chung der L¨sungsanforderungen . . . . . . . . . . . . . . . . . . . . . . 44 a o Untere Schranken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Spezielle Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45