Aktualny program seminarium
Jeśli chcesz otrzymywać regularnie aktualny plan referatów, to napisz do sekretarza seminarium.
| 19.11.2025 | Paweł Rzążewski | PW |
| Problem zbioru niezależnego w grafach uporządkowanych, c.d. | ||
| \(\quad\)Kontynuujemy rozważania na temat problemu największego zbioru niezależnego w klasach grafów uporządkowanych z wykluczonym ustalonym podgrafem indukowanym. Tym razem skupimy się na algorytmach. Wyniki uzyskane we współpracy z Pawłem Rafałem Bielińskim i Martą Piecyk. | ||
Archiwalny program seminarium (rok akademicki 2025/2026)
| 12.11.2025 | Paweł Rafał Bieliński | PW |
| KTGiZU na kółku matematycznym | ||
| \(\quad\)Zaprezentuję garść problemów z olimpiad matematycznych szczebla międzynarodowego. Ich wspólną cechą jest (nieraz dość błyskotliwe) wykorzystanie metod K, TG i ZU. Przedstawię również klasyczne twierdzenie Steinitza, które wiąże zbiór niezależny w grafie z możliwością wpisania wielościanu w sferę. | ||
| 29.10.2025 | Seminarium odwołane |
| 22.10.2025 | Hubert Grochowski | PW |
| Grafy XOR-magiczne | ||
| \(\quad\) Graf \(G\) o \(2^n\) wierzchołkach nazwiemy grafem otwarcie (domknięcie) XOR-magicznym, jeśli jest spójny i istnieje bijekcja ze zbioru wierzchołków grafu G w zbiór ciągów binarnych długości n taka, że dla każdego wierzchołka tego grafu, suma etykiet wierzchołków w jego otwartym (domkniętym) sąsiedztwie jest równa wektorowi zerowemu. \(\quad\)W jednej z prac dotyczących tego tematu [1], Batal badał problem istnienia regularnych grafów XOR-magicznych. W szczególności, postawił on problem otwarty: czy istnieje graf nieparzyście (parzyście) regularny graf otwarcie (domknięcie) XOR-magiczny? \(\quad\)W trakcie referatu odpowiemy pozytywnie na wyżej wymieniony problem, pokazując istnienie takich grafów rzędu \(2^n\) dla każdego \(n\) większego od 3. Ponadto, przedstawimy warunek konieczny (w nurcie spektralnej teorii grafów) istnienia grafów otwarcie XOR-magicznych wraz z jego zastosowaniami do wybranych grafów Cayleya. \(\quad\)Współautorki: Sylwia Cichacz, Rita Zuazua [1] A. Batal, On the construction of XOR-magic graphs, Discrete Applied Mathematics 379 (2026), 288-315. | ||
| 15.10.2025 | Tomasz Krawczyk | PW |
| Problem Defensywnej Dominacji w klasie grafów przedziałowych | ||
| \(\quad\)W problemie Defensywnej Dominacji dla danego grafu G oraz liczb naturalnych l i k należy rozstrzygnąć, czy na wierzchołkach grafu G można rozmieścić l obrońców w taki sposób, aby chronili oni przed atakiem każdy podzbiór A wierzchołków o rozmiarze co najwyżej k (tzn. każdemu wierzchołkowi z atakowanego zbioru A można przypisać prywatnego obrońcę znajdującego się w tym wierzchołku lub w jego sąsiedztwie). Wiadomo, że problem Defensywnej Dominacji jest \(\Sigma_2^P\)-zupełny. Niestety, nie jest znany jego status złożonościowy w prostych klasach grafów, takich jak grafy przedziałowe czy grafy planarne. W swoim referacie przedstawię prosty algorytm zachłanny rozwiązujący problem Defensywnej Dominacji w klasie grafów przedziałowych w przypadku, gdy w każdym wierzchołku grafu można umieścić dowolną liczbę obrońców. Pokażę również, jaki związek zachodzi między klasycznym problemem Defensywnej Dominacji (co najwyżej jeden obrońca na wierzchołek) a problemem plecakowym. | ||
| 08.10.2025 | Paweł Rafał Bieliński | PW |
| Problem zbioru niezależnego w grafach uporządkowanych | ||
| \(\quad\)Wiele trudnych problemów algorytmicznych może być rozwiązane wydajniej w węższym zakresie sytuacji. Przykładem takiego podejścia jest rozważanie nie grafów dowolnych, ale tylko tych nie zawierających określonej podstruktury. W swoim referacie zaprezentuję wyniki dotyczące trudności problemu zbioru niezależnego w klasach grafów uporządkowanych wolnych od określonych podgrafów indukowanych. Przy pomocy odpowiednich redukcji wskażę szereg przypadków NP-trudnych, a poprzez konkretne algorytmy i wnioski strukturalne zidentyfikuję przypadki, które można rozwiązać w czasie wielomianowym. | ||