Podczas wykładu pogramy w gry na grafach – od prostych do bardziej skomplikowanych – i zastanowimy się, co to znaczy optymalna strategia. Graf to struktura składająca się z wierzchołków połączonych krawędziami. Można stworzyć grę, której celem jest utworzenie jednego z grafów: trójkąta, ścieżki, cyklu, skojarzenia, kliki, gwiazdy itp. W grze Konstruktor-Malarz Konstruktor stara się utworzyć zadany, jednokolorowy podgraf poprzez dodawanie krawędzi. Malarz decyduje, czy każda nowa krawędź będzie czerwona czy niebieska, próbując utrudnić Konstruktorowi utworzenie jednokolorowej struktury.
Będziemy analizować, jak szybko (i czy w ogóle) Konstruktor jest w stanie skończyć grę. A może zamienimy ich role? Jeśli czas pozwoli, zajrzymy także do gier wierzchołkowych. Na koniec odkryjemy, dlaczego te gry są matematycznie istotne. Kredki mile widziane!
