В четверг 30 января я проведу очередной вебинар нашего курса подготовки к олимпиадам по математике. Занятие пройдет с 11 до 13 часов (Мск) и будет посвящено графам. Тема эта огромна; что именно мы будем обсуждать?

1. Конечно, невозможно обойти вниманием лемму о рукопожатиях (сумма степеней вершин равна удвоенному числу ребер). Посмотрим, какие задачи предлагаются тут на олимпиадах — обычно они не сложные. Будет задача, комбинирующая лемму о рукопожатиях и рыцарей со лжецами 🙂

2. Поговорим о двудольных графах — они возникают в задачах довольно часто. Число ребер двудольного графа равно сумме степеней вершин каждой доли, и этот факт постоянно работает в различных задачах. Разберем обещанную на прошлом вебинаре задачу, где двое играют на графе 🙂

3. Наконец, посмотрим симпатичные задачи на оценку плюс пример с участием графов. Мало того — сюда также подтянутся рыцари и лжецы, деревья, раскраска ребер графа и принцип крайнего!