$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Matematyka Dyskretna
(prowadzone przez M.Woźniaka)

We wtorek, 3 stycznia 2006 roku, o godzinie 12:45

w sali 304, łącznik A-3-A-4, A G H

Karol SUCHAN

(WMS AGH Kraków, LIFO Orléans)

wygłosi referat pod tytułem:

Zanurzenia w grafy przedziałów

Graf prosty jest grafem przedziałów jeżeli instnieje rodzina przedziałów na prostej i bijekcja między t^1 rodzin^1 a zbiorem wierzchołków grafu taka, że dwa wierzchołki s^1 przystaj^1ce wtw gdy odpowiednie przedziały się przecinaj^1.
Klasa grafów przedziałów jest ważna ze względu na liczne zastosowania, min. w biologii, chemii, archeologii, gdzie przedziały na prostej (z ich relacjami) s^1 naturalnym sposobem modelowania zagadnień. Ponad to, wiele problemów, które s^1 NP-trudne w ogólnym przypadku, ma szybkie i eleganckie rozwi^1zania gdy ograniczy się je do klasy grafów przedziałów.
Wobec tego, interesuj^1cy jest problemem zanurzenia dowolnego grafu $G=(V,E)$ w grafie przedziałów $H=(V,E \cup F)$, dodaj^1c jak najmniejsz^1 liczbę krawędzi ($\vert F\vert$). Rownie ciekawy jest problem znalezienia grafu przedziałów $H$, w którym rozmiar największej kliki będzie jak najmniejszy ($\omega(H)$). Niestety oba te zagadnienia s^1 NP-trudne.
To stwierdzenie stanowi motywację dla badania minimalnych zanurzeń w grafy przedziałów, tzn. poszukiwania grafu $H$ dla którego zbiór dodanych krawędzi $F$ jest minimalny ze względu na zawieranie. Szczególnie, że rozwi^1zania dla obu wczeÓniejszych problemów znajduj^1 sie pomiędzy rozwi^1zaniami tego ostatniego.
Na seminarium zostan^1 zaprezentowane prace nad charakteryzacj^1 minimalnych zanurzeń w grafy przedziałów i algorytmami ich odnajdywania.

--------------------------------