diff options
| author | Andreas Müller <andreas.mueller@ost.ch> | 2021-09-25 16:43:39 +0200 |
|---|---|---|
| committer | Andreas Müller <andreas.mueller@ost.ch> | 2021-09-25 16:43:39 +0200 |
| commit | f88b8071a623096f9004007ced8ec97195aaa218 (patch) | |
| tree | 9fad214708204690b2f724459234d66ffde8d12b /buch/chapters/70-graphen/chapter.tex | |
| parent | more missing periods (diff) | |
| download | SeminarMatrizen-f88b8071a623096f9004007ced8ec97195aaa218.tar.gz SeminarMatrizen-f88b8071a623096f9004007ced8ec97195aaa218.zip | |
zweite Lesung
Diffstat (limited to 'buch/chapters/70-graphen/chapter.tex')
| -rw-r--r-- | buch/chapters/70-graphen/chapter.tex | 5 |
1 files changed, 2 insertions, 3 deletions
diff --git a/buch/chapters/70-graphen/chapter.tex b/buch/chapters/70-graphen/chapter.tex index 1fb61b6..14240f4 100644 --- a/buch/chapters/70-graphen/chapter.tex +++ b/buch/chapters/70-graphen/chapter.tex @@ -22,8 +22,7 @@ Die Bedeutung des Graphenkozeptes wird unterstrichen von der Vielzahl von Fragestellungen, die über Graphen gestellt worden sind, und der zugehörigen Lösungsalgorithmen, die zu ihrer Beantwortung gefunden worden sind. -Die Komplexitätstheorie hat sogar gezeigt, dass sich jedes diskrete -\index{Komplexitätstheorie}% +Die Komplexitätstheorie hat sogar gezeigt, dass sich jedes NP-vollständige Problem in ein Graphenproblem umformulieren lässt. \index{Komplexitätstheorie}% @@ -46,7 +45,7 @@ ins gleiche Zeitintervall geplant werden. Das zugehörige abstrakte Graphenproblem heisst das Färbeproblem: \index{Färbeproblem}% ist es möglich, mit einer beschränkten Anzahl von Farben, oder im -vorliegenden Fall Zeitintervalle, die Knoten +vorliegenden Fall Zeitintervallen, die Knoten des Graphen so einzufärben, dass benachbarte Knoten niemals die gleiche Farbe haben. |