Kolorowanie kul Hilberta

Speaker(s)

Michał Przybyłek

Affiliation

Uniwersytet Warszawski

Date

May 28, 2020, 10:15 a.m.

Information about the event

https://meet.google.com/hey-wojt-wej

Seminar

Seminar of Numerical Analysis Group

---

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.

---