Strona główna > Archiwalny program seminarium > 2009/2010
2009/2010
14 X Natalia Petryszyn
"K_{1,2}-zakorzeniona dekompozycja z zakorzenionym centrum"
21X Zbigniew Lonc
"O silnej równoważności grafów"
28X Paweł Naroski
"Długie Cykle w Hipergrafach 3-Jednorodnych Spójnych w Słabszym Sensie niż Poprzednio. "
4XI Michał Kukieła (Uniwersytetu Mikołaja Kopernika w Toruniu)
"Posety i homotopia"
9XI Piotr Micek (UJ)
"Jedzenie grafów".
18XI Jarosław Grytczuk
"Kapsle na grafach"
25XI Lukasz Rożej
"minimalny koszt zasięgu sieci radiowej w drzewie"
2 XII Bartek Jabłoński
"Co nieco o algebrach grafowych" na podstawie artykułu M.Kozik G.Kum, "The subdirectly irreducible algebras in the variety generated by graph algebras"
9 XII Krzysztof Bryś
"Spojne i slabo spojne zbiory dominujace w grafach euklidesowych"
16 XII Konstanty Szaniawski
"Zachłanne ograniczone T-kolorowanie"
23 XII Michał Tuczyński
" O klikach separujących, grafach prawie cięciwowych i problemie najcięższego zbioru niezależnego "
6 I Jakub Kierzkowski
"Wielomian niezależności grafu w punkcie -1"
13 I Paweł Rzążewski
"L(2,1)-kolorowanie"
24 II Jarek Grytczuk
"Problem koloru kapelusza na grafie"
3 III Krzysztof Petelczyc (Uniwersytet Białostocki)
"Metoda częściowych zbiorów różnicowych i sumowanie struktur incydencyjnych".
10 III Przemysław Gordinowicz (Politechnika Łódzka)
"O grafach izomorficznych z sąsiedztwem i przeciwsąsiedztwem swoich wierzchołków"
17 III Armin Fügenschuh (ZIB)
"Discrete-Continuous and PDE Optimization - The Mixed-Integer Linear Perspective"
Continuous nonlinear optimization, optimization with PDE-constraints and mixed-integer linear programming are usually considered as distinct fields of mathematics. However, many real-world problems consist of a mixture of phenomena from these fields. How should we model and solve them? In this talk, we assume the mixed-integer linear (MILP) perspective.
In the first part we give a survey how to model nonlinear constraints by various kinds of linear approximations. The second part of the talk deals with an application of these methods to a network design problem from the industrial treatment of waste paper in order to obtain recovered paper. One important step in this process is the separation of stickies that are normally attached to the paper. If not properly separated, remaining stickies reduce the quality of the recovered paper or even disrupt the production process. In the third part we introduce the coolest path problem, which is a mixture of the shortest path problem from combinatorial optimization and the heat conduction problem from the field of partial differential equations. Together, they make up a control problem, where some geometrical object traverses a digraph in an optimal way, with constraints on intermediate or the final state. We discuss some properties of the problem and demonstrate that it can be formulated as a linear mixed-integer program.
24 III Witold Szczechla (UW)
"Rozwiazanie problemu odgadywania trzech kolorow na grafach cyklicznych"
Przy okraglym stole siedzi N osob w kolorowych kapeluszach. Gra polega na
tym, ze nikt nie zna koloru swojego kapelusza i ma go odgadnac (np.
zapisujac na kartce). Wiadomo, ze kazdy kapelusz jest zolty, zielony lub
niebieski, ale utrudnieniem jest fakt, ze kazda osoba widzi jedynie kolory
kapeluszy swych dwoch sasiadow (przycmione swiatlo) i tylko na tej
podstawie podaje odpowiedz. Strategie odgadywania nazwiemy wygrywajaca,
gdy dla kazdego ukladu kolorow co najmniej jedna osoba podaje poprawna
odpowiedz. Dla jakich liczb N taka strategia istnieje?
Rozwiazanie tej zagadki zostanie przedstawione na seminarium. Sytuacja
dla N>4 jest odmienna niz dla poczatkowych wartosci. Na przyklad
strategia wygrywajaca nie istnieje dla N=2009, a istnieje dla N=2010 i ma
pewne zwiazki z topologia.
****************************************************************
"A solution of the three-colour hat guessing problem for the cycle graphs"
N people wearing coloured hats are sitting around the table. They are
playing a game in which nobody knows his/her own hat colour and is
supposed to guess it (say, writing it down on a piece of paper). It is
known that each hat is either yellow, green, or blue, but in the dim light
everyone can only make out the hat colour of his or her two neighbours and
this must be the only basis for the guess. A guessing strategy is called
winning if it guarantees at least one correct answer for each assignment
of colours. For which numbers N such a strategy exists?
A solution of this puzzle will be presented in this seminar. The
situation for N>4 is different than that for the smallest values. For
example, a winning strategy does not exist for N=2009 but exists for
N=2010 and has a connection with topology.
7 IV Michał Tuczyński
"Nowe, jeszcze lepsze oszacowanie złożoności algorytmu zliczającego transwersale w grafie"
14 IV Katarzyna Rybarczyk-Krzywdzińska (UAM).
"Losowe grafy przecięć. Modelowanie sieci i ich analiza".
21 IV Lukasz Rożej
"Wymiar metryczny grafu"
28 IV Anna Zapart
"Lokalne Własności Kompleksów Symplicjalnych"
5V Paweł Rzążewski
"Problem k-L(2,1)-kolorowania grafów w ujęciu algorytmicznym"
12 V Sebastian Czerwiński (UZ)
"Problem samotnego biegacza"
2 VI Marta Przyborowska
"Przykłady rekonstrukcji zbiorów częściowo uporządkowanych"
9 VI Jakub Kierzkowski
"Sktrum laplpeasjanu grafu"