From f88b8071a623096f9004007ced8ec97195aaa218 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sat, 25 Sep 2021 16:43:39 +0200 Subject: zweite Lesung --- buch/chapters/70-graphen/chapter.tex | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'buch/chapters/70-graphen/chapter.tex') 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. -- cgit v1.2.1