Nieskierowany graf G = (V, E) ze zbiorem wierzchołków V, to symetryczna relacja binarna E \subseteq V x V. Dla grafu G jego k-kolorowanie to funkcja f : V -> {1, 2, ..., k} taka, że: E(v, w) implikuje f(v) \= f(w). Problem kolorowania grafów formułujemy następująco: mając dany skończony graf G = (V, E) rozstrzygnij czy G jest k-kolorowalny. Jest to znany w informatyce problem NP-zupełny.
Podczas referatu przedyskutuję metryczny wariant powyższego problemu: V zostanie zastąpione przez Polską przestrzeń metryczną, E zostanie zastąpione przez symetryczną nieujemną ciągłą funkcją E : V x V -> R, zbiór kolorów {1, 2, ..., k} zastąpiony zostanie przez standardowy k-wymiarowy sympleks K, natomiast przez k-kolorowanie G będziemy rozumieć ciągłą funkcję f : V -> K taką, że: E(v, w) >= 1 - |f(v) - f(w)|.
Modelowym przykładem będą grafy, których zbiory wierzchołków są definiowalnymi podzbiorami ośrodkowej przestrzenii Hilberta.
You are not logged in |
