diff options
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. |